Theory

Eigenvectors, eigenvalues - Part II

The example above illustrates a general fact: if a matrix $A$ has enough independent eigenvectors $\{{\mathbf{c}}_1,\dots ,{\mathbf{c}}_n\}$ to form a basis of the vector space ${\mathbb{R}}^n$ on which $A$ acts, then if you write $A$ in the basis of these eigenvectors, it will have a diagonal form.

In other words, the eigenbasis of $A$ is a natural basis for $A$. It is a basis in which the action of $A$ is extremely simple: it is given by scaling the basis vectors by the respective eigenvalue numbers.

Sometimes a matrix has not enough independent eigenvectors. Here is an illustration:

Eigenvectors, eigenvalues - Part II (part 2)

Sometimes a real matrix has complex eigenvalues and eigenvectors. Here is an illustration:

Eigenvectors, eigenvalues - Part II (part 3)

It is important to be aware of these two situations. For the sake of exams, you should memorize one example of each type. (You can use the two above.)

Eigenvectors, eigenvalues - Part II (part 4)

Spectral Theorem: symmetric matrices have good eigen theory

A key point of the Spectral Theorem is that symmetric matrices never encounter the phenomena illustrated in the two examples above. Eigenvalues are always real numbers, and there are always enough eigenvectors to form a basis.

Eigenvectors vs. singular vectors

It is helpful to think about the concept of an eigenvector as consisting of two aspects:

• (1) Matrix acting by scaling
• (2) Fixed lines of matrix action

Aspect (1) allows easy computation and geometric understanding of the matrix action. It also allows us to focus on vectors that are more important (those having a larger scale factor). If we have a basis of such vectors, the matrix will have a simple diagonal form when written in this basis.

Aspect (2) goes much further, even though it essentially includes aspect (1). A fixed line (eigenline) is the span of any eigenvector. Such lines are mapped to themselves by the matrix action. This aspect describes eigenvector spans as analogues of fixed points of a function. The concept of fixed points and fixed lines (‘fixity’ in general) only applies when the function or matrix keeps vectors in the same space, i.e. has the same codomain as domain.

Eigenvectors
There are various contexts where a matrix does act on vectors in a single space. Aspect (2) is very useful in these contexts. For example, a differential operator, which produces a system of first-order linear differential equations, involves a matrix $A:V\to V$ for a vector space of functions $V$. For another example, the moment of inertia matrix describing angular moment of $3$D bodies in physics. Or the many operators of quantum mechanics.

One of the biggest advantages of aspect (2) is that it is compatible with iteration.

If $A:V\to V$ is a linear transformation (i.e. a matrix) having the same codomain as domain, we can define iterates $A^2,A^3$ etc. as matrix powers. These powers allow one to apply functions to matrices: if $f(x)={\sum }_{n=0}^{\infty }{a}_n{x}^n$ is a power series, we can define $f(A)$ by the power series $f(A)={\sum }_{n=0}^{\infty }{a}_n{A}^n$. (Bracketing any problems with convergence.) An extremely important series is $e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots$, since the function $e^{At}$ solves the linear ODE system $X^{\prime }(t)=AX(t)$.

It is hard to compute $e^{At}$, or more generally ${\sum }_{n=0}^{\infty }{a}_n{A}^n$, by direct multiplication and limits of partial sums. On the other hand, it is easy to compute $e^{At}$ when $A$ is a diagonal matrix, just as it is easy to compute $A^2\mathbf{v}$ when $\mathbf{v}$ is an eigenvector of $A$. (Namely, the latter is ${\lambda }^2\mathbf{v}$.) For example, in the $2\times 2$ case we have $e^{\left(\begin{array}{cc}{\lambda }_1& 0\\ 0& {\lambda }_2\end{array}\right)}=\left(\begin{array}{cc}{e}^{{\lambda }_1}& 0\\ 0& e^{{\lambda }_2}\end{array}\right)$.

Even when $A$ is not diagonal, if an eigenbasis matrix ${}_{\mathcal{B}}{T}_{\mathcal{C}}=\left(\begin{array}{cccc}{\mathbf{c}}_1& {\mathbf{c}}_2& \dots & {\mathbf{c}}_n\end{array}\right)$ can be found, then the powers of $A$ are still easy to calculate, because (e.g. in $3$D):

