18.06 Spring2019 pset 9

due Friday 4/26 at 11:59pm

Moving to Friday night seems to be very popular so this and pset 10 will be Friday night sets, but please do not wait until Friday to start.

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

(1b) If $A=X \Lambda X^{-1}$ then $A^3=( \ )( \ )( \ )$ and $A^{-1}=( \ )( \ )( \ )$.

(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

Λ,X = eigen(A^3)
display(Λ)  
display(X)

Λ,X = eigen(inv(A))
display(Λ)  
display(X)

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

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

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

howmany = 20  
n = 4 
for i = 1:howmany
    display(eigvals(randn(n,n))) 
end

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

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

(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

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

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

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?

5. Supose rank(A) = n-1 and x is an eigenvector with eigenvalue 0. How might the information in x find itself inside the SVD?

6. 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.)

7. (Finally doing what was avoided all year!) Write an expression for $A^TA$ in terms of the svd of A. Use this to relate the singular values of $A$ to the eigenvalues of $A^TA$. Do the same for $AA^T$.

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.

8. Find two matrices (or argue that is impossible) for which $AB-BA=I$.

9. We recall that for complex numbers, the absolute value, $|z|$ is the sqrt of the real part squared plus the imaginary part.

Find a pattern (as an experimentalist, without proof) for the absolute values of eigenvalues of orthognal matrices.

using LinearAlgebra
n = 5
Q, = qr(randn(n,n))  # Q stored in a clever factorized form
λ = eigvals(Matrix(Q))
abs.(λ)

(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]'

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

M = [ 1 2 3; 4 5 6; 7 8 9] # Template for a 3x3 matrix
A =                        # Write the correct numbers

Verify numerically that the largest eigenvalue of $A$ is

ϕ = (1+∛(19+3*√33)+∛(19-3*√33))/3

1.8392867552141612

and the other two eigenvalues have absolute value less than 1.

abs.(eigvals(A))

Explain why T(31)/T(30) should be about ϕ

T(31)/T(30)

1.839286755221798

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]

real(c[1]*X[1,1]*ϕ^15),T(18)

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.

T(18) - real(c[1]*X[1,1]*ϕ^15) # error

2 * real(c[2]*X[1,2]*Λ[2]^15 )

The above formula is the exact error to the student's approximation. Explain.