MATH661

Lecture 12: The Eigenvalue Problem

1.Definitions

Linear endomorphisms $𝒇 : ℂ^{m} \to ℂ^{m}$ , represented by $𝑨 \in ℂ^{m \times m}$ , can exhibit invariant directions $𝒙 \neq 𝟎$ for which

𝒇 (𝒙) = 𝑨 𝒙 = λ 𝒙,

known as eigenvectors, with associated eigenvalue $λ \in ℂ$ . Eigenvectors are non-zero elements of the null space of $𝑨 - λ 𝑰$ ,

(𝑨 - λ 𝑰) 𝒙 = 𝟎,

and the null-space is referred to as the eigenspace of $𝑨$ for eigenvalue $λ$ , $ℰ_{𝑨} (λ) = N (𝑨 - λ 𝑰)$ .

Non-zero solutions are obtained if $𝑨 - λ 𝑰$ is rank-deficient (singular), or has linearly dependent columns in which case

\det (𝑨 - λ 𝑰) = 0 \Rightarrow \det (λ 𝑰 - 𝑨) = | \begin{array}{cccc} λ - a_{11} & a_{12} & \dots & a_{1 m} \\ a_{21} & λ - a_{22} & \dots & a_{2 m} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 2} & \dots & λ - a_{m m} \end{array} | = 0 .

From the determinant definition as “sum of all products choosing an element from row/column”, it results that

\det (λ 𝑰 - 𝑨) = λ^{m} + c_{1} λ^{m - 1} + \dots + c_{m - 1} λ + c_{m} = p_{A} (λ),

known as the characteristic polynomial associated with the matrix 𝑨, and of degree $m$ . The characteristic polynomial is monic, meaning that the coefficient of the highest power $λ^{m}$ is equal to one. The fundamental theorem of algebra states that $p_{A} (λ)$ of degree $m$ has $m$ roots, hence $𝑨 \in ℂ^{m \times m}$ has $m$ eigenvalues (not necessarily distinct), and $m$ associated eigenvectors. This can be stated in matrix form as

𝑨 𝑿 = 𝑿 𝚲,

with

𝑿 = [\begin{array}{lll} 𝒙_{1} & \dots & 𝒙_{m} \end{array}], 𝚲 = diag (λ_{1}, \dots, λ_{m}),

the eigenvector matrix and eigenvalue matrix, respectively. By definition, the matrix $𝑨$ is diagonalizable if $𝑿$ is of full rank, in which case the eigendecomposition of $𝑨$ is

𝑨 = 𝑿 𝚲 𝑿^{- 1} .

1.1.Coordinate transformations

The statement $𝑨 𝒙 = λ 𝒙$ , that eigenvector $𝒙$ is an invariant direction of the operator $𝑨$ along which the effect of operator is scaling by $λ$ , suggests that similar behavior would be obtained under a coordinate transformation $𝑻 𝒚 = 𝑰 𝒙 = 𝒙$ . Assuming $𝑻$ is of full rank and introducing $𝑩 = 𝑻^{- 1} 𝑨 𝑻$ , this leads to

𝑨 𝒙 = 𝑨 𝑻 𝒚 = λ 𝒙 = λ 𝑻 𝒚 \Rightarrow 𝑻^{- 1} 𝑨 𝑻 𝒚 = λ 𝒚 .

Upon coordinate transformation, the eigenvalues (scaling factors along the invariant directions) stay the same. Metric-preserving coordinate transformations are of particular interest, in which case the transformation matrix is unitary $𝑩 = 𝑸^{*} 𝑨 𝑸$ .

Definition. Matrices $𝑨, 𝑩 \in ℂ^{m \times m}$ are said to be similar, $𝑩 \sim 𝑨$ , if there exists some full rank matrix $𝑻 \in ℂ^{m \times m}$ such that $𝑩 = 𝑻^{- 1} 𝑨 𝑻$ .

