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!

Answer 3.

(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.

det

(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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s