Lecture 16-20

Least square solution

Let V be an inner product space and let W ⊆ V be a subspace. Let {w1 , . . . , wr } be an orthonormal
basis of W . Then recall that for every v ∈ V ,
r
X
PW (v) = ⟨v, wi ⟩ wi
i=1

has the shortest distance from v (among all vectors in W ).

Now consider A ∈ Mm,n (F ), and we need also the standard inner product on Mm,1 (F ).

Q: Given v ∈ Mm,1 (F ), find w0 ∈ Mn,1 (F ) called least square solution, such that

∥Aw0 − v∥ is minimum.

(We have to take W = Col(A).)

A projection approach

We may try to find an orthonormal basis of Col(A) using Gram–Schmidt orthonormalisation and
use the above formula computing PCol(A) (v). Now we can solve the equation

Aw0 = PCol(A) (v)

to find w0 .
This discussion shows such a w0 always exists. However it need not be unique. Moreover, one
may use the following more efficient method, which requires fewer steps.

Normal equations

Let v ∈ Mm,1 (F ) and W = Col(A). Recall

Mm,1 (F ) = Col(A) ⊕ N (AT ).

Hence,
where v − PCol(A) (v) ∈ N (AT ).


v = PCol(A) (v) + v − PCol(A) (v) ,

Therefore,
AT v − PC(A) (v) = 0.

If w0 satisfies Aw0 = PCol(A) (v), then

AT (v − Aw0 ) = 0,

so we get the normal equations

AT A w0 = AT v .

This is a linear equation we need to solve.

1
Suppose we satisfy AT Aw0 = AT v. Then

AT (Aw0 − v) = 0 =⇒ Aw0 − v ∈ N (AT ),

and also Aw0 ∈ C(A). Hence

v = Aw0 + (v − Aw0 )

is the decomposition of v into a vector in Col(A) plus a vector in N (AT ). Comparing with


v = PCol(A) (v) + v − PCol(A) (v) ,

and using the property of direct sum, we get

Aw0 = PCol(A) (v).

We have proved:

AT Aw0 = AT v iff w0 is the least square soln of Aw = v .

Example 1: A 2 × 2 matrix

Let ! !
1 1 1
A= , v= .
1 1 0
We wish to find w0 ∈ R2 such that ∥Aw0 − v∥ is minimal.

The columns of A are identical, hence

( !)
1
Col(A) = span .
1

An orthonormal basis of Col(A) is !

1 1
u= √ .
2 1
The projection of v onto Col(A) is
!
1 1
PCol(A) (v) = ⟨v, u⟩u = .
2 1

To find a least-squares solution, we solve

! ! !
1 1 x 1 1
Aw0 = PCol(A) (v), i.e. = .
1 1 y 2 1

This gives the single equation

1
x+y = ,
2
so there are infinitely many least-squares solutions. One choice is
!
1
2
w0 = .
0

2
Normal equations. We compute
! !
2 2 1
AT A = , AT v = .
2 2 1

The normal equations

AT Aw0 = AT v

reduce again to
1
x+y = ,
2
which agrees with the projection approach.

Example 2: A 3 × 3 matrix

Let    
1 0 0 1
   
A=
0 1 0  ,
 v=
1 .

1 1 0 0
The columns of A are      
1 0 0
     
c1 = 
0 ,
 c2 = 
1 ,
 c3 = 
0 ,

1 1 0
so
Col(A) = span{c1 , c2 }.

Normal equations. We compute

   
2 1 0 1
T T
   
A A = 1 2 0 

, A v = 1

.
0 0 0 0

Thus the normal equations

AT Aw0 = AT v

give 


2x + y = 1,

x + 2y = 1,



0 = 0.

Solving, we obtain
1
x=y= , z free.
3
A least-squares solution is therefore  
1
3
w0 =  13  .
 
 
0

3
Verification via projection. We compute
 
1
3
Aw0 =  1
3 .
2
3

Then  
2
3
 ∈ N (AT ),
 
v − Aw0 =  2
 3 
− 23
and hence
Aw0 = PCol(A) (v),

confirming that w0 is a least-squares solution of Aw = v.

Least square fitting

We want to find a line y = ax + b (equivalently y = bx + a) so that the sum of squared vertical