Proposition. Similar matrices $𝑨, 𝑩 \in ℂ^{m \times m}$ , $𝑩 = 𝑻^{- 1} 𝑨 𝑻$ , have the same eigenvalues, and eigenvectors $𝒙$ of $𝑨$ , $𝒚$ of $𝑩$ are related through $𝒙 = 𝑻 𝒚$ .

Since the eigenvalues of $𝑩 \sim 𝑨$ are the same, and a polynomial is completely specified by its roots and coefficient of highest power, the characteristic polynomials of $𝑨, 𝑩$ must be the same

p_{𝑨} (λ) = \prod_{k = 1}^{m} (λ - λ_{k}) = p_{𝑩} (λ) .

This can also be verified through the determinant definition

p_{𝑩} (t) = \det (λ 𝑰 - 𝑩) = \det (λ 𝑻^{- 1} 𝑻 - 𝑻^{- 1} 𝑨 𝑻) = \det (𝑻^{- 1} (λ 𝑰 - 𝑨) 𝑻) = \det (𝑻^{- 1}) \det (λ 𝑰 - 𝑨) \det (𝑻) = p_{𝑨} (λ),

since $\det (𝑻^{- 1}) = 1 / \det (𝑻)$ .

1.2.Paradigmatic eigenvalue problem solutions

$\circ$ Reflection matrix. The matrix

𝑯 = 𝑰 - 2 𝒒 𝒒^{T} \in ℝ^{2 \times 2}, || 𝒒 || = 1,

is the two-dimensional Householder reflector across $N (𝒒^{T})$ . Vectors colinear with $𝒒$ change direction along the same orientation upon reflection, while vectors orthogonal to $𝒒$ (i.e., in the null space $𝑵 (𝒒^{T})$ ) are unchanged. It is therefore to be expected that $λ_{1} = - 1$ , $𝒙_{1} = 𝒒$ , and $λ_{2} = 1$ , $𝒒^{T} 𝒙_{2} = 0$ . This is readily verified

𝑯 𝒒 = (𝑰 - 2 𝒒 𝒒^{T}) 𝒒 = 𝒒 - 2 𝒒 = - 𝒒,

𝑯 𝒙_{2} = (𝑰 - 2 𝒒 𝒒^{T}) 𝒙_{2} = 𝒙_{2} .

Figure 1. Reflector in two dimensions

∴	v=[-1; 1]; q=v/norm(v); H=I-2qq';

∴	eigvals(H)

$[\begin{array}{c} - 0.9999999999999996 \\ 1.0 \end{array}]$ (1)

∴	eigvecs(H)

$[\begin{array}{cc} - 0.7071067811865475 & 0.7071067811865475 \\ 0.7071067811865475 & 0.7071067811865475 \end{array}]$ (2)

∴

$\circ$ Rotation matrix. The matrix

𝑹 (θ) = [\begin{array}{ll} \cos θ & - \sin θ \\ \sin θ & \cos θ \end{array}],

represents the isometric rotation of two-dimensional vectors. If $θ = 0$ , $𝑹 = 𝑰$ with eigenvalues $λ_{1} = λ_{2} = 1$ , and eigenvector matrix $𝑿 = 𝑰$ . For $θ = π$ , the eigenvalues are $λ_{1} = λ_{2} = - 1$ , again with eigenvector matrix $𝑿 = 𝑰$ . If $\sin θ \neq 0$ , the orientation of any non-zero $𝒙 \in ℝ^{2}$ changes upon rotation by $θ$ . The characteristic polynomial has complex roots

p (λ) = {(λ - \cos θ)}^{2} + \sin^{2} θ \Rightarrow λ_{1, 2} = \cos θ \pm i \sin θ = e^{\pm i θ}

and the directions of invariant orientation have complex components (are outside the real plane $ℝ^{2}$ )

