Pset 8: Due Thursday April 30
(1.) (a) Find the eigenvalues and eigenvectors of$$ A = \begin{pmatrix} 1 & 4 \\ 2 & 3 \end{pmatrix}, \qquad A + 2I = \begin{pmatrix} 3 & 4 \\ 2 & 5 \end{pmatrix} $$
(b) If $Ax=\lambda x$, then what is $(A+\alpha I)x$? Therefore, how are the eigenvalues and eigenvectors of $A+\alpha I$ related to those of $A$? Is this consistent with your answer from (a)?
$\bf{\mbox{Ans}}$:(a) $det(A-\lambda I)=det\begin{pmatrix}1-\lambda& 4\\2&3-\lambda\end{pmatrix}=\lambda^2-4 \lambda-5$. Set $det(A-\lambda I)=0$, we get $\lambda=-1$ or 5.
For the eigenvalue $\lambda=-1$, a eigenvector $u_1$ satisfies $\begin{pmatrix}2&4\\2&4\end{pmatrix}x_1=0$. We choose $x_1=\begin{pmatrix}2\\-1\end{pmatrix}$.
For the eigenvalue $\lambda=5$, a eigenvector $u_2$ satisfies $\begin{pmatrix}-4&4\\2&-2\end{pmatrix}x_2=0$. we choose $x_2=\begin{pmatrix}1\\1\end{pmatrix}$.
$A+2I$ has eigenvalues $1$ and $7$ and the corresponding eigenvectors are $x_1$ and $x_2$.
(b) $(A+\alpha I)x=(\lambda +\alpha)x$.
The eigenvalues of $(A+\alpha I)$ are eigenvalues of $A$ plus $\alpha$.
The eigenvectors of $(A+\alpha I)$ are the sames as the eigenvectors of $A$.
This is consistent with (a).
(2) (From Strang, section 6.1, problem 11.)
Here is a strange fact about 2×2 matrices with eigenvalues $\lambda_1 \ne \lambda_2$: the columns of $A - \lambda_1 I$ are multiples of the eigenvector $x_2$. Why?
(Hint: think about the column and null spaces of $A - \lambda_1 I$.)
$\bf{\mbox{Ans}}:$ We have $(A-\lambda_1 I)x_2= (\lambda_2-\lambda_1)x_2$. Note that the column space of $A-\lambda_1 I$ is 1 dimensional and $(\lambda_2-\lambda_1)x_2\in col(A-\lambda_1 I)$. Thus each column of $A-\lambda_1 I$ is a multiple of $x_2$.
(3) (Based on Strang, section 6.2, problem 9.)
Suppose we form the sequence
$$ g_0,g_1,g_2,g_3,\ldots = 0, 1, \frac{1}{2}, \frac{3}{4}, \frac{5}{8}, \frac{11}{16}, \frac{21}{32}, \frac{43}{64}, \frac{85}{128}, \frac{171}{256}, \frac{341}{512}, \frac{683}{1024}, \frac{1365}{2048}, \frac{2731}{4096}, \frac{5461}{8192}, \frac{10923}{16384}, \frac{21845}{32768}, \ldots $$by the rule that $g_{k+2} = \frac{g_{k+1} + g_k}{2}$: each number is the average of the previous two.
(a) If we define $x_k = \begin{pmatrix} g_{k+1} \\ g_k \end{pmatrix}$, then write the rule for the sequence in matrix form: $x_{k+1} = A x_k$. What is $A$?
(b) Find the eigenvalues and eigenvectors of A.
(c) The eigenvalues immediately tell which of these three possibilities: the sequence blows up, decays, or goes to a constant as $n\to\infty$? Does this behavior depend on the starting vector $x_0$?
(d) Find the limit as $n\to\infty$ of $A^n$ from the diagonalization of $A$.
(e) If $g_0 = 0$ and $g_1 = 1$, i.e. $x_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$, then show that the sequence approaches 2/3.
(f) With $g_0 = 0$ and $g_1 = 1$ as in the previous part, how fast does $g_n - 2/3$ go to zero? In particular, what should $\frac{g_{n+1} - 2/3}{g_n - 2/3}$ approach for large $n$? Optionally heck your answer by the using the following Julia code, which numerically computes the sequence.
function gsequence(n)
g = [0.0, 1.0]
for i = 3:n
push!(g, (g[end]+g[end-1])/2)
end
return g
end
gsequence(25);
gsequence(25) .- 2/3;
$\bf{\mbox{Ans}}:$ (a) $\begin{pmatrix}1/2&1/2\\1&0\end{pmatrix}$.
(b) Eigenvalues are 1 and $-1/2$. An eigenvector for $\lambda=1$ is $x_1=\begin{pmatrix}1\\1\end{pmatrix}$. An eigenvector for $\lambda=-1/2$ is $x_2=\begin{pmatrix}-1\\2\end{pmatrix}$.
(c) The sequense goes to a constant as $n\to \infty$. It does not depend on the initial value.
(d) Note $A=U\Sigma U^{-1}$, where $\Sigma=\begin{pmatrix}1&0\\0&-1/2\end{pmatrix}$ and $u=(x_1,x_2)$. We have $\lim_{n\to \infty}A^n=\lim_{n\to \infty} (U\Sigma U^{-1})^n=\lim_{n\to \infty} U\Sigma^n U^{-1}=$ $ \begin{pmatrix}1& -1\\ 1&2 \end{pmatrix} \begin{pmatrix}1& 0\\ 0&0 \end{pmatrix} \begin{pmatrix}2&1\\ -1&1\end{pmatrix}\frac{1}{3}=\frac{1}{3}\begin{pmatrix}2& 1\\ 2&1 \end{pmatrix}$.
(e) As $\lim_{n\to \infty}A^n x_0= \begin{pmatrix}2/3\\2/3\end{pmatrix}$, we have $\lim_{n\to \infty}g_k=2/3$.
(f) As $\begin{pmatrix}1\\0\end{pmatrix}=\frac{2}{3}\begin{pmatrix}1\\1\end{pmatrix}-\frac{1}{3}\begin{pmatrix}-1\\2\end{pmatrix}$, we know $\begin{pmatrix}g_{n+1}\\g_n\end{pmatrix}=A^n \begin{pmatrix}1\\0\end{pmatrix}=\frac{2}{3}\begin{pmatrix}1\\1\end{pmatrix}-\frac{1}{3}(-\frac{1}{2})^n\begin{pmatrix}-1\\2\end{pmatrix}$. Therefore $\displaystyle{\frac{g_{n+1}-2/3}{g_n-2/3}= -\frac{1}{2}}$.
(4) If $M$ is an $m\times m$ Markov matrix with positive entries, consider the system of ODEs$$\frac{dx}{dt} = (M-I)x$$.
(a) Explain why the sum of the components of $x(t)$ is "conserved": that is, $o^T x(t)$ is the same number for all $t$, where $o$ is the vector of $m$ 1's.
(b) What do the eigenvalues of $M$ (positive Markov: one λ=1 eigenvalue and the remainder have $|\lambda|\lt 1$) tell you about the solution $x(t)$ for large $t$? Does it blow up, oscillate, decay to zero, or … ?
(c) Given the initial condition $x(0)$, give a formula for the solution $x(\infty) = \lim_{t\to\infty} x(t)$ in terms of $x(0)$, $o$, and the "steady-state" eigenvector $v_0$ ($M v_0 = v_0$) of $M$.
(d) Optionally Check your answers to (a) and (c) by using the following Julia code to generate a random 5×5 positive Markov matrix, a random initial condition, and evaluating $x(t)=e^{(M-I)t} x(0)$ via exp((M-I)t)x₀ for one or more values of t in Julia.
$\bf{\mbox{Ans}}:$ (a) $\displaystyle{\frac{d}{dt}o^T x = o^T \frac{dx}{dt}= o^T (M-I)x= ((M-I)^T o)^T x=0.}$ The last equation is because the sum of each column of $M-I$ is 0. Therefore $o^Tx(t)$ is a constant.
(b) $x(t)$ goes to a constant since one eigenvalue is $0$ and all the other eigenvalues of $M-I$ are negative.
(c) It is known that the only vector that contributes the the steady-state is the eigenvector of $M-I$ for $0$ eigenvalue, which is $v_0$. I.e. $x(\infty)=a_0 v_0$ where $a_0$ is a constant.
This can be understand when $M-I$ is diaonalizable. Supose $x(0)=a_0v_0+a_1v_1+\cdots a_{m-1}v_{m-1}$, where $a_i$ are numbers and $v_i$ are eigenvectors of $M-I$ for eigenvalues $0, \lambda_1, \cdots \lambda_{m-1}$. In particular, $Mv_0=v_0$. Then $x(\infty)=\lim_{n\to \infty} e^{(M-I)t}x(0)=\lim_{n\to \infty} a_0v_0+ a_1 e^{\lambda_1}v_1+\cdots a_{m-1}e^{\lambda_{m-1}}v_{m-1}=a_0v_0$.
By part (a), we know that $o^T(a_0v_0)=o^Tx(0)$, which implies $a_0=\displaystyle{\frac{o^Tx(0)}{o^Tv_0}}$. Hence we have $x(\infty)=\displaystyle{\frac{o^Tx(0)}{o^Tv_0} v_0}$.
(d) Julia code as below.
# generate a random 5×5 Markov matrix
M = rand(5,5)
M = M ./ sum(M,dims=1)
5×5 Array{Float64,2}:
0.185064 0.163531 0.216239 0.199078 0.185472
0.100901 0.140709 0.16902 0.111907 0.211666
0.295306 0.106829 0.217277 0.482829 0.197706
0.103092 0.15851 0.287594 0.0106187 0.227307
0.315637 0.43042 0.10987 0.195567 0.177849
using LinearAlgebra
v₀ = nullspace(M-I) # the λ=1 eigenvector of M
5×1 Array{Float64,2}:
0.4224202176432261
0.33297797141355534
0.5636251746168992
0.3763807065014143
0.5013492361529326
?nullspace; # Remove semicolon to read about nullspace
o = ones(size(v₀)) # the vector of 1's
5×1 Array{Float64,2}:
1.0
1.0
1.0
1.0
1.0
x₀ = randn(size(o)) # a random initial condition
5×1 Array{Float64,2}:
0.8854250021078691
2.9917147669203197
-0.06843156042186728
0.2260076379324639
-0.6424660553057497
t = 100
x = exp((M-I) * t) * x₀ # the solution x(t)
5×1 Array{Float64,2}:
0.6523057873567594
0.5141881206046452
0.8703559819030439
0.5812110851845147
0.7741888161841227
sum(x), sum(x₀) # compare the sums of the components of x(t) and x(0)
(3.392249791233086, 3.392249791233035)
((o'x₀)/(o'v₀)).*v₀
5×1 Array{Float64,2}:
0.6523057873567496
0.5141881206046378
0.8703559819030305
0.5812110851845063
0.7741888161841108
(5) Construct for every n=2,3,... a non-zero matrix A that has all eigenvalues 0, but has (n-1) singular values 1. Is A diagonalizible? (Possible Hint: Permuting the rows or columns of a matrix does not influence the singular values.)
$\bf{\mbox{Ans}}:$ Let $A_n= \begin{pmatrix} 0&1&0&\cdots &0\\ 0&0&1&\cdots &0\\ \vdots&\vdots &\vdots& \ddots&\vdots\\ 0&0&0&\cdots&1\\ 0&0&0&\cdots&0\\ \end{pmatrix} $ One can check that all the eigenvalues of $A$ are $0$.
$A_n$ has to following SVD. $ A_n=\begin{pmatrix} 0& 1 & 0& \cdots & 0\\ 0& 0 & 1& \cdots &0\\ \vdots& \vdots & \ddots & \ddots& \vdots\\ 0& 0& 0& \ddots & 1\\ 1& 0& 0& \cdots& 0 \end{pmatrix} \begin{pmatrix} 0& 0 & \cdots &0& 0\\ 0& 1& \cdots &0&0\\ \vdots&\vdots & \ddots& \vdots& \vdots\\ 0& 0& \cdots&1& 0\\ 0& 0& \cdots& 0& 1 \end{pmatrix}I_n.$ Thus $A$ has $n-1$ singular values being $1$.
$A_n$ is not diagonalizible. If it was diagnoalizable, say $A_n= U\Sigma U^{-1}$, then $A_nU=U\Sigma$. Since all the eigenvalues are $0$, all the columns of $U$ are eigenvectors for $\lambda=0$ and they are linear independent. However, the null space of $A_n-0I$ is one dimensional. Thus $A_n$ is not diagonalizible.
(6) Find two matrices (or argue that is impossible) for which $AB-BA=I$.
$\bf{\mbox{Ans}}:$ It is impossible since $tr(AB-BA)=tr(AB)-tr(BA)=0$ but $tr(I)\neq 0$.
(7) Use the full svd to derive the so called "polar factorization" of a matrix: Every square matrix $A$ can be factored into $QS$ where $Q$ is orthogonal and $S$ is positive semi-definite. If $A$ is invertible further show $S$ is positive definite. (Hint: if $A=U\Sigma V^T$, the orthogonal matrix $Q$ will be $UV^T$. What do we need to complete the story.) (Hint: if you don't yet see the answer, the polar decomposition is on page 394 of Strang.)
$\bf{\mbox{Ans}}:$ Write down a full svd $A=U\Sigma V^T$ such that all the entries of $\Sigma$ are non-negative. If any entry is negative, one can move the negative sign to the corresponding column of U. Then $A=(UV^T)(V\Sigma V^T)$. Let $Q=UV^T$ ( which is orthogonal) and $S=V\Sigma V^T$ (which is positive semi-definite). Thus we get the polar factorization.
If A is invertible, we know all the diagonal entries of $\Sigma$ are positive and thus $S$ is positive definite.
(8) Suppose $x\in R^n$ is constant and $A$ is nxn variable. Find the gradient $\nabla_A$ of sum( sin.(Ax) ). The answer can be expressed as an nxn matrix or a linear transformation.
$\bf{\mbox{Ans}}:$ $\nabla_A$sum( sin.(Ax) )=cos.(Ax)x^T