Linear Assignment

Problem 1.  For this problem use the $4\times 4$ matrix

$A = \left[ \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 0 & 2 & 4 & 6 \\ 1 & x & 7 & y \\ 1 & 0 & 0 & 1 \end{array}\right]$

(a) Are there values that we can assign $x$ and $y$ so that $A$ is not an isomorphism?  Explain your answer, and, if your answer is yes, provide two such values.

(b) Are there values that we can assign $x$ and $y$ so that $A$ is an isomorphism?  Explain your answer, and if your answer is yes, provide two such values.

Answer 1.  (a) Note that if we choose $x = 4$ and $y = 10$, then row 3 equals the sum of row 1 and row 2 which implies $A$ is not an isomorphism.

(b) In general, we can compute that the determinant of $A$ is $44 - 6x - 2y$, so provided this expression is never zero, then $\det A \neq 0 \iff A$ is an isomorphism.  In particular, we can choose $x = 0 = y$ so that $\det A = 44.$

Problem 2.  For this problem let $A$ be a square, $n \times n$ matrix.

(a) Explain why $\det A = 0 \iff$ there exists a non-zero vector $\vec{v} \in \mathbb{R}^n$ such that $A\vec{v} = \vec{0}$.

(b) Explain why a non-zero vector $\vec{v} \in \mathbb{R}^n$ is an eigenvector for $A$ (with eigenvalue $\lambda$) $\iff \det\left(A-\lambda\,I_n\right) = 0$.

Answer 2.  (a) We have already shown that there exists a non-zero vector $\vec{v}$ such that $A\vec{v} = \vec{0} \iff A$ is not one-to-one.  (By the Rank Nullity Theorem, this also implies that $A$ is also not onto.)

We have also discussed that $\det A = 0 \iff A$ is singular, i.e. $A$ is an isomorphism (from $\mathbb{R}^n$ to $\mathbb{R}^n$).  Being an isomorphism requires that $A$ be linear, one-to-one, and onto.  Since matrix multiplication is always linear, the determinant equals zero if and only if $A$ is either not one-to-one or not onto.  Again, by the Rank Nullity Theorem, $A$ is not one-to-one $\iff \, A$ is not onto.

Hence, $\det A = 0 \iff A$ is not one-to-one $\iff \, \exists \, \vec{v} \neq \vec{0}, A\vec{v} = \vec{0}$.

(b) By definition, an eigenvector must satisfy $\vec{v} \neq \vec{0}$.  Therefore, $\vec{v}$ is an eigenvector for $A$ (with eigenvalue $\lambda$) if and only if $A\vec{v} = \lambda\vec{v} \iff A\vec{v} = \lambda\,I\vec{v} \iff A\vec{v} - \lambda I\vec{v} = \vec{0} \iff (A-\lambda I)\vec{v} = \vec{0} \iff \det(A-\lambda I) = 0$ since, by our work in part (a), the matrix $A-\lambda I$ “kills” a non-zero vector if and only if its determinant is zero.

Problem 3.  Let $h \in \mathcal{L}(\mathbb{R}^2, \mathbb{R}^2)$ be the linear transformation

$h(x,y) = (x + 2y, 2x + y)^T$

(a) Compute the matrix representation $\text{Rep}_{\mathcal{E}_2, \mathcal{E}_2} (h) = M$.

(b) Use your work in part (b) of Problem 2 to compute all of the possible eigenvalues of the matrix $M$ from part (a) of this problem.  (Note: in this case you should find two distinct eigenvalues $\lambda_1, \lambda_2 \in \mathbb{R}$.)

(c ) Find a change-of-basis matrix $P$ so that

$P^{-1}\, M \, P = \left[ \begin{array}{cc} \lambda_1 & 0 \\ 0 & \lambda_2 \end{array}\right]$

(d) Take a moment to draw yourself a congratulatory picture (say, of a rainbow or a flower or something else nice), since you just diagoanlized your first matrix!  Yay you!

(a) This matrix representation is given by

$\left( \begin{array}{cc} 1 & 2 \\ 2 & 1 \end{array} \right)$

(b) An eigenvalue will necessarily make the polynomial $p(\lambda) = \det(A-\lambda I)$ equal zero.  Therefore we can compute these eigenvalues by solving