$$\begin{array}{rl}{A}^2& ={}_{\mathcal{B}}{T}_{\mathcal{C}}\left(\begin{array}{ccc}{\lambda }_1& 0& 0\\ 0& {\lambda }_2& 0\\ 0& 0& {\lambda }_3\end{array}\right){}_{\mathcal{C}}{T}_{\mathcal{B}}{}_{\mathcal{B}}{T}_{\mathcal{C}}\left(\begin{array}{ccc}{\lambda }_1& 0& 0\\ 0& {\lambda }_2& 0\\ 0& 0& {\lambda }_3\end{array}\right){}_{\mathcal{C}}{T}_{\mathcal{B}}\\ & \\ & ={}_{\mathcal{B}}{T}_{\mathcal{C}}\left(\begin{array}{ccc}{\lambda }_1& 0& 0\\ 0& {\lambda }_2& 0\\ 0& 0& {\lambda }_3\end{array}\right){}_{\mathcal{B}}{T}_{\mathcal{C}}^{-1}{}_{\mathcal{B}}{T}_{\mathcal{C}}\left(\begin{array}{ccc}{\lambda }_1& 0& 0\\ 0& {\lambda }_2& 0\\ 0& 0& {\lambda }_3\end{array}\right){}_{\mathcal{C}}{T}_{\mathcal{B}}\\ & \\ & ={}_{\mathcal{B}}{T}_{\mathcal{C}}\left(\begin{array}{ccc}{\lambda }_1& 0& 0\\ 0& {\lambda }_2& 0\\ 0& 0& {\lambda }_3\end{array}\right)\left(\begin{array}{ccc}{\lambda }_1& 0& 0\\ 0& {\lambda }_2& 0\\ 0& 0& {\lambda }_3\end{array}\right){}_{\mathcal{C}}{T}_{\mathcal{B}}\\ & \\ & ={}_{\mathcal{B}}{T}_{\mathcal{C}}\left(\begin{array}{ccc}{\lambda }_1^2& 0& 0\\ 0& {\lambda }_2^2& 0\\ 0& 0& {\lambda }_3^2\end{array}\right){}_{\mathcal{C}}{T}_{\mathcal{B}}.\end{array}$$

Similarly we have:

$$A^n={}_{\mathcal{B}}{T}_{\mathcal{C}}\left(\begin{array}{ccc}{\lambda }_1^n& 0& 0\\ 0& {\lambda }_2^n& 0\\ 0& 0& {\lambda }_3^n\end{array}\right){}_{\mathcal{C}}{T}_{\mathcal{B}},e^A={}_{\mathcal{B}}{T}_{\mathcal{C}}\left(\begin{array}{ccc}{e}^{{\lambda }_1}& 0& 0\\ 0& e^{{\lambda }_2}& 0\\ 0& 0& e^{{\lambda }_3}\end{array}\right){}_{\mathcal{C}}{T}_{\mathcal{B}}.$$

The critical piece of the calculation above is the cancellation ${}_{\mathcal{B}}{T}_{\mathcal{C}}^{-1}{}_{\mathcal{B}}{T}_{\mathcal{C}}=I_3$ occurring in the calculation for $A^2$. This cancellation shows that matrix multiplication and change of basis can be performed in either order. That in turn means we can first change basis to an eigenbasis (if it exists) and then perform multiplication with the diagonal matrices where it is easy, and only afterwards change back to the standard basis.

Singular vectors
The concept of singular vector is designed to make use of aspect (1) of eigenvectors without aspect (2). Because they do not include aspect (2), singular vectors of $A$ are not eigenvectors of $A$ except in special cases. They do not determine fixed lines of the $A$ action.

Unlike eigenvectors and eigenvalues, singular vectors and singular values are (best) defined in the context of a collection of vectors giving the singular value decomposition (SVD). So, a singular vector is one of the vectors in the SVD.

Defining the singular value decomposition

Suppose $A:{\mathbb{R}}^n\to {\mathbb{R}}^m$ is a matrix providing a linear transformation between different vector spaces.

SVD features

A singular value decomposition of $A:{\mathbb{R}}^n\to {\mathbb{R}}^m$ is given by: $A=U\Sigma V^{\mathsf{T}},$ where:

• $V=\left(\begin{array}{cccc}{\mathbf{v}}_1& {\mathbf{v}}_2& \cdots & {\mathbf{v}}_n\end{array}\right)$ is an orthogonal matrix giving a rotation/reflection combo for ${\mathbb{R}}^n$ (input)
• $U=\left(\begin{array}{cccc}{\mathbf{u}}_1& {\mathbf{u}}_2& \cdots & {\mathbf{u}}_m\end{array}\right)$ is an orthogonal matrix giving a rotation/reflection combo for ${\mathbb{R}}^m$ (output)
• $\Sigma$ has non-negative entries ${\sigma }_1,{\sigma }_2,\dots {\sigma }_{\ell }$ on the main diagonal (possibly zeros!) and zeros elsewhere. (Here $\ell =\min \{n,m\}$.) It is not square if $n\ne m$. It could look like these, for example: $$\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 3& 0& 0\\ 0& 0& 7& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right),\left(\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0& 3& 0& 0& 0& 0\\ 0& 0& 7& 0& 0& 0\end{array}\right).$$

The orthonormal basis vectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ are called right singular vectors.
The orthonormal basis vectors ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_m$ are called left singular vectors.
The values ${\sigma }_i\ge 0$ are the lengths of the images, namely ${\sigma }_i=|A{\mathbf{v}}_i|$.

(Remember: “Right $=$ Input, Left $=$ Output.”)

An alternate way to write the SVD uses scalar projections ${\mathbf{v}}_i^{\mathsf{T}}$ attached to the vectors ${\mathbf{u}}_i$:

$$A={\sigma }_1{\mathbf{u}}_1{\mathbf{v}}_1^{\mathsf{T}}+{\sigma }_2{\mathbf{u}}_2{\mathbf{v}}_2^{\mathsf{T}}+\cdots +{\sigma }_{\ell }{\mathbf{u}}_{\ell }{\mathbf{v}}_{\ell }^{\mathsf{T}}.$$