errors is minimum, i.e. we want to find a, b such that
n
X
ℓi2 is minimum.
i=1

y
ℓi = (axi + b) − yi is the vertical distance to the line
y = ax + b
(x3 , y3 )
(x1 , y1 )

ℓ1
(xn , yn )
(x2 , y2 )

That is,
n
X
i.e. | axi + b − yi |2 is minimum.
i=1

Equivalently,
i.e. ∥Ax − b∥2 is minimum,

where   
1 x1 y1 " #
. .  . b
. .  .
. .  ,
A=  . ,
b= x=
a
.
1 xn yn
Find x?

Soln: Use the least square soln method to find x.

4
Explicit example: least square line fitting

Consider the data points

(1, 2), (2, 2), (3, 4).

We want to find the line

y = ax + b

that minimizes the sum of squared vertical errors

3
X 3
X
ℓ2i = | axi + b − yi |2 .
i=1 i=1

Step 1: We write the problem in the form ∥Ax − b∥2 where

   
1 1 2 " #
    b
A= 1 2 ,
 b= 2 ,
 x= .
a
1 3 4

Step 2: Normal equations. We compute

" # " #
3 6 8
AT A = , AT b = .
6 14 18

Thus the normal equations

AT Ax = AT b

become " #" # " #

3 6 b 8
= .
6 14 a 18

Step 3: Solving, 
3b + 6a = 8,
6b + 14a = 18.

Subtracting 2× the first equation from the second gives

2a = 2 ⇒ a = 1.

Substituting back,
2
3b + 6 = 8 ⇒ b= .
3
Least squares solution. The best-fit line is

2
y =x+ .
3

Step 4: Interpretation. The vector  

5
3
Ax = 8
3
11
3

5
is the orthogonal projection of b onto Col(A), and the residual
 
1
3
T
 
b − Ax =  2
− 3  ∈ N (A ).
1
3

Hence the normal equations guarantee that the vertical errors are minimized.

Eigenvalues and Eigenvectors

Motivation: solving linear systems via diagonalization

Let A ∈ Mn×n (F ) and B ∈ Mn×1 (F ). Consider the system of equations

AX = B.

If A is of the form  
λ1 0 · · · 0  

 0 λ2 · · ·
 b1
0  .
and B =  .
A= . .. . . ..  . ,
 
 .. .

. . 
  bn
0 0 ··· λn
then the system is diagonal and we can solve it componentwise:

λi xi = bi (i = 1, . . . , n).
bi
Hence, if λi ̸= 0, then xi = ; and if λi = 0, then a solution exists only if bi = 0, in which case xi
λi
can be any element of F .
Such matrices are called diagonal matrices. Even if A is not diagonal, sometimes there exists
an invertible matrix P such that
P −1 AP = D,

where D is diagonal. Equivalently,

A = P DP −1 .

In that case we can reduce AX = B to a diagonal system:

AX = B ⇐⇒ P DP −1 X = B.

Multiplying on the left by P −1 gives

DP −1 X = P −1 B.

Let Y = P −1 X and C = P −1 B. Then the system becomes

DY = C,

which is diagonal, i.e. it splits into independent scalar equations λi yi = ci . After solving for Y , we
recover
X = P Y.

Thus diagonalization turns a coupled system into a decoupled one.

6
Definition 1 (Diagonalizable matrix). A matrix A ∈ Mn (F ) is called diagonalizable if there
exists an invertible matrix P such that P −1 AP is diagonal.

Next we introduce the notion of eigenvalues and eigenvectors, which plays an important role in
the process of diagonalization.

Definition 2 (Eigenvector and eigenvalue). Let A ∈ Mn (F ). A non-zero vector v ∈ Mn,1 (F ) is

called an eigenvector of A if there exists a scalar λ ∈ F such that

Av = λv.

The scalar λ is called an eigenvalue of A.

• (Geometric meaning, when F = R) The vectors v and Av lie on the same line through the
origin.

• (Algebraic meaning) Av = λv is equivalent to (A − λIn )v = 0, i.e.

v ∈ Null(A − λIn ) and v ̸= 0.

Finding eigenvalues

Note that λ is an eigenvalue of A if and only if

Null(A − λIn ) ̸= {0} ⇐⇒ det(A − λIn ) = 0,

which is a polynomial equation in λ of degree n.