𝑿 = [\begin{array}{ll} 1 & - 1 \\ i & i \end{array}], 𝑹 𝑿 = [\begin{array}{ll} e^{- i θ} & - e^{i θ} \\ i e^{- i θ} & i e^{i θ} \end{array}] = [\begin{array}{ll} 1 & - 1 \\ i & i \end{array}] [\begin{array}{ll} e^{- i θ} & 0 \\ 0 & e^{i θ} \end{array}] .

∴	R=[1 -1; 1 1]/sqrt(2); eigvals(R)

$[\begin{array}{c} 0.7071067811865475 - 0.7071067811865475 i \\ 0.7071067811865475 + 0.7071067811865475 i \end{array}]$ (3)

∴	eigvecs(R)

$[\begin{array}{cc} 0.7071067811865475 + 0.0 i & 0.7071067811865475 + 0.0 i \\ 0.0 + 0.7071067811865475 i & 0.0 - 0.7071067811865475 i \end{array}]$ (4)

∴

$\circ$ Second-order differentiation matrix. Eigenvalues of matrices arising from discretization of continuum operators can be obtained from the operator eigenproblem. The second-order differentiation operator $\partial_{x}^{2}$ has eigenvalues $- ξ^{2}$ associated with eigenfunctions $\sin (ξ x)$

\partial_{x}^{2} \sin (ξ x) = - ξ^{2} \sin (ξ x) .

Sampling of $\sin (ξ x)$ at $x_{k} = k h$ , $k = 1, \dots, m$ , $h = π / (m + 1)$ leads to the vector $𝒖 \in ℝ^{m}$ with components $u_{k} = \sin (ξ k h)$ . The boundary conditions at the sampling interval end-points affect the eigenvalues. Imposing $\sin (ξ x) = 0$ , at $x = 0$ and $x = π$ leads to $ξ \in ℤ$ . The derivative can be approximated at the sample points through

u_{k}^{''} ≅ \frac{\sin [ξ (x_{k} + h)] - 2 \sin [ξ x_{k}] + \sin [ξ (x_{k} - h)]}{h^{2}} = \frac{2}{h^{2}} (\cos (ξ h) - 1) \sin (ξ k h) = - \frac{4}{h^{2}} \sin^{2} (\frac{ξ h}{2}) \sin (ξ k h) .

The derivative approximation vector $𝒖^{''} = {[u_{k}^{''}]}_{k = 1, \dots m}$ results from a linear mapping $𝒖^{''} = 𝑫 𝒖,$ and the matrix

𝑫 = \frac{1}{h^{2}} diag ([\begin{array}{lll} 1 & - 2 & 1 \end{array}]),

has eigenvectors $𝒖$ and eigenvalues $- (4 / h^{2}) \sin^{2} (ξ h / 2)$ , $ξ = 1, 2, \dots, m$ . In the limit of an infinite number of sampling points the continuum eigenvalues are obtained, exemplifying again the correspondence principle between discrete and continuum representations

{lim}_{h \to 0} - \frac{4}{h^{2}} \sin^{2} (\frac{ξ h}{2}) = - ξ^{2} .

∴	m=4; o=ones(m-1,1)[:,1]; D=diagm(-1 => o, 1 => o)-2*I

$[\begin{array}{cccc} - 2.0 & 1.0 & 0.0 & 0.0 \\ 1.0 & - 2.0 & 1.0 & 0.0 \\ 0.0 & 1.0 & - 2.0 & 1.0 \\ 0.0 & 0.0 & 1.0 & - 2.0 \end{array}]$ (5)

∴	function ErrorλD(m) h=π/(m+1); ξ=1:m; o=ones(m-1); D=(diagm(-1=>o, 1=>o)-2I)/h^2; λD = sort(eigvals(D),rev=true) λ = -(4/h^2)sin.(ξ*h/2).^2 ε=norm(λD .- λ)/norm(λ) end;

∴	ε=ErrorλD.(20:20:100)';

∴	print(round.(ε; digits=3))

[0.0 0.0 0.0 0.0 0.0]