$\displaystyle p(\lambda) = \det \left( \begin{array}{cc} 1-\lambda & 2 \\ 2 & 1-\lambda \end{array}\right) = (1-\lambda)^2 - 4 = \lambda^2 - 2\lambda -3 = 0$

Factoring and/or the quadratic formula tells us that this polynomial has two roots, namely $\lambda_1 = 3$ and $\lambda_2 = -1$.

(c ) As discussed in class, we will have

$P^{-1} = \left[ \begin{array}{ccc} | & & | \\ \vec{v}_1 & \cdots & \vec{v}_n \\ | & & | \end{array}\right]$

where the vectors $\mathcal{B} = \{\vec{v}_1, \cdots, \vec{v}_n\}$ are an eigenbasis (with respect to the given matrix).  Therefore, to construct this matrix we need to find the associated eigenbasis.

This can be accomplished by first finding a basis for the eigenspace $E_{\lambda_1} = \mathcal{N}(A-\lambda_1\,I)$ and then finding a basis for the eigenspace $E_{\lambda_2} = \mathcal{N}(A-\lambda_2\,I)$.  Finding these bases corresponds to solving two homogeneous systems:

$\displaystyle \left( \begin{array}{cc|c} -2 & 2 & 0 \\ 2 & -2 & 0 \end{array}\right) \Rightarrow E_{\lambda_1} = \left\{ y\left(\begin{array}{c} 1 \\ 1 \end{array}\right) : y \in \mathbb{R} \right\}$