Definition 3 (Characteristic polynomial). Let A ∈ Mn (F ). The polynomial

χA (x) := det(A − xIn )

is called the characteristic polynomial of A.

• The eigenvalues of A are precisely the roots of χA (x) in F .

Eigenspaces

Definition 4 (Eigenspace). Let λ ∈ F . The subspace

Null(A − λIn )

is called the eigenspace of λ (for the matrix A), denoted by WA (λ).

• Note: λ ∈ F is an eigenvalue if and only if WA (λ) ̸= {0}.

7
Examples

(1) If A = In , then 1 ∈ F is the only eigenvalue of A, and every non-zero vector in Mn,1 (F ) is an
eigenvector corresponding to 1. In this case,

χIn (x) = (1 − x)n .

(2) If A = 0 (the zero matrix), then 0 ∈ F is the only eigenvalue, and

χA (x) = (−x)n .

(3) Let " #

1 0
D= .
0 2
Then
χD (x) = (1 − x)(2 − x),

so the eigenvalues are 1 and 2. Moreover,

(" #) (" #)
1 0
WD (1) = span , WD (2) = span .
0 1

Non-zero vectors in WD (λ) are eigenvectors corresponding to λ (for λ = 1, 2).

(4) Let " #

0 −1
A= ∈ M2 (R).
1 0
Then " #
−x −1
χA (x) = det = x2 + 1,
1 −x
so A has no real eigenvalues. However, if we consider A ∈ M2 (C), then the eigenvalues are i
and −i, where i2 = −1 (we will compute the eigenvectors as well).

(5) Let " #

0 1
A= .
0 0
Then
χA (x) = x2 ,

so the only eigenvalue is 0.

Since nullity(A) = 1, we have dim WA (0) = 1 and
(" #)
1
WA (0) = span .
0

(6) If A is a diagonal matrix with diagonal entries λ1 , λ2 , . . . , λn , then λ1 , . . . , λn are eigenvalues

of A (note that they need not be distinct).

(7) (Exercise) Let A be an upper triangular matrix with diagonal entries a11 , a22 , . . . , ann . Then
the eigenvalues of A are a11 , a22 , . . . , ann .

8
Algebraic and Geometric Multiplicity and Diagonalization

Let A be an n × n matrix and λ an eigenvalue of A.

Algebraic Multiplicity

The algebraic multiplicity (AM) of λ is the number of times λ appears as a root of the charac-
teristic polynomial
det(A − λI).

Geometric Multiplicity

The geometric multiplicity (GM) of λ is the dimension of its eigenspace:

GM(λ) = dim ker(A − λI),

that is, the number of linearly independent eigenvectors corresponding to λ.

Fundamental Inequality

For every eigenvalue λ,

1 ≤ GM(λ) ≤ AM(λ).

Proof. (Optional reading)

Let LA : Fn → Fn be the linear transformation

LA (x) = Ax.

Step 1: 1 ≤ GM(λ).
If λ is an eigenvalue, then there exists v ̸= 0 such that

LA (v) = λv,

i.e.
(LA − λI)(v) = 0.

Thus ker(LA − λI) ̸= {0}, so

GM(λ) = dim ker(LA − λI) ≥ 1.

Step 2: GM(λ) ≤ AM(λ).

Let
g = dim ker(LA − λI).

Choose a basis
B = {v1 , . . . , vg , vg+1 , . . . , vn }

of Fn such that
{v1 , . . . , vg }

9
is a basis of ker(LA − λI).
Since LA (vi ) = λvi for 1 ≤ i ≤ g, the subspace

W = ker(LA − λI)

is LA –invariant.

If P is the change–of–basis matrix whose columns are the vectors v1 , . . . , vn , then the matrix of
LA in the basis B is
[LA ]B = P −1 AP.

Because LA acts as multiplication by λ on W , the matrix takes block upper–triangular form:

!
λIg ∗
[LA ]B = ,
0 B

where B is an (n − g) × (n − g) matrix.

The characteristic polynomial of LA is

χA (t) = det(tI − A).

Since similar matrices have the same determinant,

χA (t) = det tI − [LA ]B .

Using the block form, !

(t − λ)Ig ∗
tI − [LA ]B = .
0 tI − B
The determinant of a block upper–triangular matrix equals the product of determinants of diag-
onal blocks, hence

χA (t) = det((t − λ)Ig ) det(tI − B) = (t − λ)g det(tI − B).

Thus (t − λ)g divides χA (t), which implies

AM(λ) ≥ g = GM(λ).

Combining both parts,

1 ≤ GM(λ) ≤ AM(λ).

Example

Consider !
2 1
A= .
0 2
The characteristic polynomial is

det(A − λI) = (2 − λ)2 ,

10
so λ = 2 has algebraic multiplicity AM = 2.
Solving (A − 2I)x = 0 gives !
0 1
x = 0,
0 0
which yields only one linearly independent eigenvector. Hence,

GM = 1.

Relation to Diagonalization

A matrix A is diagonalizable if and only if, for every eigenvalue λ,

GM(λ) = AM(λ).

Equivalently, A is diagonalizable if it has n linearly independent eigenvectors.

In the example above, since GM(2) < AM(2), the matrix A is not diagonalizable.

Summary

• Algebraic multiplicity counts how many times an eigenvalue appears.

• Geometric multiplicity counts how many independent eigenvectors it has.

• A matrix is diagonalizable exactly when these two quantities agree for every eigenvalue.

A fact from algebra

Fact. A degree n polynomial over C has n roots (counted with multiplicity). Hence, if A ∈ Mn (R)
or A ∈ Mn (C), then A has n eigenvalues in C (counted with multiplicity).

Multiplicity example

Example. Let
χA (x) = (x − 1)2 (x − 2)(x − 3).

Then we say A has 4 eigenvalues 1, 1, 2, 3, with algebraic multiplicity of 1 equal to 2, and algebraic
multiplicity of 2 and 3 equal to 1 each.

Similarity, Triangularization, and Diagonalization

Triangularization over C

Let F = C. Let A ∈ Mn (C) and let V = Mn,1 (C).

Theorem 1 (Triangularization Theorem). For every matrix A ∈ Mn (C), there exists an invertible
matrix P ∈ Mn (C) such that
P −1 AP

is an upper triangular matrix.

11
Proof. Let λ1 be an eigenvalue of A. (Note that eigenvalues of A are precisely the roots of the
characteristic polynomial charA (x), and over C all roots exist.)
Choose a nonzero vector
v1 ∈ WA (λ1 ),

so that
Av1 = λ1 v1 .

Extend {v1 } to a basis

B1 = {v1 , v2 , . . . , vn }

of Mn,1 (C).
Let
P = [v1 v2 · · · vn ] ∈ Mn (C).

Then
P −1 AP (e1 ) = P −1 Av1 = P −1 (λ1 v1 ) = λ1 e1 .

Hence  
λ1 ∗ · · · ∗
 
0 
−1
P AP =  . ,
 
 .. A1 
 
0
where A1 ∈ Mn−1 (C).
By the induction hypothesis, there exists Q ∈ Mn−1 (C) invertible such that

Q−1 A1 Q

is upper triangular.
Define !
1 0
Q1 = .
0 Q
Then
Q−1
1 P
−1
AP Q1

is upper triangular. This completes the proof.

0.1 Similar Matrices

Definition 5 (Similarity). Two matrices A, B ∈ Mn (F) are said to be similar if there exists an
invertible matrix P ∈ Mn (F) such that

P −1 AP = B.

Similarity defines a relation ∼ on Mn (F) by

A ∼ B ⇐⇒ A is similar to B.

Theorem 2. Similarity is an equivalence relation on Mn (F).

12
Proof. • Reflexive: A = I −1 AI.

• Symmetric: If P −1 AP = B, then A = P BP −1 .

• Transitive: If A ∼ B and B ∼ C, then A ∼ C [Exercise].

Invariants under Similarity

Theorem 3. If A ∼ B, then
charA (x) = charB (x).

Proof. Exercise.

Corollary 1. If A ∼ B, then A and B have the same eigenvalues, counted with multiplicity.

Theorem (determinant and trace)

Theorem 4. Let A ∈ Mn (C) and let λ1 , . . . , λn be the eigenvalues of A in C (counted with multi-
plicity). Then

(i) det(A) = λ1 λ2 · · · λn ,

(ii) trace(A) = λ1 + λ2 + · · · + λn .

Proof. Exercise.

Diagonalization

Definition 6 (Diagonalizable Matrix). A matrix A ∈ Mn (F) is called diagonalizable if there exists

an invertible matrix P ∈ Mn (F) such that

P −1 AP

is a diagonal matrix.

Eigenvector Criterion

Suppose A is diagonalizable. Then there exists an invertible matrix

P = [v1 v2 · · · vn ]

such that  
λ1 0 ··· 0
 
−1
0 λ2 · · · 0 
P AP = D =  . .. . . .. .
 
 .. . . . 
 
0 0 ··· λn
Then
AP = P D.

13
 Applying both sides to ei ,
Avi = λi vi .

Hence, the columns of P are eigenvectors of A.

As a consequence of the above exercise, we get the following Characterisation of Diagonalizability:

Theorem 5. Let A ∈ Mn (F). Then A is diagonalizable if and only if A has n linearly independent
eigenvectors.

Theorem 6. Let A ∈ Mn (F). Then A is diagonalizable if and only if A has n linearly independent
eigenvectors.

Proof. (⇒) Assume A is diagonalizable. Then there exists an invertible matrix P ∈ Mn (F) and a
diagonal matrix D such that
A = P DP −1 .

Let the diagonal entries of D be λ1 , . . . , λn . Write

 
P = v1 · · · v n ,

so the columns v1 , . . . , vn form a basis of Fn (hence are linearly independent).

From A = P DP −1 we get AP = P D (multiply on the right by P ):

AP = P DP −1 P = P D.

Comparing columns of both sides,

Avi = λi vi (i = 1, . . . , n).

Thus each vi is an eigenvector of A, and since the columns of P are linearly independent, A has n
linearly independent eigenvectors.

(⇐) Conversely, assume A has n linearly independent eigenvectors v1 , . . . , vn with corresponding

eigenvalues λ1 , . . . , λn , i.e.
Avi = λi vi (i = 1, . . . , n).

Let
 
P = v1 · · · vn , D = diag(λ1 , . . . , λn ).

Since v1 , . . . , vn are linearly independent, P is invertible.

Now compute AP . Its i-th column is Avi = λi vi , hence
 
λ1 0
      .. 
AP = Av1 · · · Avn = λ1 v1 · · · λn vn = v1 · · · vn 
 .  = P D.

0 λn

Thus AP = P D. Multiplying on the left by P −1 gives

P −1 AP = D,

so A is similar to a diagonal matrix, i.e. A is diagonalizable.

Therefore, A is diagonalizable if and only if it has n linearly independent eigenvectors.

14
Algorithm to Check Diagonalizability

1. Compute the characteristic polynomial charA (x).

2. Find all eigenvalues λ1 , . . . , λk .

3. For each λi , solve

(A − λi I)x = 0.

4. Find a basis Bi of each eigenspace.

5. If
X
dim WA (λi ) = n,
i

then A is diagonalizable.

Example: Illustrating the Algorithm

Consider  
2 1 0
 
0 2 0 ∈ M3 (R).
A= 
0 0 3

1. Compute the characteristic polynomial charA (x).

Since A is upper triangular, the eigenvalues are the diagonal entries, and

charA (x) = det(xI − A) = (x − 2)2 (x − 3).

2. Find all eigenvalues.

Thus the eigenvalues are

λ1 = 2 (algebraic multiplicity 2), λ2 = 3 (algebraic multiplicity 1).

3. For each λi , solve (A − λi I)x = 0.

(i) For λ = 2:  
0 1 0
 
A − 2I = 
0 0 0 .

0 0 1

Solve (A − 2I)x = 0. Let x = (x1 , x2 , x3 )T . Then

x2 = 0, x3 = 0, x1 free.

So  
 1 

 
 
WA (2) = ker(A − 2I) = span 0 ,
  dim WA (2) = 1.

 
 0 


15
 A basis is  
1

 

B1 = 0  .
 


 0 

(ii) For λ = 3:  
−1 1 0
 
A − 3I = 
 0 −1 0 .

0 0 0
Solve (A − 3I)x = 0. From the second row, −x2 = 0 ⇒ x2 = 0. Then the first row gives
−x1 + x2 = 0 ⇒ x1 = 0. Thus x3 is free, and
 
0

 

WA (3) = ker(A − 3I) = span  0 ,
  dim WA (3) = 1.


 1 

A basis is  
0

 

B2 = 0  .
 

 
 1 

4. Check the sum of dimensions.

We have
dim WA (2) + dim WA (3) = 1 + 1 = 2 ̸= 3.

5. Conclusion.
Since the total number of linearly independent eigenvectors is 2 < 3, the matrix A is

not diagonalizable.

Example 2

Consider  
2 1 0
 
1 2 0 ∈ M3 (R).
A= 
0 0 3
Clearly A is not diagonal (it has nonzero off-diagonal entries). We use the algorithm to check that
it is diagonalizable.

1. Compute the characteristic polynomial charA (x).

Compute
 
x − 2 −1 0 !
  x − 2 −1
charA (x) = det(xI − A) = det 
 −1 x − 2  = (x − 3) det −1 x − 2 .
0 
0 0 x−3

16
 Now !
x−2 −1
det = (x − 2)2 − 1 = (x − 1)(x − 3).
−1 x−2
Hence
charA (x) = (x − 3)(x − 1)(x − 3) = (x − 1)(x − 3)2 .

2. Find all eigenvalues.

Thus the eigenvalues are

λ1 = 1 (algebraic multiplicity 1), λ2 = 3 (algebraic multiplicity 2).

3. For each λi , solve (A − λi I)x = 0.

(i) For λ = 1:  
1 1 0
 
A−I =
1 1 0 .

0 0 2

Let x = (x1 , x2 , x3 )T . Then

x1 + x2 = 0, x3 = 0.

So  
 1 

 

WA (1) = ker(A − I) = span 
−1 ,
 dim WA (1) = 1.


 0  

A basis is  
 1 

 

B1 = 
−1 .



 0  

(ii) For λ = 3:  
−1 1 0
 
A − 3I = 
 1 −1 0 .

0 0 0
Then (A − 3I)x = 0 gives
−x1 + x2 = 0 ⇐⇒ x2 = x1 ,

and x3 is free. Hence

   
1 0

 

WA (3) = ker(A − 3I) = span 1  , 0 ,
    dim WA (3) = 2.

 
 0 1 

A basis is    
1 0

 

B2 = 
1 0 .
 ,  

 
 0 1 

17
 4. Check the sum of dimensions.
We have
dim WA (1) + dim WA (3) = 1 + 2 = 3 = n.

5. Conclusion.
Since the total dimension of the eigenspaces is 3, the matrix A has 3 linearly independent
eigenvectors and is therefore diagonalizable.

Diagonalization. Taking eigenvectors as columns of

   
1 1 0 1 0 0
   
P = −1 1 0 ,
 D=
0 3 0  ,

0 0 1 0 0 3

we have A = P DP −1 .

Linear Independence of Eigenvectors

Theorem 7. Eigenvectors corresponding to distinct eigenvalues are linearly independent.

Proof. We argue by induction.

For k = 1 the claim is trivial.
For k = 2, if Avi = λi vi with λ1 ̸= λ2 and c1 v1 +c2 v2 = 0, applying A−λ2 I gives c1 (λ1 −λ2 )v1 = 0,
hence c1 = c2 = 0.
Pk
Assume the claim holds for k − 1 eigenvectors. If i=1 ci vi = 0, applying A − λk I yields
k−1
X
ci (λi − λk )vi = 0.
i=1

By induction, all ci = 0.

Corollary 2. If A ∈ Mn (F) has n distinct eigenvalues λ1 , . . . , λn with corresponding eigenvectors

v1 , . . . , vn , then
P = [ v1 v2 · · · vn ]

is invertible and
P −1 AP = diag(λ1 , . . . , λn ).

Hence A is diagonalizable.

Symmetric and Orthogonal Matrices

Motivation

Consider the matrix !

0 −1
A= .
1 0

18
Its characteristic polynomial is
χA (x) = x2 + 1.

Hence the eigenvalues of A are ±i, which are distinct and lie in C. Therefore, A is diagonalizable
over C, but not diagonalizable over R.
However, if we assume that A is a symmetric matrix over R, then we will show that A is always
diagonalizable over R.
Before proving this, we first discuss orthogonal matrices.

Orthogonal Matrices

Definition 7. A matrix A ∈ Mn (R) is called orthogonal if

AAT = I = AT A.

Theorem 8. For A ∈ Mn (R), the following are equivalent:

1. The column vectors of A are orthonormal.

2. AT A = In .

3. AT = A−1 .

4. AAT = In .

5. ∥Ax∥ = ∥x∥ for all x ∈ Rn .

6. ⟨Ax, Ay⟩ = ⟨x, y⟩ for all x, y ∈ Rn .

7. The row vectors of A are orthonormal.

Proof. (Exercise.)

Eigenvalues of Symmetric Matrices

Theorem 9. Let A ∈ Mn (R) be symmetric, i.e. AT = A. Then all eigenvalues of A are real.

Proof. View A as an element of Mn (C). Let λ ∈ C be an eigenvalue of A and 0 ̸= u ∈ Cn an

associated eigenvector, so
Au = λu.

Then
uT AT = λuT .

Since AT = A,
uT A = λuT .

Taking complex conjugates,

uT A = λ uT .

Multiplying by u,
uT Au = λ uT u.

19
On the other hand,
uT Au = λ uT u.

Hence
λ∥u∥2 = λ∥u∥2 .

Since u ̸= 0, we conclude λ = λ, so λ ∈ R.

Orthogonal Diagonalization

Theorem 10 (Spectral Theorem for Symmetric Matrices). Let A ∈ Mn (R) be symmetric. Then
there exists an orthogonal matrix P ∈ Mn (R) such that

P −1 AP = P T AP

is diagonal.

Proof. We prove this by induction on n.

If n = 1, the statement is obvious.
Assume the result holds for (n − 1) × (n − 1) symmetric matrices. Let A ∈ Mn (R) be symmetric.
By the previous theorem, A has a real eigenvalue λ1 . Let v1 ∈ Rn be a corresponding eigenvector
with ∥v1 ∥ = 1.
Extend {v1 } to an orthonormal basis

B = {v1 , v2 , . . . , vn }

of Rn using the Gram–Schmidt process. Let

Q1 = [ v1 v2 · · · vn ].

Then Q1 is orthogonal.
Since
(Q−1 T −1
1 AQ1 ) = Q1 AQ1 ,

the matrix Q−1

1 AQ1 is symmetric. Moreover,

Q−1
1 AQ1 e1 = λ1 e1 .

Hence !
λ1 0
Q−1
1 AQ1 = ,
0 A1
where A1 ∈ Mn−1 (R) is symmetric.
By the induction hypothesis, there exists an orthogonal matrix Q2 ∈ Mn−1 (R) such that

Q−1
2 A1 Q2

is diagonal.
Define !
1 0
Q3 = .
0 Q2

20
Then Q3 is orthogonal and ! !
λ1 0 λ1 0
Q−1
3 Q3 = ,
0 A1 0 D
where D is diagonal.
Finally, set
P = Q 1 Q3 .

Then P is orthogonal and

P −1 AP

is diagonal.

Example: A 2 × 2 Symmetric Matrix

Consider the symmetric matrix !

2 1
A= .
1 2
The characteristic polynomial is

χA (λ) = det(A − λI) = (2 − λ)2 − 1 = λ2 − 4λ + 3,

so the eigenvalues are

λ1 = 1, λ2 = 3.

For λ1 = 1, !
1
(A − I)v = 0 ⇒ v1 = .
−1
For λ2 = 3, !
1
(A − 3I)v = 0 ⇒ v2 = .
1
Normalize the eigenvectors:
! !
1 1 1 1
u1 = √ , u2 = √ .
2 −1 2 1
Define the orthogonal matrix !
√1 √1
P = 2 2 .
− √12 √1
2

Then P T P = I, and !
T 1 0
P AP = .
0 3
Thus A is diagonalized by an orthogonal matrix, illustrating the Spectral Theorem for real
symmetric matrices.

Conclusion

Every real symmetric matrix is diagonalizable by an orthogonal change of basis. In particular,

symmetric matrices admit an orthonormal basis of eigenvectors.

21
Cayley–Hamilton Theorem
Theorem 11. Let A be an n × n matrix and let its characteristic polynomial be

p(λ) = det(λI − A).

Then A satisfies its own characteristic polynomial, that is,

p(A) = 0,

where 0 denotes the zero matrix.

Proof of the above theorem is beyond the scope of this course. However, we state and prove it
below for an optional reading.

Proof. (optional reading) First note that over C, A can be conjugated to an upper triangular matrix.
Since the identity p(A) = 0 is preserved under similarity, we may assume without loss of generality
that A is upper triangular.
So assume  
λ1 ∗ · · · ∗
 
 0 λ2 · · · ∗ 
A= . .
. . . . . ... 
.
 
 ..
 
0 · · · 0 λn
For an upper triangular matrix, det(λI − A) = ni=1 (λ − λi ), hence
Q

n
Y
p(λ) = (λ − λi ).
i=1

Thus
n
Y
p(A) = (A − λi I).
i=1

We prove by induction on n that this product is the zero matrix.

Base case (n = 1). If A = [λ1 ], then p(λ) = λ − λ1 and p(A) = A − λ1 I = 0.

Induction step. Assume the statement holds for (n − 1) × (n − 1) upper triangular matrices. Write
A in block form: !
λ1 u
A= ,
0 A1
where u is a 1 × (n − 1) row vector and A1 ∈ Mn−1 (C) is upper triangular with diagonal entries
λ2 , . . . , λ n .
Let
n
Y
q(λ) = (λ − λi ), so that p(λ) = (λ − λ1 )q(λ).
i=2

Then
p(A) = (A − λ1 I) q(A).

22
Claim 1: q(A) has the block form
!
q(λ1 ) w
q(A) = for some 1 × (n − 1) row vector w.
0 q(A1 )
Pn−1
Indeed, since q(λ) = k=0 ck λ
k for some scalars ck ,
n−1
X
q(A) = ck Ak .
k=0

Each power Ak is block upper triangular of the form

!
k λk1 ∗
A = ,
0 Ak1

hence summing gives the stated block form, with top-left entry ck λk1 = q(λ1 ) and bottom-right
P

block ck Ak1 = q(A1 ).

P

Claim 2: q(A1 ) = 0. This follows from the induction hypothesis applied to the (n − 1) × (n − 1)
upper triangular matrix A1 , since q(λ) = det(λI − A1 ) is its characteristic polynomial.
Therefore, !
q(λ1 ) w
q(A) = .
0 0
Also, !
0 u
A − λ1 I = .
0 A1 − λ1 I
Multiplying these two block matrices gives
! ! !
0 u q(λ1 ) w 0 0
(A − λ1 I) q(A) = = .
0 A1 − λ1 I 0 0 0 0

Hence p(A) = 0, completing the induction.

Therefore A satisfies its characteristic polynomial.

Example 1 (Diagonal Matrix)

Let !
2 0
A= .
0 3
The characteristic polynomial is

p(λ) = (λ − 2)(λ − 3) = λ2 − 5λ + 6.

Substituting A,
p(A) = A2 − 5A + 6I = 0.

23
Example 2 (Non-Diagonal Matrix)

Let !
1 2
A= .
3 4
The characteristic polynomial is

p(λ) = λ2 − 5λ − 2.

By the Cayley–Hamilton theorem,

A2 − 5A − 2I = 0.

Example 3 (Repeated Eigenvalue)

Let !
2 1
A= .
0 2
The characteristic polynomial is
p(λ) = (λ − 2)2 .

Hence,
(A − 2I)2 = 0.

Elementary and Useful Applications

1. Expressing Higher Powers of a Matrix

From Example 2,
A2 = 5A + 2I.

Thus,
A3 = A(5A + 2I) = 5A2 + 2A = 27A + 10I.

2. Finding the Inverse of a Matrix

If A is invertible and satisfies

A2 − 5A − 2I = 0,

multiply both sides by A−1 :

A − 5I − 2A−1 = 0.

Hence,
A−1 = 12 (A − 5I).

24
3. Simplifying Matrix Polynomials

Any polynomial f (A) can be reduced to a polynomial of degree at most n − 1.

For a 2 × 2 matrix,
f (A) = αA + βI,

for suitable scalars α, β.

—

4. Nilpotent Matrices

If the characteristic polynomial of A is

p(λ) = λk ,

then by Cayley–Hamilton,
Ak = 0.

Summary

• Every square matrix satisfies its own characteristic polynomial.

• Cayley–Hamilton allows reduction of higher powers of matrices.

• It provides an efficient method for finding inverses of matrices.

• It simplifies polynomial expressions in matrices.

25