Finding the Eigenvalues of a Matrix

Upper Triangular Matrix

A ~k # ~k matrix B = (~b_{~i ~j })_{~i , ~j = 1 ... ~k} _ is #{~{ upper triangular}} _ if _ ~b_{~i ~j } = 0 _ whenever _ ~i > ~j .

 

Similarity to Upper Triangular

For any ~n # ~n matrix A , _ &exist. a ( ~n # ~n ) unitary matrix U ( U* = U^{&minus.1} ), such that _ U^{&minus.1}AU _ ( = U*AU ) _ is upper triangular. _ Furthermore the elements of the diagonal of U^{&minus.1}AU are eigenvalues of A.

Proof:
By induction on ~n. When ~n = 1 , A = (~a) is upper triangular, A#{~v} = a#{~v} for any one-dimensional vector #{~v} &in. F^1 , _ #{~v} = (~v).
Suppose true for ~n = ~k, _ i.e. for ~k # ~k matrix B &exist. unitary V, such that V^{&minus.1}BV = X is upper triangular and the diagonal elements of X are the eigenvalues of B.
Consider for (~k+1) # (~k+1) matrix A. Let λ be an eigenvalue of A with corresponding eigenvector #{&xi.}. _ Assume _ || #{&xi.} || _ = 1. _ Construct an orthonormal basis for F^{~k+1} , _ #{&xi.}, #{&eta.}_1, ... #{&eta.}_{~k} , _ and set _ U_1 = (#{&xi.} #{&eta.}_1 ... #{&eta.}_{~k} ) . _ This is unitary, since the columns are orthonormal by construction. Now

U_1^{&minus.1} A U_1 _ = _ matrix{λ,~r_1, ... ,~r_{~k}/0,,,/:,,B,/0,,,}

[ First column is _ U_1^{&minus.1} A #{&xi.} _ = _ U_1^{&minus.1} λ #{&xi.} _ = _ λ U_1^{&minus.1} #{&xi.} _ = λ #{e}_1 _ ].
where B is ~k # ~k , _ so &exist., V such that _ V^{&minus.1}BV = X _ is upper triangular. Let
_

U_2 _ = _ matrix{1,0, ... ,0/0,,,/:,,V,/0,,,}

Then U_2 is unitary

U_2* U_2 _ = _ matrix{1,#0^T/#0,V*}matrix{1,#0^T/#0,V} _ = _ matrix{1,#0^T/#0,V*V} _ = _ matrix{1,#0^T/#0,I_{~k}} _ = _ I_{~k+1}

Now Put _ U = U_1U_2 , _ U is unitary since it is a product of unitary matrices, we have

U^{&minus.1} A U _ = _ U_2^{&minus.1}U_1^{&minus.1} A U_1U_2

_ = _ matrix{1,#0^T/#0,V*}matrix{λ,#{~r}^T/#0,B}matrix{1,#0^T/#0,V} _ = _ matrix{1,#0^T/#0,V*} matrix{λ,#{~r}^TV/#0,BV}

_ = _ matrix{λ,#{~r}^TV/#0,V*BV} _ = _ matrix{λ,#{~r}^TV/#0,X} _ _ which is upper triangular.

Furthermore if λ_2 is on the principal diagonal of X, then it is an eigenvalue of B, by the inductive hypothesis, _ B#{&xi.} = λ_2#{&xi.} , _ some ~k-dimensional vector {&xi.}.
Now λ_2 is also an eigenvalue of A: _ put _ &mu. = #{~r}^T#{&xi.}_2 / ( λ_2 &minus. λ ) _ and consider the vector (&mu., #{&xi.}_2)^T

U^{&minus.1}AU matrix{&mu./#{&xi.}_2} _ = _ matrix{λ,#{~r}^T/#0,B}matrix{&mu./ #{&xi.}_2} _ = _ matrix{λ&mu.+#{~r}^T#{&xi.}_2/B#{&xi.}_2}

_ = _ matrix{λ_2&mu./λ_2#{&xi.}_2} _ = _ λ_2 matrix{&mu./#{&xi.}_2}

λ_2 is an eigenvalue of A (since A &tilde. to U^{&minus.1}AU both correspond to same linear map). This completes the inductive step.

---