$\displaystyle \left(\begin{array}{cc|c} 2 & 2 & 0 \\ 2 & 2 & 0 \end{array}\right) \Rightarrow E_{\lambda_2} = \left\{ y\left(\begin{array}{c} 1 \\ -1 \end{array}\right) : y \in \mathbb{R}$

Each eigenspace is one-dimensional, and so we may select a single basis vector from each.  Our eigenbasis is, for instance,

$\mathcal{B} = \left\{ \left(\begin{array}{c} 1 \\ 1 \end{array}\right), \, \left\{ y\left(\begin{array}{c} 1 \\ -1 \end{array}\right)$

As a result we have

$\left( \begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}\right)\,\left(\begin{array}{cc} 1 & 2 \\ 2 & 1 \end{array}\right)\,\left( \begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}\right)^{-1} = \left(\begin{array}{cc} 3 & 0 \\ 0 & -1 \end{array}\right)$

Problem 4.  Compute the area of the parallelogram shown in the picture below.

(Note: unit lengths are marked on the axes above.)

Answer 4.  This can be computed by writing down the two black vectors, $\vec{v}_1$ and $\vec{v}_2$, as columns in a matrix

$A = \left[ \begin{array}{cc} | & | \\ \vec{v}_1 & \vec{v}_2 \\ | & | \end{array}\right ]$.

Then the desired area is $|\det A|$.

Problem 5.  (a) Find $A^{-1}$ given

$A = \left[ \begin{array}{cc} \pi & 1 \\ 2 & 4 \end{array}\right]$.

(b) Find $A^{-1}$ given

$A = \left[ \begin{array}{ccc} 1 & 2 & 3 \\ 1 & 1 & 1 \\ 3 & 5 & 8 \end{array}\right]$.

If we want to interpret $A$ as a change-of-basis matrix, $A = \text{Rep}\left(\text{id}_{\mathbb{R}^3}\right)_{\mathcal{E}_3, \mathcal{B}}$, what are the basis vectors $\mathcal{B} = \{ \vec{v}_1, \vec{v}_2, \vec{v}_3 \}$?

Answer 5.  (a) The matrix $A^{-1}$ is given by

$A^{-1}= \frac{1}{4\pi-2}\left[\begin{array}{cc}4 & -1 \\ -2 & \pi \end{array}\right]$

(b) The matrix $A^{-1}$ is given by

$A^{-1} = \left[\begin{array}{ccc} -3 & 1 & 1 \\ 5 & 1 & -2 \\ -2 & -1 & 1 \end{array}\right]$

The basis $\mathcal{B}$ contains the vectors

$\mathcal{B} = \left\{ \left(\begin{array}{c} -3 \\ 5 \\ -2 \end{array}\right), \left(\begin{array}{c} 1 \\ 1 \\ -1 \end{array}\right), \left(\begin{array}{c} 1 \\ -2 \\ 1 \end{array}\right)\right\}$

Problem 6. Let $D$ denote an $n \times n$ diagonal matrix:

$D = \left[ \begin{array}{cccc} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n \end{array} \right]$.

Under what conditions is $D$ invertible?  Write down the inverse matrix $D^{-1}$ (assuming the conditions you specified are met).

Answer 6.  $D$ is invertible provided each diagonal entry $\lambda_i \neq 0$.  When this condition is met, the inverse matrix is a diagonal matrix with entries

$\displaystyle (D)_{i,i} = \frac{1}{\lambda_i}$

Problem 7.  The trace of a square matrix $A \in \mathcal{M}_{n\times n}$ is the sum of the diagonal entries of $A$:

$\displaystyle \text{tr}A = \sum_{i=1}^n \! a_{ii} = a_{11} + a_{22} + \cdots + a_{nn}$.

(a) Prove that the trace, regarded as a function $\text{tr}:\mathcal{M}_n \to \mathbb{R}$ is a homomorphism.

(b) A proof is written below.  Write down the theorem this proof demonstrates.

Theorem: Given two matrices, $\text{tr}(AB) = \text{tr}(BA)$.

proof.  Let $A, B \in \mathcal{M}_{n\times n}$.

Let us notate the $(i, j)$-entry of $A$ by $a_{ij}$, the $(i, j)$-entry of $B$ by $b_{ij}$, the $(i, j)$-entry  of the product $AB$ by $c_{ij}$, and the $(i, j)$-entry of the product $BA$ by $d_{ij}$.

Then the traces of these matrices is given by the sum of their respective diagonal entries so that

$\text{tr}A = a_{11} + a_{22} + \cdots + a_{nn}$

$\text{tr}B = b_{11} + b_{22} + \cdots b_{nn}$

$\text{tr}AB = c_{11} + c_{22} + \cdots c_{nn}$

$\text{tr}BA = d_{11} + d_{22} + \cdots d_{nn}$

We want to prove that $\text{tr}(AB) = \text{tr}(BA)$, i.e. that

$c_{11} + c_{22} + \cdots + c_{nn} = d_{11} + d_{22} + \cdots d_{nn}$.

To prove this, we first note that

$c_{ij} = \text{(row i)}_A \cdot \text{(col j)}_B \text{ and } d_{ij} = \text{(row i)}_B \cdot \text{(col j)}_A$

This lets us replace each $c_{ii}$ expression appearing in the trace of $AB$ in terms of the entries of $A$ and $B$.  In particular, we find

$\text{tr}(AB) = \text{(row 1)}_A\cdot\text{(col 1)}_B + \text{(row 2)}_A\cdot\text{(col 2)}_B + \cdots + \text{(row n)}_A\cdot \text{(col n)}_B$

$= \left(a_{11}b_{11} + a_{12}b_{21} + \cdots + a_{1n}b_{n1}\right) + \left(a_{21}b_{12} + a_{22}b_{22} + \cdots a_{2n}b_{n2}\right) + \cdots + \left(a_{n1}b_{1n} + a_{n2}b_{2n} + \cdots a_{nn}b_{nn}\right)$

$\displaystyle = \left( \sum_{i=1}^n a_{1i}b_{i1} \right) + \left( \sum_{i=1}^n a_{2i}b_{i2}\right) + \cdots + \left(\sum_{i=1}^n a_{ni}b_{in}\right) = \sum_{i,j = 1}^n a_{ji}b_{ij}$

Similarly, the trace of the product $BA$ works out as follows:

$\text{tr}(BA) = \text{(row 1)}_B\cdot\text{(col 1)}_A + \text{(row 2)}_B\cdot\text{(col 2)}_A + \cdots + \text{(row n)}_B\cdot \text{(col n)}_A$

$= \left(b_{11}a_{11} + b_{12}a_{21} + \cdots + b_{1n}a_{n1}\right) + \left(b_{21}a_{12} + b_{22}a_{22} + \cdots b_{2n}a_{n2}\right) + \cdots + \left(b_{n1}a_{1n} + b_{n2}a_{2n} + \cdots b_{nn}a_{nn}\right)$

$\displaystyle = \left( \sum_{i=1}^n b_{1i}a_{i1} \right) + \left( \sum_{i=1}^n b_{2i}a_{i2}\right) + \cdots + \left(\sum_{i=1}^n b_{ni}a_{in}\right) = \sum_{i,j = 1}^n b_{ji}a_{ij} = \sum_{i, j = 1}^n a_{ij}b_{ji}$

Note that in this last sum if we interchange the names of the indices $i$ and $j$, we obtain the exact same expression for the $\text{tr}(AB)$.  This implies that these two sums are equal, completing the proof.  $\square$

(c ) Suppose that a square matrix $A$ is diagonalizable.  Explain why $\det A =$ the product of $A$‘s eigenvalues.  Using part (b) from this problem, explain why $\text{tr}A =$ the sum of $A$‘s eigenvalues.

Answer 7.  (a) Proving the trace is linear is straightforward.

(b) The Theorem claims that $\text{tr}(AB) = \text{tr}(BA)$.

(c ) First, we can use the fact that for determinants, $\det(AB) = \det(A)\det(B)$.  Suppose $A$ diagonalizes to $D$ so that $P^{-1}AP = D$.  We then have

$\det D = \det(P^{-1}AP) = \det(P^{-1})\det(A)\det(P) = \det A$

and since $D$ is a diagonal matrix, by our (many) formula(s) for computing the determinant we find that

$\lambda_1\lambda_2\cdots\lambda_n = \det D = \det A$

where $\lambda_i$ is an eigenvalue for $A$.

For the trace claim, we can perform a similar bit of magic.  Note that

$\text{tr}(D) = \text{tr}(P^{-1}AP) = \text{tr}(P^{-1}PA) = \text{tr}(A)$

and since the trace of $D$ is $\text{tr}D = \lambda_1 + \cdots \lambda_n$ we find that the trace of $A$ is the sum of its eigenvalues.

Problem 8.  (a) Given two square matrices, $A, B \in \mathcal{M}_{n\times n}$, prove that $(AB)^T = B^T\,A^T$.

(b) Suppose $A$ is a non-singular matrix.  Prove that $\left(A^{-1}\right)^T = \left(A^T\right)^{-1}$.

Answer 8.  (a) Let $C = AB$, and now that the $(i, j)$ entry of $C$ is the number

$c_{ij} = (\text{row}_i A)\cdot (\text{col}_j B)$

so that the $(i, j)$ entry of $C^T$ is

$c_{ji} = (\text{row}_j A)\cdot(\text{col}_i B)$

We now need to argue that the $(i, j)$ entry of the product $B^TA^T$ equals $c_{ji}$.  Of course

$\left(B^TA^T\right)_{i,j} = (\text{row}_i B^T)\cdot(\text{col}_j A^T) = (\text{col}_i B)\cdot (\text{row}_j A) = c_{ji}$.

(b) To prove the claim we simply use part (a) and multiply:

$AA^{-1} = I \Rightarrow \left(AA^{-1}\right)^T = I^T = I$

and by part (a) we have

$\left(A^{-1}\right)^T\,A^T = I \Rightarrow \left(A^{-1}\right)^T = \left(A^T\right)^{-1}$

Problem 9. (Bonus)  For this problem, get help from a math student who has taken Algebra I.

Prove that the set $\text{GL}_n(\mathbb{R}) = \{ \text{ all invertible, } n \times n \text{ matrices with real entries } \}$ is a group under matrix multiplication.

Answer 9.  (definition)  A group is a set, $G$, with a binary operation $\star : G\times G \to G$ satisfying three conditions.

(1) $\exists \, e \in G, g\star e = g = e \star g \, \, \forall \, g \in G$

(2) $\forall \, g \in G, \exists \, h \in G, g\star h = e = h \star g$

(3) $\star$ is associative; i.e. $\forall \, a, b, c \in G, a\star(b\star c) = (a\star b)\star c)$.

To prove that $\text{GL}_n(\mathbb{R})$ is a group under matrix multiplication, we must show these three conditions hold (where $A\star B$ means $AB$).

First, the $n \times n$ identity matrix, $I_n \in \text{GL}_n(\mathbb{R})$, satisfies property (1) since for all square matrices $AI = A = IA$.

Second, given an invertible matrix $A \in \text{GL}_n(\mathbb{R})$, we have that $A^{-1} \in \text{GL}_n(\mathbb{R}$ with $AA^{-1} = I = A^{-1}A$.

Third, by the definition of matrix multiplication it follows that $A(BC) = (AB)C$ — in fact, the easiest way to argue this is to view matrix multiplication not as “rows times columns,” but as representing the composition of homomorphisms.

fdfd