(1a) $A$ is diagonalizable if it can be written $X\Lambda X^{-1}$ for some invertible matrix $X$. The eigenvalues go on the diagonal of $\Lambda$ (in any order) and the corresponding eigenvectors are the columns of $X$.
(GS p314 6.2 p1) Factor the following matrices into $A = X\Lambda X^{-1}$:
$A = \begin{bmatrix} 1 & 2 \\ 0 & 3 \end{bmatrix}$ and $A = \begin{bmatrix} 1 & 1 \\ 3 & 3 \end{bmatrix}$.
Solution: (i) The matrix $A=\begin{pmatrix}1&2\\0&3\end{pmatrix}$ is upper triangular, so its eigenvalues are the entries on the diagonal, i.e., $1$ and $3$. For $v=\begin{pmatrix}a\\b\end{pmatrix}$,
$$Av=\begin{pmatrix}a+2b\\3b\end{pmatrix}.$$If $Av=v$, then $3b=b$, so $b=0$. Thus, an eigenvector for the eigenvalue $1$ is $\begin{pmatrix}1\\0\end{pmatrix}$. If $Av=3v$, then $a+2b=3a$, so $a=b$. Thus, an eigenvector for the eigenvalue $3$ is $\begin{pmatrix}1\\1\end{pmatrix}$. Putting the eigenvalues and eigenvectors into the matrices
$$\Lambda=\begin{pmatrix}1&0\\0&3\end{pmatrix},~~\text{and}~~X=\begin{pmatrix}1&1\\0&1\end{pmatrix}$$gives $A=X\Lambda X^{-1}$.
(ii) The characteristic polynomial for $A=\begin{pmatrix}1&1\\3&3\end{pmatrix}$ is
$$p(x)=\det\begin{pmatrix}1-x&1\\3&3-x\end{pmatrix}=(1-x)(3-x)-3=x^2-4x=x(x-4).$$The eigenvalues are the roots of this polynomial, namely $0$ and $4$ (note that we can also see that $0$ is an eigenvalue because the columns of $A$ are linearly dependent). As before, if $v=\begin{pmatrix}a\\b\end{pmatrix}$,
$$Av=\begin{pmatrix}a+b\\3a+3b\end{pmatrix}.$$We see that $Av=0$ if and only if $a=-b$. Thus, an eigenvector for the eigenvalue $0$ is $\begin{pmatrix}1\\-1\end{pmatrix}$. If $Av=4v$, then $a+b=4a$, so $b=3a$. Thus, an eigenvector for the eigenvalue $4$ is $\begin{pmatrix}1\\3\end{pmatrix}$. Putting the eigenvalues and eigenvectors into
$$\Lambda=\begin{pmatrix}0&0\\0&4\end{pmatrix},~~\text{and}~~X=\begin{pmatrix}1&1\\-1&3\end{pmatrix}$$gives $A=X\Lambda X^{-1}$.
(1b) If $A=X \Lambda X^{-1}$ then $A^3=( \ )( \ )( \ )$ and $A^{-1}=( \ )( \ )( \ )$.
Solution: Compute
$$A^3=X\Lambda X^{-1}X\Lambda X^{-1}X\Lambda X^{-1}=X\Lambda\Lambda\Lambda X^{-1}=X \Lambda^3 X^{-1}.$$Assume $A$ is invertible. We have $\Lambda=X^{-1}AX$, so $\Lambda$ is invertible because it is the product of invertible matrices. Thus, set $B=X\Lambda^{-1}X^{-1}$ and compute
$$AB=X\Lambda X^{-1}X\Lambda^{-1}X^{-1}=X\Lambda\Lambda^{-1}X^{-1}=XX^{-1}=I.$$This proves that $A^{-1}=B=X\Lambda^{-1}X^{-1}$.
Note that in general, $A^n=X\Lambda^n X^{-1}$ for any integer $n$ (also assuming $A$ is invertible if $n<0$).
(Optional) Check your work:
using LinearAlgebra
A = [1 2; 0 3]
Λ,X = eigen(A)
display(Λ) # Eigenvalues in machine picked order
display(X) # Eigenvectors normalized to unit vectors
2-element Array{Float64,1}:
1.0
3.0
2×2 Array{Float64,2}:
1.0 0.707107
0.0 0.707107
Λ,X = eigen(A^3)
display(Λ)
display(X)
2-element Array{Float64,1}:
1.0
27.0
2×2 Array{Float64,2}:
1.0 0.707107
0.0 0.707107
Λ,X = eigen(inv(A))
display(Λ)
display(X)
2-element Array{Float64,1}:
1.0
0.3333333333333333
2×2 Array{Float64,2}:
1.0 0.707107
0.0 0.707107
Find the pattern. (We are not asking for an explanation. We want you to experiment and observe.)
(2a) When n=3, if you generate random real matrices which of the following seem to be possible:
$[ \ ]$ All complex eigenvalues, $[ \ ]$ All real eigenvalues, $ [ \ ]$ 2 Real, One Complex, $ [ \ ]$ 2 Complex, One Real
Solution: The possibilities are: all real eigenvalues; and 2 complex, 1 real.
An example of all real eigenvalues is
$$\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix},$$whose only eigenvalue is $1$.
An example of 2 complex, 1 real is
$$\begin{pmatrix}0&-1&0\\1&0&0\\0&0&1\end{pmatrix},$$whose eigenvalues are $i$, $-i$, and $1$.
This makes sense because the eigenvalues are the roots of a cubic polynomial, and cubic polynomials can either have all real roots, or 2 complex roots and 1 real root.
howmany = 10 # if you like change 10 to anything
n = 3
for i = 1:howmany
display(eigvals(randn(n,n))) # random n x n
end
3-element Array{Complex{Float64},1}:
-1.0326565316917389 + 0.0im
0.6748820354452995 + 0.6727656200935755im
0.6748820354452995 - 0.6727656200935755im
3-element Array{Complex{Float64},1}:
-2.266604422992689 + 0.0im
0.35457475308031694 + 1.7051102618405212im
0.35457475308031694 - 1.7051102618405212im
3-element Array{Complex{Float64},1}:
-0.3141903037361268 + 0.5122022872233882im
-0.3141903037361268 - 0.5122022872233882im
-1.1860629033747003 + 0.0im
3-element Array{Complex{Float64},1}:
-0.7770609747976158 + 0.0im
0.1362058736113101 + 0.9694457536053633im
0.1362058736113101 - 0.9694457536053633im
3-element Array{Complex{Float64},1}:
0.7214103017519602 + 1.1537456995985798im
0.7214103017519602 - 1.1537456995985798im
-0.8389780038090663 + 0.0im
3-element Array{Complex{Float64},1}:
0.54985917981346 + 0.0im
-0.3643513153847361 + 1.0539143828625936im
-0.3643513153847361 - 1.0539143828625936im
3-element Array{Complex{Float64},1}:
0.11092292929223922 + 1.0061703385932412im
0.11092292929223922 - 1.0061703385932412im
0.42147542922943043 + 0.0im
3-element Array{Complex{Float64},1}:
0.11471880160861044 + 1.4004543555978073im
0.11471880160861044 - 1.4004543555978073im
0.46926868637691466 + 0.0im
3-element Array{Float64,1}:
-0.1984249946348733
1.6459164857606743
1.1119815491262333
3-element Array{Float64,1}:
-2.2468027521279437
0.7315762093315911
1.6060024423068209
(2b) When n=4, if you generate random real matrices what possibilities emerge for how many real and complex eigenvalues: (Note four real eigenvalues can happen, but it seems a bit rarer.)
Solution: For this, when we ask how many real or complex eigenvalues, we mean with multiplicity. This way, a $4 \times 4$ matrix will always have 4 total eigenvalues.
The possibilities are: all real; 2 complex, 2 real; and all complex.
An example of all real is again the identity
$$\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}.$$An example of 2 complex, 2 real is
$$\begin{pmatrix}0&-1&0&0\\1&0&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix},$$whose eigenvalues are $i$, $-i$, and $1$ with multiplicity 2.
An example of all complex is
$$\begin{pmatrix}0&-1&0&0\\1&0&0&0\\0&0&0&-1\\0&0&1&0\end{pmatrix},$$whose eigenvalues are $i$ and $-i$, both with multiplicity 2.
(These examples were chosen because they are block diagonal. The eigenvalues of block diagonal matrices are just the eigenvalues of the blocks, and the $2 \times 2$ $90^{\circ}$ rotation matrix $\begin{pmatrix}0&-1\\1&0\end{pmatrix}$ has eigenvalues $i$ and $-i$.)
howmany = 20
n = 4
for i = 1:howmany
display(eigvals(randn(n,n)))
end
4-element Array{Complex{Float64},1}:
1.560590175803797 + 0.0im
-0.983470317806491 + 1.6004504952058682im
-0.983470317806491 - 1.6004504952058682im
-1.4974930433589766 + 0.0im
4-element Array{Float64,1}:
1.781366984879747
0.34154201040846444
-2.695458982236387
-1.6376825271876745
4-element Array{Complex{Float64},1}:
-3.7595515040572054 + 0.0im
-0.009836252346407032 + 0.9178009133895911im
-0.009836252346407032 - 0.9178009133895911im
1.6731582374462488 + 0.0im
4-element Array{Complex{Float64},1}:
-0.8605521411312727 + 0.0im
-0.18112370487116083 + 0.916680392854106im
-0.18112370487116083 - 0.916680392854106im
0.7524322528454063 + 0.0im
4-element Array{Complex{Float64},1}:
0.1776257849143505 + 0.6153772958793717im
0.1776257849143505 - 0.6153772958793717im
1.3573167748250454 + 0.573282835303293im
1.3573167748250454 - 0.573282835303293im
4-element Array{Complex{Float64},1}:
2.7882092060243506 + 0.0im
-0.5042420558358356 + 0.0im
0.8566738479869862 + 0.8539761447900258im
0.8566738479869862 - 0.8539761447900258im
4-element Array{Complex{Float64},1}:
-2.5583881342066968 + 0.0im
1.2085478232261706 + 0.566454296322378im
1.2085478232261706 - 0.566454296322378im
-0.5672572382845301 + 0.0im
4-element Array{Complex{Float64},1}:
-1.1945805620881451 + 0.8744630704225174im
-1.1945805620881451 - 0.8744630704225174im
2.435771733106273 + 0.0im
1.6683747751531255 + 0.0im
4-element Array{Complex{Float64},1}:
1.1413085721625742 + 1.3024506153320938im
1.1413085721625742 - 1.3024506153320938im
-0.597759510194639 + 0.0im
-2.5603416709187736 + 0.0im
4-element Array{Float64,1}:
2.6005101270991724
0.7588751274631581
-1.6312801560076378
-0.929811902678773
4-element Array{Complex{Float64},1}:
0.40087100962577127 + 0.6687290326171628im
0.40087100962577127 - 0.6687290326171628im
-0.7258665002621363 + 0.6389799407819325im
-0.7258665002621363 - 0.6389799407819325im
4-element Array{Complex{Float64},1}:
-2.7140457832386717 + 0.0im
0.18728234751982387 + 0.12554189996880621im
0.18728234751982387 - 0.12554189996880621im
-0.9501013477859107 + 0.0im
4-element Array{Complex{Float64},1}:
-1.1497412238686227 + 0.0im
0.3643545596533507 + 0.0im
1.6897924378492708 + 1.509601719882982im
1.6897924378492708 - 1.509601719882982im
4-element Array{Complex{Float64},1}:
3.027046410750918 + 0.0im
-0.36138449990046223 + 1.3664106227167587im
-0.36138449990046223 - 1.3664106227167587im
0.5661404293396619 + 0.0im
4-element Array{Complex{Float64},1}:
-1.8394645481858496 + 0.0im
0.7895661101330409 + 0.9944327410575493im
0.7895661101330409 - 0.9944327410575493im
0.8160446029161094 + 0.0im
4-element Array{Float64,1}:
-1.2643016699210379
-0.8410158801763042
-0.4141691486387531
0.4843963394875232
4-element Array{Complex{Float64},1}:
-0.885493779142659 + 0.0im
0.6933733604465229 + 0.0im
0.1061350876033248 + 2.218126934263994im
0.1061350876033248 - 2.218126934263994im
4-element Array{Float64,1}:
-2.1030202480414952
-0.8751756978742045
1.2548671098233837
0.7109565510500513
4-element Array{Complex{Float64},1}:
-0.14972625824255384 + 0.8698827483385227im
-0.14972625824255384 - 0.8698827483385227im
-0.013393506842766014 + 0.26625342412377806im
-0.013393506842766014 - 0.26625342412377806im
4-element Array{Complex{Float64},1}:
-1.8065121423080175 + 0.0im
-0.6611989566331753 + 0.0im
1.0093584125178536 + 0.4408991075589041im
1.0093584125178536 - 0.4408991075589041im
(2c) What do you observe if the matrix is symmetric or antisymmetric? Try n=3,4,5. (You may interpret as 0 floating point numbers with an e-16 (meaning $10^{-16}$, E for exponent) or less.)
Solution: If $A$ is a symmetric matrix, then all of its eigenvalues are real. If $A$ is an antisymmetric matrix, then all of its eigenvalues are imaginary.
The problem does not ask for a proof, but here is one if you are curious. If $M$ is any matrix with complex number entries, then denote $M^*$ to be the conjugate transpose of $M$. That is, the $i,j$-entry of $M^*$ is the complex conjugate of the $j,i$-entry of $M$. Just like transpose, this has the property that $(M_1M_2)^*=M_2^*M_1^*$. Also, if $x=(x_1,x_2,\dots,x_n)$ is a vector of complex numbers, then
$$x^*x=\overline{x_1}x_1+\overline{x_2}x_2+\cdots+\overline{x_n}x_n=|x_1|^2+|x_2|^2+\cdots+|x_n|^2.$$The important thing here is that if $x$ is not the zero vector, then $x^*x>0$. Now, if $A$ is a real symmetric matrix and $x$ is an eigenvector for $A$ with eigenvalue $\lambda$, then
$$\lambda x^*x=x^*Ax=x^*A^*x=(Ax)^*x=(\lambda x)^*x=\overline{\lambda}x^*x.$$Divide $x^*x$ from both sides to get $\lambda=\overline{\lambda}$. Therefore, $\lambda$ is real.
If $A$ is a real antisymmetric matrix with $x$ and $\lambda$ as before, then
$$\lambda x^*x=x^*Ax=-x^*A^*x=-(Ax)^*x=-(\lambda x)^*x=-\overline{\lambda}x^*x.$$Like before, we get $\lambda=-\overline{\lambda}$, meaning $\lambda$ is imaginary.
howmany = 5
n = 4
for i = 1:howmany
A = randn(n,n)
A += A' # This means add A' (same as Aᵀ) to A making A symmetric
display(eigvals(A))
end
4-element Array{Float64,1}:
-4.902972236533854
-0.6286676691682798
1.3213847276733686
4.914903605080317
4-element Array{Float64,1}:
-6.988829218343527
-2.8755027636050765
1.5161605686106587
2.5779576875042447
4-element Array{Float64,1}:
-0.8413222960416971
0.16186523375286438
1.41310254932645
4.013188592206044
4-element Array{Float64,1}:
-2.768430079454699
-1.2509975472592465
0.47969069346733456
2.772779106923938
4-element Array{Float64,1}:
-3.46252181517286
-2.2496796074128413
-0.20583001253204872
1.8597540937537025
(3a) (GS p.314 p4) True or false: If the columns of X (eigenvectors of A) are linearly independent then
(a) A is invertible?
(b) A is diagonalizable
(c) X is invertible?
(d) X is diagonalizable
Solution: (a) False (e.g., $A=\begin{pmatrix}0&0\\0&0\end{pmatrix}$, $X=\begin{pmatrix}1&0\\0&1\end{pmatrix}$)
(b) True
(c) True
(d) False (e.g., $A=\begin{pmatrix}1&-2\\0&-1\end{pmatrix}$, $X=\begin{pmatrix}1&1\\0&1\end{pmatrix}$)
(3b) (GS p. 315 p11) True or false: If the eigenvalues of $A$ are $2,2,5$ then the matrix is certainly
(a) invertible
(b) diagonalizable
(c) not diagonalizable.
Solution: (a) True
(b) False (e.g., $A=\begin{pmatrix}2&1&0\\0&2&0\\0&0&5\end{pmatrix}$)
(c) False (e.g., $A=\begin{pmatrix}2&0&0\\0&2&0\\0&0&5\end{pmatrix}$)
(3c) (GS p. 315 p. 12) True or false: If the only eigenvectors of $A$ are multiples of (1,4) then A has
(a) no inverse
(b) a repeated eigenvalue
(c) no diagonalization $X \Lambda X^{-1}$.
Solution: (a) False (e.g., $A=\begin{pmatrix}0&1\\-16&8\end{pmatrix}$)
(b) True
(c) True
(4) If a matrix has eigenvalue 1, must it have singular value 1? If a matrix has eigenvalue 0, must it have fewer than n positive singular values?
Solution: (i) If a matrix has eigenvalue $1$, it might not have singular value $1$. An example is $A=\begin{pmatrix}0&1\\0&1\end{pmatrix}$, which has eigenvalues $0$ and $1$. But, it has compact SVD
$$A=\begin{pmatrix}1\\1\end{pmatrix}\begin{pmatrix}0&1\end{pmatrix}=\begin{pmatrix}1/\sqrt{2}\\1/\sqrt{2}\end{pmatrix}\begin{pmatrix}\sqrt{2}\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix}^T,$$so its singular values are $\sqrt{2}$ and $0$.
(ii) If a matrix has eigenvalue $0$, then $Av=0$ for some nonzero vector $v$. This means $A$ has nontrivial null space, so 0 is a singular value for $A$.
Solution: If the rank of $A$ is $n-1$, then its null space is $1$-dimensional. The null space is the column space of $V_2$ in the full SVD for $A$, and in this case, $V_2$ is just the last column of $V$. The eigenvector $x$ is in the null space, so $x$ is just a scalar multiple of the last column of $V$.
Solution: Let $A$ be the $n \times n$ matrix with $0$s down the diagonal and $1$s just above the diagonal:
$$A=\begin{pmatrix}0&1&0&0&\cdots\\0&0&1&0&\cdots\\0&0&0&1&\cdots\\0&0&0&0&\cdots\\\vdots&\vdots&\vdots&\vdots&\ddots\end{pmatrix}.$$A full SVD for $A$ is as follows. Let $U=I_n$ be the $n \times n$ identity, let $\Sigma$ be the diagonal $n \times n$ matrix whose diagonal has $n-1$ $1$s followed by $0$, and $V^T$ be $A$ itself. For example, when $n=5$, the SVD is
$$\begin{pmatrix}0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\\0&0&0&0&0\end{pmatrix}=\begin{pmatrix}1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\end{pmatrix}\begin{pmatrix}1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&0\end{pmatrix}\begin{pmatrix}0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\\0&0&0&0&0\end{pmatrix}.$$From this, we see that $A$ has $n-1$ singular values $1$.
Now, we will show that no matter what answer you give for the first part of this problem, $A$ is not diagonalizable. If $A$ had $n$ linearly independent eigenvectors, then they would all be in the null space of $A$ because $0$ is the only eigenvalue. But, this would force $A$ to be the $0$ matrix, which we know is impossible because $A$ has at least one nonzero singular value.
We admit this is straightforward, so why did we avoid it? From a practical perspective this can be numerically unstable as an algorithm. From a mathematical perspective, by getting too caught up with eigendecompositions, one loses perspective of all the utility of the SVD that we have seen all semester.
Solution: Let $A$ be an $m \times n$ matrix. For this problem, we are going to assume $n \le m$; the logic is very similar for $n \ge m$. Let $A=U\Sigma V^T$ be a full SVD for $A$. Compute
$$A^TA=(V\Sigma^T U^T)(U \Sigma V^T)=V \Sigma^T\Sigma V^{-1}.$$The matrix $\Sigma^T\Sigma$ is simply a diagonal $n \times n$ matrix whose diagonal entries are the squares of the $n$ singular values of $A$:
$$\Sigma^T\Sigma=\begin{pmatrix}\sigma_1^2&0&0&\cdots&0\\0&\sigma_2^2&0&\cdots&0\\0&0&\sigma_3^2&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&\sigma_n^2\end{pmatrix}.$$This expression for $A^TA$ shows that $A^TA$ is diagonalizable and that its $n$ eigenvalues are $\sigma_1^2,\sigma_2^2,\dots,\sigma_n^2$.
For $AA^T$, we have
$$AA^T=(U\Sigma V^T)(V \Sigma^T U^T)=U \Sigma\Sigma^T U^{-1}.$$The matrix $\Sigma \Sigma^T$ is a diagonal $m \times m$ matrix whose diagonal entries are the squares of the $n$ singular values of $A$ followed by $m-n$ $0$s:
$$\Sigma\Sigma^T=\begin{pmatrix} \sigma_1^2&0&0&\cdots&0&0&\cdots&0\\ 0&\sigma_2^2&0&\cdots&0&0&\cdots&0\\ 0&0&\sigma_3^2&\cdots&0&0&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&\sigma_n^2&0&\cdots&0\\ 0&0&0&\cdots&0&0&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&0&0&\cdots&0 \end{pmatrix}.$$Thus, the $m$ eigenvalues of $AA^T$ are $\sigma_1^2,\sigma_2^2,\dots,\sigma_n^2,0,\dots,0$.
As a final note, we see that the singular values of $A$ are the square roots of the eigenvalues of $A^TA$ if $n \le m$. Doing the same in the case where $n \ge m$, we would see that the singular values of $A$ are the square roots of the eigenvalues of $AA^T$.
Solution: If $A$ and $B$ are square $n \times n$ matrices, then compute the trace
$$\operatorname{Tr}(AB-BA)=\operatorname{Tr}(AB)-\operatorname{Tr}(BA)=\operatorname{Tr}(AB)-\operatorname{Tr}(AB)=0.$$But, $\operatorname{Tr}(I)=n$, so $AB-BA=I$ is possible only in the case $n=0$ (Yes, $0 \times 0$ matrices are a thing! In fact, $AB-BA=I$, where $A=B=I=\begin{pmatrix}\end{pmatrix}$).
For a proof using eigenvalues instead of trace, assume for the sake of contradiction that $n \ge 1$ and there exist matrices $A$ and $B$ such that $AB-BA=I$. Suppose $\lambda$ is an eigenvalue of $BA$ with a corresponding eigenvector $v$. Then,
$$ABv=(BA+I)v=\lambda v+v=(\lambda+1)v.$$Therefore, $\lambda+1$ is an eigenvector for $AB$. Now, there must exist some $\lambda_0$ that is an eigenvalue for $BA$ but not for $AB$, otherwise $\lambda+k$ would be an eigenvalue for $AB$ for any chosen eigenvalue $\lambda$ of $AB$ and every positive integer $k$. Let $v_0$ be an eigenvector for $BA$ with eigenvalue $\lambda_0$. We have
$$(AB)(Av_0)=A(BAv_0)=\lambda_0(Av_0).$$But, $\lambda_0$ is not an eigenvalue for $AB$, so the only way this is possible is if $Av_0=0$. Furthermore,
$$\lambda_0v_0=BAv_0=B0=0,$$so $\lambda_0=0$. However, because $Av_0=0$, $A$ is a singular matrix, so $AB$ is also singular. This means $AB$ has $0=\lambda_0$ as an eigenvalue, a contradiction. This finishes the proof.
(If you are wondering where we used the fact that $n \ge 1$, it is in the fact that $\lambda_0$ exists. If $n=0$, $BA$ doesn't have any eigenvalues at all, so there is no contradiction!)
Find a pattern (as an experimentalist, without proof) for the absolute values of eigenvalues of orthognal matrices.
Solution: If $A$ is an orthogonal square matrix and $\lambda$ is an eigenvalue of $A$, then $|\lambda|=1$.
For a proof if you are curious, recall the conjugate transpose notation $M^*$ from the solution to problem 2c above. If $x$ is an eigenvector for $A$ with eigenvalue $\lambda$, then
$$x^*x=x^*A^TAx=x^*A^*Ax=(Ax)^*(Ax)=(\lambda x)^*(\lambda x)=\overline{\lambda}\lambda x^*x=|\lambda|^2x^*x.$$Divide $x^*x$ from both sides to get $|\lambda|^2=1$, or $|\lambda|=1$.
using LinearAlgebra
n = 5
Q, = qr(randn(n,n)) # Q stored in a clever factorized form
λ = eigvals(Matrix(Q))
abs.(λ)
5-element Array{Float64,1}:
1.0000000000000002
0.9999999999999994
0.9999999999999994
1.0000000000000007
1.0000000000000007
(10) The Tribonacci numbers are defined in analogy to the Fibonacci numbers: $T_1=T_2=0$, $\ T_3=1$, $T_n=T_{n-1}+T_{n-2}+T_{n-3}$ (for $n>3$)
# Inefficient but straightforward computation
T(n) = n>3 ? T(n-1)+T(n-2)+T(n-3) : n==3 ? 1 : 0
[T(n) for n=1:15]'
1×15 Adjoint{Int64,Array{Int64,1}}:
0 0 1 1 2 4 7 13 24 44 81 149 274 504 927
(Not required: but if you want to understand the Julia it says if n>3, use the recurrence, if n=3 return 1, otherwise 0)
Let $u_k = \begin{pmatrix} T_{k+2} \\ T_{k+1} \\ T_k \end{pmatrix}$. Find a matrix A that relates $u_{k+1}$ to $u_k$
A = [ 1 1 1; 1 0 0; 0 1 0]
3×3 Array{Int64,2}:
1 1 1
1 0 0
0 1 0
Verify numerically that the largest eigenvalue of $A$ is
ϕ = (1+∛(19+3*√33)+∛(19-3*√33))/3
1.8392867552141612
eigvals(A)
3-element Array{Complex{Float64},1}:
1.839286755214161 + 0.0im
-0.41964337760708065 + 0.6062907292071997im
-0.41964337760708065 - 0.6062907292071997im
and the other two eigenvalues have absolute value less than 1.
abs.(eigvals(A))
3-element Array{Float64,1}:
1.839286755214161
0.7373527057603281
0.7373527057603281
Explain why T(31)/T(30) should be about ϕ
T(31)/T(30)
1.839286755221798
(May be interesting to compare last year's solution) Solution: First, notice that
$$u_{k+1}=A^ku_1=A^k\begin{pmatrix}1\\0\\0\end{pmatrix}.$$Let $\alpha$ denote one of the eigenvalues of $A$ that is not $\varphi$. The third eigenvalue is then $\overline{\alpha}$. Let $v_{\varphi}$, $v_{\alpha}$, and $v_{\overline{\alpha}}$ be any chosen eigenvectors for $\varphi$, $\alpha$, and $\overline{\alpha}$ respectively. Because the three eigenvalues of $A$ are distinct, these eigenvectors must be linearly independent. Therefore, for some complex numbers $c_1,c_2,c_3$, we have
$$\begin{pmatrix}1\\0\\0\end{pmatrix}=c_1v_{\varphi}+c_2v_{\alpha}+c_3v_{\overline{\alpha}}.$$Now,
$$u_{k+1}=A^k\begin{pmatrix}1\\0\\0\end{pmatrix}=\varphi^k(c_1v_{\varphi})+\alpha^k(c_2v_{\alpha})+\overline{\alpha}^k(c_3v_{\overline{\alpha}})$$.
Because we saw that $|\alpha|<1$, we know $\alpha^k$ and $\overline{\alpha}^k$ get smaller and smaller as $k$ increases. On the other hand, the vector $u_k$ gets larger and larger. This means that $c_1 \neq 0$. So, for large $k$, we have an approximation
$$u_{k+1} \approx \varphi^k(c_1v_{\varphi}),$$and looking at the entries in $u_{k+1}$ tells us that $T(k+1) \approx \varphi T(k)$. In the above Julia output, it looks like this is already a good approximation for $k=30$.
Using Julia, expand u₁ in an eigenvector basis obtaining the coefficients c. (Two of which are complex, and one may have roundoff as an imaginary part.)
Λ,X = eigen(A) # Λ is a vector of eigenvalues in Julia for efficiency
c = X\[1,0,0] # Solve Xc = [1,0,0]
3-element Array{Complex{Float64},1}:
-0.7272617676223453 + 2.4480415638808602e-17im
-0.12395935590945975 + 0.4618502490960845im
-0.12395935590945978 - 0.46185024909608463im
real(c[1]*X[1,1]*ϕ^15),T(18)
(5767.998305699344, 5768)
A student wishes to approximate the 18th Tribonacci number. Explain why the above expression is correct, including the role played by c[1], X[1,1], 15, and 18.
Solution: Looking at the first entries of both sides of the approximation
$$u_{k+1} \approx \varphi^k c_1 v_{\varphi}$$with $k=15$, we get
$$T(18) \approx \varphi^{15} c_1 (v_{\varphi})_1.$$In the Julia code, c[1] is the number $c_1$, X[1,1] is the number $(v_{\varphi})_1$, $15=k$, and $18=(k+1)+2$.
T(18) - real(c[1]*X[1,1]*ϕ^15) # error
0.0016943006557994522
2 * real(c[2]*X[1,2]*Λ[2]^15 )
0.0016943006593527162
The above formula is the exact error to the student's approximation. Explain.
Solution: The full equation from which we got our approximation was
$$u_{k+1}=\varphi^k(c_1v_{\varphi})+\alpha^k(c_2v_{\alpha})+\overline{\alpha}^k(c_3v_{\overline{\alpha}})$$.
The error is therefore
$$u_{k+1}-\varphi^k(c_1v_{\varphi})=\alpha^k(c_2v_{\alpha})+\overline{\alpha}^k(c_3v_{\overline{\alpha}})$$.
Now, notice that the entries of $v_{\overline{\alpha}}$ could have been chosen to be the complex conjugates of the entries of $v_{\alpha}$ (to see this, take complex conjugates of both sides of $Av_{\alpha}=\alpha v_{\alpha}$). Now, because the entries of $u_{k+1}$ are real, this forces $c_3=\overline{c_2}$. Taking the first entry in the above equation and putting this all together, we have
$$T(18)-\varphi^{15}c_1(v_{\varphi})_1=\alpha^{15} c_2 (v_\alpha)_1+\overline{\alpha}^{15} \overline{c_2} \overline{(v_\alpha)_1}=\alpha^{15} c_2 (v_\alpha)_1+\overline{\alpha^{15} c_2 (v_\alpha)_1}=2\operatorname{Re}(\alpha^{15} c_2 (v_\alpha)_1),$$where $\operatorname{Re}$ means take the real part. In the Julia code, c[2] is the number $c_2$, X[1,2] is the number $(v_\alpha)_1$, and Λ[2] is $\alpha$.