∴	function eigD(m) h=π/m; o=ones(m-1,1)[:,1]; D=diagm(-1 => o, 1 => o)-2I; λD=sort(eigvals(D),rev=true) λ = -4sin.(collect(1:m).*h/2).^2 return [λD λ] end;

∴

clf();

∴	for m=10:10:100 local Λ=eigD(m) plot(1:m,Λ[:,1],"ob",markerfacecolor="none") plot(1:m,Λ[:,2],"xr") end

∴	xlabel("k"); ylabel("λ[k]");

∴	pre=homedir()*"/courses/MATH661/images/";

∴	savefig(pre*"L14D2eigs.eps");

∴

1.3.Matrix eigendecomposition

A solution $𝑿, 𝚲$ to the eigenvalue problem $𝑨 𝑿 = 𝑿 𝚲$ always exists, but the eigenvectors of $𝑨$ do not always form a basis set, i.e., $𝑿$ is not always of full rank. The factorized form of the characteristic polynomial of $𝑨 \in ℂ^{m \times m}$ is

p_{𝑨} (λ) = \det (λ 𝑰 - 𝑨) = \prod_{k = 1}^{K} {(λ - λ_{k})}_{}^{m_{k}},

with $K ⩽ m$ denoting the number of distinct roots of $p_{𝑨} (λ)$ , and $m_{k}$ is the algebraic multiplicity of eigenvalue $λ_{k}$ , defined as the number of times the root $λ_{k}$ is repeated. Let $ℰ_{k}$ denote the associated eigenspace $ℰ_{k} = ℰ_{𝑨} (λ_{k}) = N (𝑨 - λ_{k} 𝑰)$ . The dimension of $ℰ_{k}$ denoted by $n_{k}$ is the geometric multiplicity of eigenvalue $λ_{k}$ . The eigenvector matrix is of full rank when the vector sum of the eigenspaces covers $ℂ^{m}$ , as established by the following results.

Proposition. The geometric multiplicity is at least 1, $n_{k} ⩾ 1$ .

Proof. By contradiction if $n_{k} = \dim ℰ_{k}$ , then $ℰ_{k} = {𝟎}$ , but eigenvectors cannot be null. $□$

Proposition. If $λ_{i} \neq λ_{j}$ then $ℰ_{i} \cap ℰ_{j} = {𝟎}$ (the eigenspaces of distinct eigenvalues are disjoint)

Proof. Let $𝒙 \in$ $ℰ_{i}$ , hence $𝑨 𝒙 = λ_{i} 𝒙$ and $𝒙 \in$ $ℰ_{j}$ , hence $𝑨 𝒙 = λ_{j} 𝒙$ . Subtraction gives

𝑨 𝒙 - 𝑨 𝒙 = 𝟎 = (λ_{i} - λ_{j}) 𝒙 .

Since $λ_{i} \neq λ_{j}$ it results that $𝒙 = 𝟎$ . $□$

Proposition. The geometric multiplicity of an eigenvalue is less or equal to its algebraic multiplicity,

$0 < n_{k} = \dim (N (𝑨 - λ_{k} 𝑰)) ⩽ m_{k} .$

Proof. Let $\hat{𝑽} \in ℂ^{m \times n_{k}}$ be an orthonormal basis for $N (𝑨 - λ_{k} 𝑰)$ . By definition of a null space, $𝒚 \in N (𝑨 - λ_{k} 𝑰)$

(𝑨 - λ_{k} 𝑰) 𝒚 = 𝟎 \Rightarrow 𝑨 𝒚 = λ_{k} 𝒚,

i.e., every vector of the eigenspace is an eigenvector with eigenvalue $λ_{k}$ . Then

𝑨 \hat{𝑽} = 𝑨 [\begin{array}{llll} 𝒗_{1} & 𝒗_{2} & \dots & 𝒗_{n_{k}} \end{array}] = [\begin{array}{llll} 𝑨 𝒗_{1} & 𝑨 𝒗_{2} & \dots & 𝑨 𝒗_{n_{k}} \end{array}] = λ [\begin{array}{llll} 𝒗_{1} & 𝒗_{2} & \dots & 𝒗_{n_{k}} \end{array}] .