Each term ${\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^{\mathsf{T}}$ takes an input vector, dots it with ${\mathbf{v}}_i$, then applies this value to ${\mathbf{u}}_i$ scaled by ${\sigma }_i$. With this formula, we can compute $A\mathbf{x}$ for any input $\mathbf{x}$ using dot products:

$$A\mathbf{x}={\sigma }_1{\mathbf{u}}_1({\mathbf{v}}_1\cdot \mathbf{x})+{\sigma }_2{\mathbf{u}}_2({\mathbf{v}}_2\cdot \mathbf{x})+\cdots +{\sigma }_{\ell }{\mathbf{u}}_{\ell }({\mathbf{v}}_{\ell }\cdot \mathbf{x}).$$

By plugging in $\mathbf{x}={\mathbf{v}}_i$, we verify that $A{\mathbf{v}}_1={\sigma }_1{\mathbf{u}}_1$ and $A{\mathbf{v}}_2={\sigma }_2{\mathbf{u}}_2$, etc. up to $A{\mathbf{v}}_{\ell }={\sigma }_{\ell }{\mathbf{u}}_{\ell }$. (For $\ell <i\le n$, we have $A{\mathbf{v}}_i=0$.)

Singular vectors vs. eigenvectors

The rule $A{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i$ looks analogous to the rule for eigenvectors.

But it’s actually very different! Notice that ${\mathbf{v}}_i$ and ${\mathbf{u}}_i$ are not even vectors in the same space!

The rule $A\mathbf{v}=\sigma \mathbf{u}$ does not by itself determine any special property of $\mathbf{v}$ or $\mathbf{u}$. (Take any unit vector $\mathbf{v}$, apply $A$, then define $\sigma =|A\mathbf{v}|$ and $\mathbf{u}={\sigma }^{-1}A\mathbf{v}$.)

The significance of the rule $A{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i$ manifests when it holds simultaneously on all vector pairs in orthonormal bases ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ and ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_m$.

Still, the SVD says that after rotating / reflecting the basis of ${\mathbb{R}}^n$ and the basis of ${\mathbb{R}}^m$ by suitable orthogonal matrices (not necessarily the same on each), the action of $A$ can be represented as simple scalings by ${\sigma }_i$.

We may think of ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ as a special basis for the input space ${\mathbb{R}}^n$ vis-à-vis the matrix $A$, and ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_m$ as a corresponding basis for the output space ${\mathbb{R}}^m$. Then $A$ acts by pairing the vector ${\mathbf{v}}_i$ to ${\mathbf{u}}_i$ and stretching it by ${\sigma }_i$.

Partial matrices ${\mathbf{u}}_i{\mathbf{v}}_i^{\mathsf{T}}$ for $i=1,\dots ,5$.

Partial sum matrices ${\sigma }_1{\mathbf{u}}_1{\mathbf{v}}_1^{\mathsf{T}}+\cdots +{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^{\mathsf{T}}$ for $i=1,\dots ,5$.

Computing the singular value decomposition

In practice, on a computer, the SVD is calculated using numerical procedures that are akin to those used to find approximations to eigenvectors. We do not address those kinds of procedures in this course.

Still, it is possible to specify and calculate SVD elements by hand for a matrix $A$ by making use of the fact that $A^{\mathsf{T}}A$ is always a symmetric matrix and the Spectral Theorem can be applied to it. This method also shows that the SVD always exists, since the symmetric $A^{\mathsf{T}}A$ always has real eigenvalues and enough eigenvectors by the Spectral Theorem, even when $A$ does not. Let us see how this works.

First observe that $(A^{\mathsf{T}}A{)}^{\mathsf{T}}=A^{\mathsf{T}}(A^{\mathsf{T}}{)}^{\mathsf{T}}=A^{\mathsf{T}}A$, so $A^{\mathsf{T}}A$ is always symmetric. Also notice that $A^{\mathsf{T}}A:{\mathbb{R}}^n\to {\mathbb{R}}^n$, so the input and output spaces of this matrix are the same.

SVD elements

• ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n=$ orthonormal eigenbasis of $A^{\mathsf{T}}A$.
  As guaranteed by the Spectral Theorem, so $V$ here is $Q$ in the notation of that theorem.
• ${\sigma }_i=|A{\mathbf{v}}_i|$ defined for $1\le i\le \ell$.
  If $\left(A^{\mathsf{T}}A\right){\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$, then ${\sigma }_i=\sqrt{{\lambda }_i}$.
• The equation ${\sigma }_i{\mathbf{u}}_i=A{\mathbf{v}}_i$ for $1\le i\le \ell$ defines unit vectors ${\mathbf{u}}_i$ for those $i$ with ${\sigma }_i\ne 0$.
• Gram-Schmidt provides additional ${\mathbf{u}}_i$ vectors when ${\sigma }_i=0$.

Computing the singular value decomposition (part 2)

Explaining the SVD elements

First, why is $V=\left(\begin{array}{ccc}{\mathbf{v}}_1& \dots & {\mathbf{v}}_n\end{array}\right)$ an orthogonal matrix?
Answer: Since ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ is an orthonormal basis, the matrix $V$ is orthogonal.
Second, why is $U=\left(\begin{array}{ccc}{\mathbf{u}}_1& \dots & {\mathbf{u}}_m\end{array}\right)$ an orthogonal matrix?
Answer: Consider the calculation:

$$\begin{array}{rl}⟨A{\mathbf{v}}_i,A{\mathbf{v}}_j⟩& =(A{\mathbf{v}}_i{)}^{\mathsf{T}}A{\mathbf{v}}_j\\ & ={\mathbf{v}}_i^{\mathsf{T}}{A}^{\mathsf{T}}A{\mathbf{v}}_j\\ & ={\mathbf{v}}_i^{\mathsf{T}}(A^{\mathsf{T}}A{\mathbf{v}}_j)\\ & ={\mathbf{v}}_i^{\mathsf{T}}({\lambda }_j{\mathbf{v}}_j)\\ & ={\lambda }_j({\mathbf{v}}_i^{\mathsf{T}}{\mathbf{v}}_j)\\ & =\{\begin{array}{ll}{\lambda }_j& i=j\\ 0& i\ne j.\end{array}\end{array}$$

Notes: The first line is the dot product using ‘inner product’ notation. The second line is the transpose rule. The fourth line is the definition of ${\mathbf{v}}_j$ as eigenvector of $A^{\mathsf{T}}A$. The last line is the property that ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ are orthonormal vectors.

From this calculation it follows that $A{\mathbf{v}}_1,\dots ,A{\mathbf{v}}_n$ are orthogonal vectors (at least when they aren’t zero). Since ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_m$ are the same vectors renormalized as unit vectors, we know ${\mathbf{u}}_1,\dots {\mathbf{u}}_m$ are orthonormal (at least when ${\sigma }_i\ne 0$). In the case of ${\sigma }_i=|A{\mathbf{v}}_i|=0$, the alternate definition of ${\mathbf{u}}_i$ using Gram-Schmidt implies that all ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_m$ are orthonormal.

Third, why is ${\sigma }_i=\sqrt{{\lambda }_i}$?
Answer: According to the calculation above, $|A{\mathbf{v}}_i{|}^2={\lambda }_i$. But $|A{\mathbf{v}}_i|={\sigma }_i$ by definition.

Fourth, why is $A=U\Sigma V^{\mathsf{T}}$, with these definitions of $U,\Sigma ,V$?
Answer: To verify the equality $A=U\Sigma V^{\mathsf{T}}$, it is sufficient to verify that the matrices on both sides have the same action on a basis of ${\mathbb{R}}^n$. (If that is true, then by linearity the matrices have the same action on any vector, and therefore they are the same matrices.)

Therefore, it is sufficient to verify the equality of actions on the basis ${\mathbf{v}}_1,\dots {\mathbf{v}}_n$. Since this basis is orthonormal, we see that $V^{\mathsf{T}}{\mathbf{v}}_i$ is the vector with $1$ in the $i^{\text{th}}$ row and zeros elsewhere. Then $\Sigma \left(V^{\mathsf{T}}{\mathbf{v}}_i\right)$ is the $i^{\text{th}}$ column of $\Sigma$, which has ${\sigma }_i$ in the $i^{\text{th}}$ row and zeros elsewhere. Finally $U\left(\Sigma V^{\mathsf{T}}{\mathbf{v}}_i\right)$ is the $i^{\text{th}}$ row of $U$ (which is ${\mathbf{u}}_i$) scaled by ${\sigma }_i$. Therefore $\left(U\Sigma V^{\mathsf{T}}\right){\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i$, and this is equal to $A{\mathbf{v}}_i$. All these statements are valid for $i=1,\dots ,\ell$. For $\ell <i$, both sides send ${\mathbf{v}}_i$ to $0$.

Backwards: Going from SVD to eigenvectors-eigenvalues of $A^{\mathsf{T}}A$

Addendum. If we already have an SVD given by $A=U\Sigma V^{\mathsf{T}}$, with ${\sigma }_1,\dots ,{\sigma }_{\ell }$ on the diagonal of $\Sigma$, then ${\mathbf{v}}_1,\dots {\mathbf{v}}_n$ must be the eigenvectors of $A^{\mathsf{T}}A$, and ${\sigma }_1^2,\dots ,{\sigma }_{\ell }^2,0,\dots ,0$ are the corresponding eigenvalues.

Proof: Observe that

$$\begin{array}{rl}{A}^{\mathsf{T}}A& =(V^{\mathsf{T}}{)}^{\mathsf{T}}{\Sigma }^{\mathsf{T}}{U}^{\mathsf{T}}U\Sigma V^{\mathsf{T}}\\ & =V{\Sigma }^{\mathsf{T}}{I}_n\Sigma V^{\mathsf{T}}\\ & =V{\Sigma }^{\mathsf{T}}\Sigma V^{\mathsf{T}}\\ & =V{\Sigma }^{\prime }{V}^{\mathsf{T}},\end{array}$$

where ${\Sigma }^{\prime }$ is the square diagonal matrix with diagonal entries given by ${\sigma }_1^2,\dots ,{\sigma }_{\ell }^2$. Applying the matrix $A{\Sigma }^{\prime }{V}^{\mathsf{T}}$ to ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_{\ell }$ returns ${\sigma }_1^2{\mathbf{v}}_1,\dots ,{\sigma }_{\ell }{\mathbf{v}}_{\ell }$, which verifies the claim. (Again both matrices send ${\mathbf{v}}_i$ to $0$ for $\ell <i\le n$.)