Form the unitary matrix $𝑽 = [\begin{array}{ll} \hat{𝑽} & 𝒁 \end{array}] \in ℂ^{m \times m}$ , and compute

𝑽^{*} 𝑨 𝑽 = [\begin{array}{l} {\hat{𝑽}}^{*} \\ 𝒁^{*} \end{array}] 𝑨 [\begin{array}{ll} \hat{𝑽} & 𝒁 \end{array}] = [\begin{array}{l} {\hat{𝑽}}^{*} \\ 𝒁^{*} \end{array}] [\begin{array}{ll} 𝑨 \hat{𝑽} & 𝑨 𝒁 \end{array}] = [\begin{array}{ll} {\hat{𝑽}}^{*} 𝑨 \hat{𝑽} & {\hat{𝑽}}^{*} 𝑨 𝒁 \\ 𝒁^{*} 𝑨 \hat{𝑽} & 𝒁^{*} 𝑨 𝒁 \end{array}] .

Since $𝑽$ is unitary, obtain

{\hat{𝑽}}^{*} 𝑨 \hat{𝑽} = λ [\begin{array}{l} 𝒗_{1}^{*} \\ 𝒗_{2}^{*} \\ ⋮ \\ 𝒗_{n_{k}}^{*} \end{array}] [\begin{array}{llll} 𝒗_{1} & 𝒗_{2} & \dots & 𝒗_{n_{k}} \end{array}] = λ 𝑰_{n_{k}}, 𝒁^{*} 𝑨 \hat{𝑽} = λ [\begin{array}{l} 𝒛_{1}^{*} \\ 𝒛_{2}^{*} \\ ⋮ \\ 𝒛_{m - n_{k}}^{*} \end{array}] [\begin{array}{llll} 𝒗_{1} & 𝒗_{2} & \dots & 𝒗_{n_{k}} \end{array}] = 𝟎,

where $𝑰_{n_{k}}$ is the $n_{k} \times n_{k}$ identity matrix, and in the above $𝟎$ denotes a $(m - n_{k}) \times n_{k}$ matrix of zeros. The matrix

𝑩 = 𝑽^{*} 𝑨 𝑽 = [\begin{array}{ll} λ 𝑰 & 𝑪 \\ 𝟎 & 𝑫 \end{array}]

is similar to $𝑨$ and has the same eigenvalues. Since $\det (z 𝑰 - 𝑩) = \det ((z - λ) 𝑰) \det (𝑫)$ , the algebraic multiplicity of $λ$ must be at least $n_{k}$ , i.e., $n_{k} ⩽ m_{k}$ . $□$

Definition 1. An eigenvalue for which the geometric multiplicity is less than the algebraic multiplicity is said to be defective.

$\circ$ Example. Non-defective matrices exist, for example

𝑨 = [\begin{array}{lll} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{array}], 𝑿 = 𝑰, 𝚲 = diag ([\begin{array}{lll} 1 & 2 & 3 \end{array}]) .

∴	A=diagm([1,2,3])

$[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{array}]$ (6)

∴	eigvals(A)

$[\begin{array}{c} 1.0 \\ 2.0 \\ 3.0 \end{array}]$ (7)

∴	eigvecs(A)

$[\begin{array}{ccc} 1.0 & 0.0 & 0.0 \\ 0.0 & 1.0 & 0.0 \\ 0.0 & 0.0 & 1.0 \end{array}]$ (8)

∴

$\circ$ Example. Non-defective matrices with repeated eigenvalues exist, for example

𝑨 = [\begin{array}{lll} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}], 𝑿 = 𝑰, 𝚲 = diag ([\begin{array}{lll} 1 & 1 & 1 \end{array}]) .

∴	A=diagm([1,1,1]); eigvals(A)

$[\begin{array}{c} 1.0 \\ 1.0 \\ 1.0 \end{array}]$ (9)

∴	eigvecs(A)

$[\begin{array}{ccc} 1.0 & 0.0 & 0.0 \\ 0.0 & 1.0 & 0.0 \\ 0.0 & 0.0 & 1.0 \end{array}]$ (10)

∴

$\circ$ Example. Defective matrices exist, for example

𝑨 = [\begin{array}{lll} 3 & 1 & 1 \\ 0 & 3 & 1 \\ 0 & 0 & 3 \end{array}],

has eigenvalue $λ = 3$ with algebraic multiplicity $m_{1} = 3$ . Reduction to row-echelon form of $𝑨 - λ 𝑰$ leads to

𝑨 - λ 𝑰 = [\begin{array}{lll} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{array}],

and $N (𝑨 - λ 𝑰) = ⟨ 𝒆_{1} ⟩$ , i.e., the geometric multiplicity is equal to 1. The above is known as a Jordan block.

∴	A=[3 1 1; 0 3 1; 0 0 3]

$[\begin{array}{ccc} 3 & 1 & 1 \\ 0 & 3 & 1 \\ 0 & 0 & 3 \end{array}]$ (11)

∴	eigvals(A)

$[\begin{array}{c} 3.0 \\ 3.0 \\ 3.0 \end{array}]$ (12)

∴	X=eigvecs(A)

$[\begin{array}{ccc} 1.0 & - 1.0 & 1.0 \\ 0.0 & 6.661338147750939 e - 16 & - 6.661338147750945 e - 16 \\ 0.0 & 0.0 & 4.437342591868195 e - 31 \end{array}]$ (13)

∴	(X .+ 10) .- 10

$[\begin{array}{ccc} 1.0 & - 1.0 & 1.0 \\ 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 \end{array}]$ (14)

Proposition 2. A matrix is diagonalizable if the geometric multiplicity of each eigenvalue is equal to the algebraic multiplicity of that eigenvalue.

Proof. Recall that $𝑨$ is diagonalizable if the eigenvector matrix $𝑿$ is of full rank. Since the eigenspaces $ℰ_{j}$ of the $K$ distinct eigenvalues are disjoint, the column space of $𝑿$ is the direct vector sum of the eigenspaces

C (𝑿) = ℰ_{1} \oplus \dots \oplus ℰ_{K} .

The dimension of $C (𝑿)$ is therefore given by the sum of the eigenspace dimensions

\dim C (𝑿) = \sum_{k = 1}^{K} n_{k} ⩽ \sum_{k = 1}^{K} m_{k} = m .

Since $n_{k} ⩽ m_{k}$ , the only possibility for $𝑿$ to be of full rank, $\dim C (𝑿) = m$ , is for $n_{k} = m_{k}$ . $□$

1.4.Matrix properties from eigenvalues

Eigenvalues as roots of the characteristic polynomial

p_{A} (λ) = \det (λ 𝑰 - 𝑨) = λ^{m} + c_{1} λ^{m - 1} + \dots + c_{m - 1} λ + c_{m} = \prod_{k = 1}^{m} (λ - λ_{k})

reveal properties of a matrix $𝑨 \in ℂ^{m \times m}$ . The evaluation of $p_{A} (0)$ leads to

\det (- 𝑨) = {(- 1)}^{m} \det (𝑨) = {(- 1)}^{m} \prod_{k = 1}^{m} λ_{k},

hence the determinant of a matrix is given by the product of its eigenvalues

\det (𝑨) = \prod_{k = 1}^{m} λ_{k} .

The trace of a matrix is the sum of its diagonal elements is equal to the sum of its eigenvalues

tr (𝑨) = \sum_{k = 1}^{m} a_{k k} = \sum_{k = 1}^{m} λ_{k},

a relationship established by the Vieta formulas.

1.5.Matrix eigendecomposition applications

Whereas the SVD, QR, LU decompositions can be applied to general matrices $𝑨 \in ℂ^{m \times n}$ with $m$ not necessarily equal to $n$ , the eigendecomposition requires $𝑨 \in ℂ^{m \times m}$ , and hence is especially relevant in the characterization of endomorphisms. A generic time evolution problem is stated as

\partial_{t} 𝒖 = 𝒖_{t} = 𝒇 (𝒖), 𝒖 (0) = 𝒖_{0}, 𝒖 : ℝ_{+} \to ℂ^{m},

stating that the rate of change in the state variables $𝒖$ characterizing some system is a function of the current state through the function $𝒇 : ℂ^{m} \to ℂ^{m}$ , an endomorphism. An approximation of $𝒇$ is furnished by the MacLaurin series

𝒇 (𝒖) = 𝒗 + 𝑨 𝒖 + 𝒪 ({|| 𝒖 ||}^{2}), 𝒗 = 𝒇 (𝟎), 𝑨 = \frac{\partial 𝒇}{\partial 𝒖} (𝟎) .

Truncation at first order gives a linear ODE system $𝒖_{t} = 𝒗 + 𝑨 𝒖$ , that can be formally integrated to give

𝒖 (t) = 𝒗 t + e^{t 𝑨} 𝒖_{0} .

The matrix exponential $e^{t 𝑨}$ is defined as

e^{t 𝑨} = 𝑰 + \frac{1}{1!} t 𝑨 + \frac{1}{2!} {(t 𝑨)}^{2} + \frac{1}{3!} {(t 𝑨)}^{3} + \dots .

Evaluation of $𝑨^{n}$ requires $n - 1$ matrix multiplications or $(n - 1) m^{3}$ floating point operations. However, if the eigendecomposition of $𝑨 = 𝑿 𝚲 𝑿^{- 1}$ is available the matrix exponential can be evaluate in only $2 m^{3}$ operations since

𝑨^{k} = (𝑿 𝚲 𝑿^{- 1}) (𝑿 𝚲 𝑿^{- 1}) \dots (𝑿 𝚲 𝑿^{- 1}) = 𝑿 𝚲^{k} 𝑿^{- 1},

leads to

e^{t 𝑨} = 𝑿 e^{t 𝚲} 𝑿^{- 1} .

2.Computation of the SVD

The existence of the SVD $𝑨 = 𝑼 𝚺 𝑽^{*}$ was establish by a constructive procedure by complete induction. However the proof depends on determining the singular values, e.g., $σ_{1} = || 𝑨 ||$ . The existence of the singular values was established by an argument from analysis, that the norm function on a compact domain must attain its extrema. This however leaves open the problem of effectively determining the singular values. In practive the singular values and vectors are determined by solving the eigenvalue problem for $𝑨 𝑨^{*}$ and $𝑨^{*} 𝑨$

𝑨^{*} 𝑨 = {(𝑼 𝚺 𝑽^{*})}^{*} (𝑼 𝚺 𝑽^{*}) = 𝑽 𝚺^{T} 𝑼^{*} 𝑼 𝚺 𝑽^{*} = 𝑽 𝚺^{T} 𝚺 𝑽^{*} \Rightarrow (𝑨^{*} 𝑨) 𝑽 = 𝑽 𝚺^{T} 𝚺,

𝑨 𝑨^{*} = (𝑼 𝚺 𝑽^{*}) {(𝑼 𝚺 𝑽^{*})}^{*} = 𝑼 𝚺 𝑽^{*} 𝑽 𝚺^{T} 𝑼^{*} = 𝑼 𝚺 𝚺^{T} 𝑼^{*} \Rightarrow (𝑨 𝑨^{*}) 𝑼 = 𝑼 𝚺 𝚺^{T} .

From the above the left singular vectors $𝑼$ are eigenvectors of $𝑨 𝑨^{*}$ , and the right singular vectors are eigenvectors of $𝑨^{*} 𝑨$ . Both $𝑨 𝑨^{*}$ and $𝑨^{*} 𝑨$ have the same eigenvalues that are the squared singular values.