Chapter 06 - Inner Products and Spectrum

Matrices III: Inner Products

Introduction

In this section we study some interrelated concepts: orthogonal matrices, symmetric matrices, inner products, quadratic forms, and positive definite matrices.

Link to original

Orthogonal matrices

Orthogonal matrices

A matrix $Q$ is called orthogonal when it satisfies $A^{\mathsf{T}}A=I_n$.

‘Orthogonal’ $=$ ‘orthonormal’ for matrices

The term orthonormal is also used for the same class of matrices. (Warning! Not so for vectors! Orthogonal vectors are merely perpendicular, while orthonormal vectors are also unit vectors.)

Now consider the meaning of the formula $Q^{\mathsf{T}}Q=I_n$. Remember the rule for matrix products (e.g. in $3$D):

$$BA=\left(\begin{array}{ccc}B{\mathbf{a}}_1& B{\mathbf{a}}_2& B{\mathbf{a}}_3\end{array}\right).$$

What is $Q^{\mathsf{T}}{\mathbf{q}}_i$? Each row of this vector is the dot product of the same row of $Q^{\mathsf{T}}$ with the vector ${\mathbf{q}}_i$. In turn, each row of $Q^{\mathsf{T}}$ is from a column of $Q$. Combining all these claims with the product rule, column $i$ of $Q^{\mathsf{T}}Q$ has rows equal to the dot products of the various columns of $Q$ with the specific column $i$ of $Q$. Specifically, $(Q^{\mathsf{T}}Q{)}_{ij}={\mathbf{q}}_j\cdot {\mathbf{q}}_i$. In conclusion, $Q^{\mathsf{T}}Q=I_n$ means that ${\mathbf{q}}_j\cdot {\mathbf{q}}_i=\{\begin{array}{ll}1& i=j\\ 0& i\ne j.\end{array}$

It follows that $Q^{\mathsf{T}}Q=I_n$ is another way of saying that ${\mathbf{q}}_j$ and ${\mathbf{q}}_i$ are mutually orthonormal. So, if you put an orthonormal basis into the column vectors of a matrix, the resulting matrix is orthogonal. Conversely, if a matrix is orthogonal, then its columns form an orthonormal basis. (They are orthonormal by the definition of orthogonal, and they are a basis because they are perpendicular and thus independent.)

An important fact about orthogonal matrices is that they correspond geometrically to rotations and reflections (and combinations of these actions called ‘rotoreflections’).

Orthogonal matrices preserve the dot product, preserving lengths and angles

The action of an orthogonal matrix preserves the dot product:

$$(Q\mathbf{u})\cdot (Q\mathbf{v})=\mathbf{u}\cdot \mathbf{v}.$$

Why $(Q\mathbf{u})\cdot (Q\mathbf{v})=\mathbf{u}\cdot \mathbf{v}$

To see this, recall (1) our interpretation of row vectors as $1\times n$ matrices, and (2) the dot product with $\mathbf{x}$ as the action of the transpose row vector ${\mathbf{x}}^{\mathsf{T}}$ acting by matrix multiplication on the left, so e.g. $\mathbf{x}\cdot \mathbf{w}={\mathbf{x}}^{\mathsf{T}}\mathbf{w}$. Using this, we derive:

$$\begin{array}{rl}(Q\mathbf{u})\cdot (Q\mathbf{v})& =(Q\mathbf{u}{)}^{\mathsf{T}}(Q\mathbf{v})\\ & =({\mathbf{u}}^{\mathsf{T}}{Q}^{\mathsf{T}})(Q\mathbf{v})\\ & ={\mathbf{u}}^{\mathsf{T}}(Q^{\mathsf{T}}Q)\mathbf{v}\\ & ={\mathbf{u}}^{\mathsf{T}}(I_n)\mathbf{v}\\ & ={\mathbf{u}}^{\mathsf{T}}\mathbf{v}\\ & =\mathbf{u}\cdot \mathbf{v}.\end{array}$$

Link to original

Symmetric matrices

Symmetric matrices

A symmetric matrix $A$ is a matrix that satisfies $A^{\mathsf{T}}=A$. In terms of coefficients, this means it satisfies $a_{ij}=a_{ji}$. A symmetric matrix is symmetric about reflection in a mirror that runs down the main diagonal:

$$\text{Non-symmetric:}\left(\begin{array}{cc}1& 2\\ 3& 4\end{array}\right),\left(\begin{array}{cc}1& 2\\ -2& 1\end{array}\right)$$ $$\text{Symmetric:}\left(\begin{array}{cc}1& 3\\ 3& -2\end{array}\right),\text{antisymmetric:}\left(\begin{array}{cc}0& 3\\ -3& 0\end{array}\right)$$

An antisymmetric matrix (also called skew-symmetric) satisfies $A^{\mathsf{T}}=-A$, in other words $a_{ij}=-a_{ji}$.

Symmetric matrices do arise naturally in many applications. This can happen for a variety of reasons. One example is PCA (principal component analysis): here the matrix in question arises as a “covariance matrix,” and it is symmetric because covariance is symmetric: $\mathrm{Cov}(X,Y)=\mathrm{Cov}(Y,X)$. Antisymmetric matrices are less common.

Symmetric matrices have some very nice properties:

Spectral theorem

Let $A$ be any $n\times n$ symmetric matrix, so $A^{\mathsf{T}}=A$. Then:

• (a) $A$ has the max number of $n$ eigenvalues (some might be repeated, but they still exist).
• (b) All eigenvalues of $A$ are real numbers.
• (c) Eigenvectors with distinct eigenvalues are perpendicular to each other.
• (d) There is an orthonormal basis $\mathcal{Q}=\{{\mathbf{q}}_1,\dots ,{\mathbf{q}}_n\}$ such that $A$ becomes diagonal in this basis: $$D=Q^{-1}AQ,\text{ where }Q=\left(\begin{array}{ccc}{\mathbf{q}}_1& \cdots & {\mathbf{q}}_n\end{array}\right)={}_{\mathcal{B}}{T}_{\mathcal{Q}}$$ in other words $A=QD{Q}^{-1}$. Notice that $Q$ is an orthogonal matrix, and ${\mathbf{q}}_i$ are eigenvectors of $A$.

Proofs of most of these facts are just a little beyond the scope of a first applied course. Part (c) is not hard though:

Orthogonal eigenvectors of a symmetric matrix

Suppose $A{\mathbf{q}}_1={\lambda }_1{\mathbf{q}}_1$ and $A{\mathbf{q}}_2={\lambda }_2{\mathbf{q}}_2$ and ${\lambda }_1\ne {\lambda }_2$. Assume, as we do for eigenvectors, that ${\lambda }_1\ne 0$. Then consider the sequence:

$$\begin{array}{rl}{\mathbf{q}}_1\cdot {\mathbf{q}}_2& ={\lambda }_1^{-1}({\lambda }_1{\mathbf{q}}_1\cdot {\mathbf{q}}_2)\\ & ={\lambda }_1^{-1}(A{\mathbf{q}}_1)\cdot {\mathbf{q}}_2\\ & ={\lambda }_1^{-1}(A{\mathbf{q}}_1{)}^{\mathsf{T}}{\mathbf{q}}_2\\ & ={\lambda }_1^{-1}({\mathbf{q}}_1^{\mathsf{T}}{A}^{\mathsf{T}}){\mathbf{q}}_2\\ & ={\lambda }_1^{-1}{\mathbf{q}}_1^{\mathsf{T}}(A{\mathbf{q}}_2)\\ & ={\lambda }_1^{-1}{\mathbf{q}}_1^{\mathsf{T}}({\lambda }_2{\mathbf{q}}_2)\\ & =({\lambda }_1^{-1}{\lambda }_2){\mathbf{q}}_1^{\mathsf{T}}{\mathbf{q}}_2\\ & =({\lambda }_1^{-1}{\lambda }_2){\mathbf{q}}_1\cdot {\mathbf{q}}_2.\end{array}$$

Therefore, we find that ${\mathbf{q}}_1\cdot {\mathbf{q}}_2=({\lambda }_1^{-1}{\lambda }_2){\mathbf{q}}_1\cdot {\mathbf{q}}_2$. This can only happen if ${\lambda }_1={\lambda }_2$, which we have denied by hypothesis, or else if ${\mathbf{q}}_1\cdot {\mathbf{q}}_2=0$, which must therefore be true.

The equation $A=QD{Q}^{\mathsf{T}}$ is equivalent to a very nice formula for $A$ called the spectral decomposition formula:

$$A={\lambda }_1({\mathbf{q}}_1{\mathbf{q}}_1^{\mathsf{T}})+{\lambda }_2({\mathbf{q}}_2{\mathbf{q}}_2^{\mathsf{T}})+\cdots +{\lambda }_n({\mathbf{q}}_n{\mathbf{q}}_n^{\mathsf{T}}).$$

In this formula, the ${\mathbf{q}}_i$ are the orthogonal basis given by the spectral theorem (remember they are also eigenvectors), and the ${\lambda }_i$ are the corresponding eigenvalues.

SVD prelude

The spectral decomposition is an instance of the singular value decomposition (SVD) which works for general matrices. Stay tuned for more in the section on the SVD!

A great thing about this formula is that each ${\mathbf{q}}_i{\mathbf{q}}_i^{\mathsf{T}}$ is actually a projection matrix onto ${\mathbf{q}}_i$:

$${\mathbf{q}}_i{\mathbf{q}}_i^{\mathsf{T}}=[{\mathrm{proj}}_{{\mathbf{q}}_i}].$$

Why? Of course ${\mathbf{q}}_i{\mathbf{q}}_i^{\mathsf{T}}\mathbf{v}={\mathbf{q}}_i({\mathbf{q}}_i\cdot \mathbf{v})$. Since ${\mathbf{q}}_i$ are unit vectors, we have ${\mathrm{proj}}_{{\mathbf{q}}_i}(\mathbf{v})=(\mathbf{v}\cdot {\mathbf{q}}_i){\mathbf{q}}_i$. This is the same thing, just written with a different order for the scalar factor (result of the dot product).

[Optional] Explaining the spectral decomposition formula

The spectral decomposition formula itself comes from writing out the matrices in $A=QD{Q}^{\mathsf{T}}$:

$$\begin{array}{rl}A=QD{Q}^{\mathsf{T}}& =\left(\begin{array}{ccc}{\mathbf{q}}_1& \cdots & {\mathbf{q}}_n\end{array}\right)\left(\begin{array}{ccc}{\lambda }_1& & 0\\ & \ddots & \\ 0& & {\lambda }_n\end{array}\right)\left(\begin{array}{c}{\mathbf{q}}_1^{\mathsf{T}}\\ ⋮\\ {\mathbf{q}}_n^{\mathsf{T}}\end{array}\right)\\ & =\left(\begin{array}{ccc}{\mathbf{q}}_1& \cdots & {\mathbf{q}}_n\end{array}\right)\left(\begin{array}{c}{\lambda }_1{\mathbf{q}}_1^{\mathsf{T}}\\ ⋮\\ {\lambda }_n{\mathbf{q}}_n^{\mathsf{T}}\end{array}\right)\\ & =\left(\begin{array}{ccc}{\mathbf{q}}_1& \cdots & {\mathbf{q}}_n\end{array}\right)\left(\left(\begin{array}{c}{\lambda }_1{\mathbf{q}}_1^{\mathsf{T}}\\ 0\\ ⋮\\ 0\end{array}\right)+\left(\begin{array}{c}0\\ {\lambda }_2{\mathbf{q}}_2^{\mathsf{T}}\\ ⋮\\ 0\end{array}\right)+\left(\begin{array}{c}0\\ 0\\ ⋮\\ {\lambda }_n{\mathbf{q}}_n^{\mathsf{T}}\end{array}\right)\right)\\ & ={\mathbf{q}}_1{\lambda }_1{\mathbf{q}}_1^{\mathsf{T}}+\cdots +{\mathbf{q}}_n{\lambda }_n{\mathbf{q}}_n^{\mathsf{T}}\\ & ={\lambda }_1({\mathbf{q}}_1{\mathbf{q}}_1^{\mathsf{T}})+{\lambda }_2({\mathbf{q}}_2{\mathbf{q}}_2^{\mathsf{T}})+\cdots +{\lambda }_n({\mathbf{q}}_n{\mathbf{q}}_n^{\mathsf{T}}).\end{array}$$

Link to original

Quadratic forms and symmetric matrices

Quadratic forms and symmetric matrices

A quadratic form is a function $Q:{\mathbb{R}}^n\to \mathbb{R}$ from vectors to scalars that can be written as a polynomial with all terms having degree $2$. For example:

$$\begin{array}{rl}& \text{In }2\mathrm{D}:Q(\left(\begin{array}{c}x\\ y\end{array}\right))=a{x}^2+b{y}^2+cxy\\ & \text{In }3\mathrm{D}:Q(\left(\begin{array}{c}x\\ y\\ z\end{array}\right))=a{x}^2+b{y}^2+c{z}^2+dxy+exz+fyz\end{array}$$

In short, a quadratic form is just a polynomial in several variables that is homogeneous of degree $2$. (‘Homogeneous’ just means that all terms have the same degree.) The difference between quadratic forms and quadratic polynomials is that the latter could also have terms of degree zero and degree one.

Applications of quadratic forms

The simplest possible quadratic form is the sum of squares: $Q(x,y,z)=x^2+y^2+z^2$. Notice that this form gives the square distance from $(x,y,z)$ to $(0,0,0)$. One strong application of linear algebra is the ability to extremize quadratric forms. For example, in Linear Least Squares, we extremize the distance from a point to a certain span. We will shortly see how to represent this distance as a quadratic form. In Weighted LLS, we minimize the distance with inequal weights applied to each term, such as in $Q(x,y,z)=4x^2+y^2+9z^2$. This kind of weighting is useful when some data is more reliable than other data, so it should be given more weight.

Link to original

Question

[Removed!]

Quadratic forms and symmetric matrices (part 2)

Key fact:

Matrix of a quadratic form

Every quadratic form $Q$ can be represented uniquely by a symmetric matrix, meaning there is some symmetric $A$ such that $Q(\mathbf{x})={\mathbf{x}}^{\mathsf{T}}A\mathbf{x}$.

So there is a perfect correspondence between quadratic forms and symmetric matrices.

Link to original

Example

Quadratic form

Quadratic form

$$\begin{array}{rl}Q(\mathbf{x})={\mathbf{x}}^{\mathsf{T}}A\mathbf{x}& =\left(\begin{array}{ccc}{x}_1& x_2& x_3\end{array}\right)\left(\begin{array}{ccc}5& -1/2& 0\\ -1/2& 3& 4\\ 0& 4& 2\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)\\ & \\ & =5x_1^2+3x_2^2+2x_3^2-x_1{x}_2+8x_2{x}_3.\end{array}$$

Link to original

Question

01

Matrix of a quadratic form

What is the matrix $A$ such that $Q(\mathbf{x})=3x_1^2+7x_2^2-4x_1{x}_2$ is the quadratic form $Q(\mathbf{x})={\mathbf{x}}^{\mathsf{T}}A\mathbf{x}$?

Link to original

Quadratic forms and symmetric matrices (part 3)

A quadratic form can always be converted into a new quadratic form that has no cross terms by a suitable linear change of variables. If the original variables are the components of $\mathbf{x}$, then a linear change of variables would be a vector $\mathbf{y}$ defined by $\mathbf{y}={}_{{\mathcal{B}}^{\prime }}{T}_{\mathcal{B}}(\mathbf{x})$ for some change of basis transfer matrix ${}_{{\mathcal{B}}^{\prime }}{T}_{\mathcal{B}}$.

Principal axes theorem: eliminating cross terms

Given a quadratic form $Q(\mathbf{x})$ defined by the symmetric matrix $A$, suppose $A=PD{P}^{\mathsf{T}}$. Set $\mathbf{y}=P^{\mathsf{T}}\mathbf{x}$, so also $\mathbf{x}=P\mathbf{y}$. Then $Q(P\mathbf{y})$ has no cross terms in the $\mathbf{y}$ variables.

Derivation

First plug in the new variables and manipulate:

$${\mathbf{x}}^{\mathsf{T}}A\mathbf{x}=(P\mathbf{y}{)}^{\mathsf{T}}A(P\mathbf{y})={\mathbf{y}}^{\mathsf{T}}(P^{\mathsf{T}}AP)\mathbf{y}={\mathbf{y}}^{\mathsf{T}}D\mathbf{y}$$

This last expression has no cross terms:

$$\begin{array}{rl}{\mathbf{y}}^{\mathsf{T}}D\mathbf{y}& =\left(\begin{array}{ccc}{y}_1& \cdots & y_n\end{array}\right)\left(\begin{array}{ccc}{\lambda }_1& & 0\\ & \ddots & \\ 0& & {\lambda }_n\end{array}\right)\left(\begin{array}{c}{y}_1\\ ⋮\\ y_n\end{array}\right)\\ & \\ & ={\lambda }_1{y}_1^2+\cdots +{\lambda }_n{y}_n^2.\end{array}$$

Link to original

Example

Eliminating cross terms

Eliminating cross terms

Problem: Eliminate the cross terms in the quadratic form $Q(\mathbf{x})=2x_1^2+6x_1{x}_2-6x_2^2$.

Solution: First compute the matrix of $Q$. By reading off the components (dividing in half the cross term), we see

$$A=\left(\begin{array}{cc}2& 3\\ 3& -6\end{array}\right).$$

Now we must write $A=PD{P}^{\mathsf{T}}$ for $P$ an orthogonal matrix. We find the eigenvalues and then seek eigenvectors that are orthonormal. Observe that $\det A_{\lambda }={\lambda }^2+4\lambda -21=(\lambda +7)(\lambda -3)$, so the eigenvalues are $\lambda =-7,3$.

Then we have:

$$A_{-7}=\left(\begin{array}{cc}2--7& 3\\ 3& -6--7\end{array}\right)=\left(\begin{array}{cc}9& 3\\ 3& 1\end{array}\right)$$

so $3x_1+x_2=0$ gives the relation satisfied by the rows of an eigenvector. Choose $\left(\begin{array}{c}1\\ -3\end{array}\right)$ and then normalize this to the unit vector ${\mathbf{v}}_{-7}=\left(\begin{array}{c}1/\sqrt{10}\\ -3/\sqrt{10}\end{array}\right)$.

Then we also have:

$$A_3=\left(\begin{array}{cc}2-3& 3\\ 3& -6-3\end{array}\right)=\left(\begin{array}{rc}-1& 3\\ 3& -9\end{array}\right)$$

so $-x_1+3x_2=0$ and we choose $\left(\begin{array}{c}3\\ 1\end{array}\right)$ as an eigenvector, and normalize to the unit vector ${\mathbf{v}}_3=\left(\begin{array}{c}3/\sqrt{10}\\ 1/\sqrt{10}\end{array}\right)$. Notice that ${\mathbf{v}}_{-7}\cdot {\mathbf{v}}_3=0$.

Now we set ${\mathbf{q}}_1={\mathbf{v}}_{-7}$ and ${\mathbf{q}}_2={\mathbf{v}}_3$ and write our expression for $A$:

$$\begin{array}{rl}A& =\left(\begin{array}{cc}2& 3\\ 3& -6\end{array}\right)=PD{P}^{\mathsf{T}}\\ & =\left(\begin{array}{cc}1/\sqrt{10}& 3/\sqrt{10}\\ -3/\sqrt{10}& 1/\sqrt{10}\end{array}\right)\left(\begin{array}{rc}-7& 0\\ 0& 3\end{array}\right)\left(\begin{array}{cc}1/\sqrt{10}& -3/\sqrt{10}\\ 3/\sqrt{10}& 1/\sqrt{10}\end{array}\right).\end{array}$$

In terms of the $\mathbf{y}$ variables, we have $Q(\mathbf{x})=Q(P\mathbf{y})=-7y_1^2+3y_2^2$. The formulas relating the variables to each other are given by interpreting $P^{\mathsf{T}}$ as the change of variable transfer matrix:

$$\begin{array}{rl}{y}_1& =\frac{1}{\sqrt{10}}{x}_1-\frac{3}{\sqrt{10}}{x}_2\\ y_2& =\frac{3}{\sqrt{10}}{x}_1+\frac{1}{\sqrt{10}}{x}_2.\end{array}$$

Link to original

Exercise

01

Eliminating cross terms.

Repeat the example to eliminate cross terms for the quadratic form $Q(\mathbf{x})=2x_1^2-4x_1{x}_2-x_2^2$.

Link to original

Constrained optimization, min-max principle

Constrained optimization, min-max principle

One simple yet important application of elimination of cross terms is constrained optimization. The goal of constrained optimization is to find the extreme values of a quadratic form $Q(\mathbf{x})$ where $\mathbf{x}$ is constrained to be a unit vector, so ${\mathbf{x}}^{\mathsf{T}}\mathbf{x}=1$. Geometrically, this means: find the direction of fastest increase or direction of fastest decrease of $Q$, and find the rate of increase / decrease in those directions.

If we have written $Q(\mathbf{y})$ so as to eliminate cross terms:

$$Q(\mathbf{y})={\lambda }_1{y}_1^2+\cdots +{\lambda }_n{y}_n^2$$

then the max / min of $Q$ occurs for $\mathbf{y}={\mathbf{e}}_i$ where ${\lambda }_i$ is the max / min coefficient.

If $Q(\mathbf{x})$ is not written without cross terms, then we can first eliminate cross terms completely, and find the max / min among the set of ${\lambda }_i$. This will give the max / min value, and the input where this occurs in terms of the $y$ variables at $\mathbf{y}={\mathbf{e}}_i$. The change of variables must be made in reverse to find the corresponding $x$ input values where the max / min occurs. If the eigenvector ${\mathbf{q}}_i$ corresponding to ${\lambda }_i$ has already been found, its components are by definition the components of $P{\mathbf{e}}_i$ that we seek.

Link to original

Example

Optimizing the quadratic form from the eliminating cross terms example

Optimizing $Q(\mathbf{x})=2x_1^2+6x_1{x}_2-6x_2^2$

In the Example of the previous section on eliminating cross terms, we obtained the formula $-7y_1^2+3y_2^2$ for $Q$ in terms of the variables $y_1,y_2$. We can see directly from this formula that the min eigenvalue is $-7$ and the max eigenvalue is $3$.

The min of $-7$ occurs when $y_1=1,y_2=0$. In other words it is at the first eigenvector ${\mathbf{q}}_1$. In terms of the $x_1,x_2$ variables, this occurs at $x_1=1/\sqrt{10}$ and $x_2=-3/\sqrt{10}$, the components of ${\mathbf{q}}_1={\mathbf{v}}_{-7}$ in the standard basis.

The max of $3$ occurs when $y_1=0,y_2=1$. In other words at ${\mathbf{q}}_2$, which corresponds to $x_1=3/\sqrt{10}$ and $x_2=1/\sqrt{10}$.

Link to original

Exercise

02

Optimizing $Q(\mathbf{x})=2x_1^2-4x_1{x}_2-x_2^2$

Repeat the example on this quadratic form, using your work in Exercise 12-01, to find the min and max of $Q(\mathbf{x})=2x_1^2-4x_1{x}_2-x_2^2$ for $\mathbf{x}$ a unit vector, and find the unit vectors that produce these extreme values.

Link to original

Constrained optimization, min-max principle (part 2)

However, it is not necessary to find all of the ${\lambda }_i$. These ${\lambda }_i$ are the eigenvalues / eigenvectors, and there are some methods of computing eigenvalues that locate the largest / smallest values by a numerical procedure that does not waste time finding the other values. The power method is an example of such a method. (Read more about the power method online, if you like.)

Min-max principle and Rayleigh quotient

A closely related topic is the min-max principle for finding eigenvalues using the Rayleigh quotient. Given any symmetric matrix $A$, its Rayleigh quotient is:

$$R(A,\mathbf{x})=\frac{{\mathbf{x}}^{\mathsf{T}}A\mathbf{x}}{{\mathbf{x}}^{\mathsf{T}}\mathbf{x}}.$$

Notice that the value of $R(A,\mathbf{x})$ is the same as the value of the quadratic form generated by $A$, evaluated at the unit vector given by first normalizing the input $\mathbf{x}$. Therefore, maximizing $R(A,\mathbf{x})$ over all possible $\mathbf{x}\ne 0$ is the same as maximizing the quadratic form of $A$ over all possible unit vectors.

The min-max principle is simply this: the min / max eigenvalues of $A$ are the min / max values of $R(A,\mathbf{x})$, and these occur when $\mathbf{x}$ is an eigenvector for that eigenvalue. The use of this principle is to find min / max eigenvalues / eigenvectors of a symmetric $A$ by extremizing $R(A,\mathbf{x})$ with numerical methods (like the power method and its variants).

The min-max principle and Rayleigh quotient is essentially just a notation and terminology for the process of normalizing $\mathbf{x}$ and plugging it into the quadratic form $Q$ arising from the symmetric matrix $A$.

Link to original

Positive definite symmetric matrices

Positive definite symmetric matrices

• A positive definite matrix is by definition a symmetric matrix all of whose eigenvalues are greater than zero.
• A negative definite matrix is by definition a symmetric matrix all of whose eigenvalues are less than zero.
• An indefinite matrix is by definition a symmetric matrix whose eigenvalues have mixed signs.

For example, in terms of spectral decompositions, we have:

$$\begin{array}{rl}A\text{ is positive definite:}A& =7{\mathbf{q}}_1{\mathbf{q}}_1^{\mathsf{T}}+{\mathbf{q}}_2{\mathbf{q}}_2^{\mathsf{T}}+3{\mathbf{q}}_3{\mathbf{q}}_3^{\mathsf{T}}\\ A\text{ is negative definite:}A& =-7{\mathbf{q}}_1{\mathbf{q}}_1^{\mathsf{T}}-{\mathbf{q}}_2{\mathbf{q}}_2^{\mathsf{T}}-3{\mathbf{q}}_3{\mathbf{q}}_3^{\mathsf{T}}\\ A\text{ is indefinite:}A& =7{\mathbf{q}}_1{\mathbf{q}}_1^{\mathsf{T}}-{\mathbf{q}}_2{\mathbf{q}}_2^{\mathsf{T}}+3{\mathbf{q}}_3{\mathbf{q}}_3^{\mathsf{T}}.\end{array}$$

Since the spectral decomposition reveals the quadratic form in the new variables, where ${\mathbf{q}}_i=P{\mathbf{e}}_i$, but these input variables cover the same set of possibilities, we also know:

Quadratic forms definiteness

• When $A$ is positive definite, then its form $Q(\mathbf{x})$ is always positive for $\mathbf{x}\ne 0$.
• When $A$ is negative definite, then its form $Q(\mathbf{x})$ is always negative for $\mathbf{x}\ne 0$.

Link to original

Inner products and symmetric matrices

Inner products and symmetric matrices

An inner product is a function sending two vector inputs to one scalar output:

$$⟨-,-⟩:(\mathbf{u},\mathbf{v})\mapsto ⟨\mathbf{u},\mathbf{v}⟩\in \mathbb{R},$$

which is linear in both inputs considered separately.

Rules of inner products:

• $⟨\mathbf{u},\mathbf{v}⟩=⟨\mathbf{v},\mathbf{u}⟩$ Symmetry.
• $⟨{\mathbf{u}}_1+{\mathbf{u}}_2,\mathbf{v}⟩=⟨{\mathbf{u}}_1,\mathbf{v}⟩+⟨{\mathbf{u}}_2,\mathbf{v}⟩$ Respects sums (also in $\mathbf{v}$ using symmetry).
• $⟨\lambda \mathbf{u},\mathbf{v}⟩=\lambda ⟨\mathbf{u},\mathbf{v}⟩$ Respects scalars (also in $\mathbf{v}$ using symmetry).
• $⟨\mathbf{u},\mathbf{u}⟩>0$ for all $\mathbf{u}\ne 0$, and $⟨\mathbf{u},\mathbf{u}⟩=0$ only occurs when $\mathbf{u}=0$.

We are very familiar with the dot product, which is a valid inner product:

$$\begin{array}{rl}⟨\mathbf{u},\mathbf{v}{⟩}_{\text{dot}}& =\mathbf{u}\cdot \mathbf{v}=\left(\begin{array}{c}{u}_1\\ u_2\\ u_3\end{array}\right)\cdot \left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)\\ & ={\mathbf{u}}^{\mathsf{T}}\mathbf{v}=\left(\begin{array}{ccc}{u}_1& u_2& u_3\end{array}\right)\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)\\ & =u_1{v}_1+u_2{v}_2+u_3{v}_3.\end{array}$$

Using the linearity of matrix actions, we can create many candidate inner products by first acting by a symmetric matrix $A=A^{\mathsf{T}}$ and then taking the usual dot product:

$$⟨\mathbf{u},\mathbf{v}{⟩}_A=⟨\mathbf{u},A\mathbf{v}{⟩}_{\text{dot}}=\mathbf{u}\cdot A\mathbf{v}.$$

This definition of $⟨\mathbf{u},\mathbf{v}{⟩}_A$ is automatically symmetric (i.e. it satisfies the symmetry rule) because $A$ is symmetric:

$$\begin{array}{rl}⟨\mathbf{u},\mathbf{v}{⟩}_A& ={\mathbf{u}}^{\mathsf{T}}A\mathbf{v}\\ & =({\mathbf{u}}^{\mathsf{T}}A\mathbf{v}{)}^{\mathsf{T}}({\lambda }^{\mathsf{T}}=\lambda \text{ for scalars})\\ & ={\mathbf{v}}^{\mathsf{T}}{A}^{\mathsf{T}}({\mathbf{u}}^{\mathsf{T}}{)}^{\mathsf{T}}\\ & ={\mathbf{v}}^{\mathsf{T}}A\mathbf{u}\\ & =⟨\mathbf{v},A\mathbf{u}{⟩}_A.\end{array}$$

If you take any inner product given by a symmetric matrix, and plug the input $\mathbf{x}$ into both slots, you get a quadratic form:

$$⟨\mathbf{x},\mathbf{x}{⟩}_A={\mathbf{x}}^{\mathsf{T}}A\mathbf{x}=Q(\mathbf{x}).$$

The last property of inner products (namely that $⟨\mathbf{u},\mathbf{u}⟩>0$ etc.) means that a quadratic form created in this way by setting $Q(\mathbf{x})=⟨\mathbf{x},\mathbf{x}{⟩}_A$ is always a positive definite quadratic form.

Conversely, any inner product is given by some positive definite symmetric matrix. To find the matrix corresponding to an inner product, simply set $a_{ij}=⟨{\mathbf{e}}_i,{\mathbf{e}}_j⟩$. This works because $A{\mathbf{e}}_j$ gives the $j^{\text{th}}$ column vector of $A$, and then ${\mathbf{e}}_i^{\mathsf{T}}A{\mathbf{e}}_j$ gives the $i^{\text{th}}$ row entry of this column, which is therefore the $i^{\text{th}}$ row and $j^{\text{th}}$ column entry of $A$. By linearity, $⟨\cdot ,\cdot ⟩$ is then determined on every other pair of vectors by this data.

Link to original

Addendum: determinants and eigenvectors

Addendum - determinants and eigenvectors

The determinant of a $2\times 2$ matrix is given by the formula:

$$A=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right),\det A=\left|\begin{array}{cc}a& b\\ c& d\end{array}\right|=ad-bc.$$

The determinant of a $3\times 3$ matrix is given by the formula:

$$A=\left(\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right),\det A=\left|\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right|=a\left|\begin{array}{cc}e& f\\ h& i\end{array}\right|-b\left|\begin{array}{cc}d& f\\ g& i\end{array}\right|+c\left|\begin{array}{cc}d& e\\ g& h\end{array}\right|.$$

Higher determinants

You may notice a pattern here that hold true in general and allows calculation of $n\times n$ determinants: traverse any row or column, using these entries as weights (with alternating signs), writing a weighted sum of the smaller determinants of the minor matrices (which are given by deleting the row and column in which the given entry in our traversal process lives). This process therefore reduces an $n\times n$ determinant to a linear combination of $(n-1)\times (n-1)$ determinants, and the reduction can be iterated until the $2\times 2$ case is reached.

The characteristic polynomial ${\mathrm{ch}}_A(\lambda )$ of a matrix $A$ is defined as the determinant $\det A_{\lambda }$ in which $\lambda$ is considered an indefinite variable.

For example: if $A=\left(\begin{array}{cc}1& -2\\ -4& -1\end{array}\right)$ then $A_{\lambda }=\left(\begin{array}{cc}1-\lambda & -2\\ -4& -1-\lambda \end{array}\right)$ and (using the determinant formula) we have:

$${\mathrm{ch}}_A(\lambda )=\left|\begin{array}{cc}1-\lambda & -2\\ -4& -1-\lambda \end{array}\right|=(1-\lambda )(-1-\lambda )-8={\lambda }^2-9.$$

Key fact for finding eigenvalues

The eigenvalues of a matrix $A$ are the roots of its characteristic polynomial ${\mathrm{ch}}_A(\lambda )$.

In the previous example, therefore, $\lambda =\pm 3$ are the eigenvalues.

Once the eigenvalues are found by solving ${\mathrm{ch}}_A(\lambda )=0$ for $\lambda$, the solutions can be plugged back in for $\lambda$ in the equation $A_{\lambda }\mathbf{x}=0$, and then we can try to find the eigenvectors $\mathbf{x}$ by solving this equation. For the $2\times 2$ case, you can solve it using the fact that one row is a multiple of the other. In $3\times 3$ and higher, you may need to perform row reduction on $A_{\lambda }$ (with $\lambda =\text{specific eigenvalue}$) in order to find solutions $\mathbf{x}$.

Notice that if $\mathbf{x}$ is an eigenvector, then $\alpha \mathbf{x}$ is also an eigenvector for any scalar $\alpha \ne 0$. So really we are studying eigenlines, namely the spans of eigenvectors. The relation of proportionality between $x_1$ and $x_2$ gives the direction of this line.

For $\lambda =+3$ in the previous example, solving $A_{\lambda }\mathbf{x}=0$ would mean solving $\left(\begin{array}{cc}-2& -2\\ -4& -4\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right)$. Therefore $-x_1-x_2=0$ and thus $x_1=-x_2$, so an eigenvector is given by $\left(\begin{array}{c}1\\ -1\end{array}\right)$ and a line of eigenvectors is given by the span $\alpha \left(\begin{array}{c}1\\ -1\end{array}\right)=\left(\begin{array}{c}\alpha \\ -\alpha \end{array}\right)$ for all $\alpha$. For $\lambda =-3$ we find $\left(\begin{array}{cc}4& -2\\ -4& 2\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right)$, and solving this we find $2x_1=x_2$ and therefore $\left(\begin{array}{c}1\\ 2\end{array}\right)$ is an eigenvector, as is everything in the span $\left(\begin{array}{c}\alpha \\ 2\alpha \end{array}\right)$.

Link to original

Matrices IV: Spectrum

Eigenvectors, eigenvalues: Part II

Example

Finding eigenvectors and eigenvalues

Finding eigenvectors and eigenvalues

Problem: Find the eigenvectors and their eigenvalues for the matrix $A=\left(\begin{array}{rrr}4& 0& 1\\ -2& 1& 0\\ -2& 0& 1\end{array}\right)$.
Solution: First find the eigenvalues:

$$\begin{array}{rl}\det A_{\lambda }& =\left|\begin{array}{ccc}4-\lambda & 0& 1\\ -2& 1-\lambda & 0\\ -2& 0& 1-\lambda \end{array}\right|\\ & \\ & =(4-\lambda )\left|\begin{array}{cc}1-\lambda & 0\\ 0& 1-\lambda \end{array}\right|-0\left|\begin{array}{cc}-2& 0\\ -2& 1-\lambda \end{array}\right|+1\left|\begin{array}{cc}-2& 1-\lambda \\ -2& 0\end{array}\right|\\ & \\ & =(4-\lambda )(1-\lambda {)}^2-0+2(1-\lambda )\\ & =-{\lambda }^3+6{\lambda }^2-11\lambda +6.\end{array}$$

The roots are $\lambda =1,2,3$. (The rational roots theorem leads to the guess $\lambda =2$, and then you can divide the cubic polynomial by $\lambda -2$ to obtain a quadratic one, which is easily factored.)

Now we seek eigenvectors by solving $A_{\lambda }\mathbf{x}=0$ for each $\lambda$ root. When $\lambda =1$:

$$A_{\lambda }\mathbf{x}=\left(\begin{array}{rrr}3& 0& 1\\ -2& 0& 0\\ -2& 0& 0\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\end{array}\right).$$

To solve for $\mathbf{x}$, row reduce $A_{\lambda }$ to obtain a matrix in RREF:

$$\begin{array}{rl}{A}_{\lambda }& =\left(\begin{array}{rrr}3& 0& 1\\ -2& 0& 0\\ -2& 0& 0\end{array}\right)\sim \left(\begin{array}{rrr}3& 0& 1\\ 0& 0& 2/3\\ 0& 0& 2/3\end{array}\right)\\ & \\ & \sim \left(\begin{array}{rrr}3& 0& 0\\ 0& 0& 2/3\\ 0& 0& 0\end{array}\right)\sim \left(\begin{array}{rrr}1& 0& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}\right).\end{array}$$

So we know $x_1=x_3=0$ and $x_2$ is free. Plugging these in we have $\mathbf{x}=\left(\begin{array}{c}0\\ x_2\\ 0\end{array}\right)$, and we choose $x_2=1$ obtaining $\left(\begin{array}{c}0\\ 1\\ 0\end{array}\right)$ for an eigenvector.

Next for $\lambda =2$ we have:

$$A_{\lambda }\mathbf{x}=\left(\begin{array}{rrr}2& 0& 1\\ -2& -1& 0\\ -2& 0& -1\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\end{array}\right).$$

To solve for $\mathbf{x}$, row reduce $A_{\lambda }$ to obtain a matrix in RREF:

$$\begin{array}{rl}{A}_{\lambda }& =\left(\begin{array}{rrr}2& 0& 1\\ -2& -1& 0\\ -2& 0& -1\end{array}\right)\sim \left(\begin{array}{rrr}2& 0& 1\\ 0& -1& 1\\ 0& 0& 0\end{array}\right)\sim \left(\begin{array}{rrr}1& 0& 1/2\\ 0& 1& -1\\ 0& 0& 0\end{array}\right).\end{array}$$

So we know $x_1=-\frac{1}{2}{x}_3$ and $x_2=+x_3$. Plugging these in we have $\mathbf{x}=\left(\begin{array}{c}-\frac{1}{2}{x}_3\\ x_3\\ x_3\end{array}\right)$, and we choose $x_3=2$ obtaining $\left(\begin{array}{c}-1\\ 2\\ 2\end{array}\right)$.

Finally for $\lambda =3$ we have:

$$A_{\lambda }\mathbf{x}=\left(\begin{array}{rrr}1& 0& 1\\ -2& -2& 0\\ -2& 0& -2\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\end{array}\right).$$

To solve for $\mathbf{x}$, row reduce $A_{\lambda }$ to obtain a matrix in RREF:

$$\begin{array}{rl}{A}_{\lambda }& =\left(\begin{array}{rrr}1& 0& 1\\ -2& -2& 0\\ -2& 0& -2\end{array}\right)\sim \left(\begin{array}{rrr}1& 0& 1\\ 0& -2& 2\\ 0& 0& 0\end{array}\right)\sim \left(\begin{array}{rrr}1& 0& 1\\ 0& 1& -1\\ 0& 0& 0\end{array}\right).\end{array}$$

So we know $x_1=-x_3$ and $x_2=+x_3$. Plugging these in we have $\mathbf{x}=\left(\begin{array}{c}-x_3\\ x_3\\ x_3\end{array}\right)$, and we choose $x_3=1$ obtaining $\left(\begin{array}{c}-1\\ 1\\ 1\end{array}\right)$.

Link to original

Example

Changing to eigenbasis yields diagonal matrix

Changing to eigenbasis yields diagonal matrix

Notice that $A$ in the previous example has three eigenvectors, and that they are independent. Therefore they constitute a basis of ${\mathbb{R}}^3$; let’s call this basis $\mathcal{C}$. Putting these basis vectors as the columns of a matrix, we create the change of basis transfer matrix from $\mathcal{C}$ to the standard basis $\mathcal{B}$:

$${}_{\mathcal{B}}{T}_{\mathcal{C}}=\left(\begin{array}{ccc}{\mathbf{c}}_1& {\mathbf{c}}_2& {\mathbf{c}}_3\end{array}\right)=\left(\begin{array}{rcc}0& -1& -1\\ 1& 2& 1\\ 0& 2& 1\end{array}\right).$$

So ${}_{\mathcal{B}}{T}_{\mathcal{C}}\cdot [\mathbf{x}{]}_{\mathcal{C}}=x_1{\mathbf{c}}_1+x_2{\mathbf{c}}_2+x_3{\mathbf{c}}_3=x_1\left(\begin{array}{c}0\\ 1\\ 0\end{array}\right)+x_2\left(\begin{array}{c}-1\\ 2\\ 2\end{array}\right)+x_3\left(\begin{array}{c}-1\\ 1\\ 1\end{array}\right)$.

Now consider that these are eigenvectors of $A$ with eigenvalues $1,2,3$:

$$A{\mathbf{c}}_1={\mathbf{c}}_1,A{\mathbf{c}}_2=2{\mathbf{c}}_2,A{\mathbf{c}}_3=3{\mathbf{c}}_3.$$

If we write $A$ in the basis $\mathcal{C}$ using the transfer matrix ${}_{\mathcal{B}}{T}_{\mathcal{C}}$, we have:

$$\begin{array}{rl}[A{]}_{\mathcal{C}}& ={}_{\mathcal{C}}{T}_{\mathcal{B}}\cdot A\cdot {}_{\mathcal{B}}{T}_{\mathcal{C}}\\ & \\ & ={\left(\begin{array}{rcc}0& -1& -1\\ 1& 2& 1\\ 0& 2& 1\end{array}\right)}^{-1}\left(\begin{array}{rrr}4& 0& 1\\ -2& 1& 0\\ -2& 0& 1\end{array}\right)\left(\begin{array}{rcc}0& -1& -1\\ 1& 2& 1\\ 0& 2& 1\end{array}\right)=\left(\begin{array}{rcc}1& 0& 0\\ 0& 2& 0\\ 0& 0& 3\end{array}\right).\end{array}$$

In other words, the matrix of $A$ is a diagonal matrix when written in the basis of its own eigenvectors.

Link to original

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:

Link to original

Example

Matrix with too few eigenvectors

Matrix with too few eigenvectors

The matrix $A=\left(\begin{array}{rc}1& 1\\ 0& 1\end{array}\right)$ has $\det A_{\lambda }=(1-\lambda {)}^2$. Therefore it has a “double” eigenvalue $\lambda =+1$. To find the eigenvectors:

$$A_{+1}\cdot \mathbf{x}=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right).$$

The matrix is already in RREF. So the equation says that $x_1$ is free and $x_2=0$. Therefore we have the eigenvector $\left(\begin{array}{c}1\\ 0\end{array}\right)$.

However, no more eigenvectors are available (other than scalar multiples of this one, which would not be independent of this one). Therefore it is impossible to find a basis of eigenvectors, and it is thus impossible to convert $A$ to diagonal form by a change of basis.

Link to original

Eigenvectors, eigenvalues - Part II (part 2)

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

Link to original

Example

Matrix with complex eigenvalues and eigenvectors

Matrix with complex eigenvalues and eigenvectors

The matrix $A=\left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)$ has $\det A_{\lambda }={\lambda }^2+1$ so its eigenvalues are $\lambda =\pm i$. To find the eigenvectors:

$$A_i\cdot \mathbf{x}=\left(\begin{array}{cc}-i& -1\\ 1& -i\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right).$$

Row reduce the matrix $A_i$:

$$A_i=\left(\begin{array}{cc}-i& -1\\ 1& -i\end{array}\right)\sim \left(\begin{array}{cc}-i& -1\\ 0& 0\end{array}\right)\sim \left(\begin{array}{cc}1& -i\\ 0& 0\end{array}\right).$$

This is now in RREF, so we see that $x_1=i{x}_2$ and $x_2$ is free, so we get the eigenvector $\left(\begin{array}{c}i\\ 1\end{array}\right)$.

Following the same procedure for $\lambda =-i$, we find the eigenvector $\left(\begin{array}{c}-i\\ 1\end{array}\right)$.

Link to original

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

Link to original

Question

01

Double eigenvalues does not imply insufficient eigenvectors

What are the eigenvalues and eigenvectors of $A=\left(\begin{array}{cc}2& 0\\ 0& 2\end{array}\right)$? Are there enough to form a basis of ${\mathbb{R}}^2$?

Link to original

Question

02

Enough eigenvectors?

Does the matrix $A=\left(\begin{array}{ccc}2& 1& 0\\ 0& 2& 1\\ 0& 0& 2\end{array}\right)$ have enough eigenvectors to form a basis? If not, how many does it have?

Link to original

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.

Link to original

Eigenvectors vs. singular vectors

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.

Link to original

Defining the singular value decomposition

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

Link to original

Computing the singular value decomposition

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

Link to original

Example

Computing SVD by hand

Computing SVD by hand

Problem: Find an SVD for the matrix $A=\left(\begin{array}{rr}1& -1\\ -2& 2\\ 2& -2\end{array}\right)$.

Solution: First calculate that $A^{\mathsf{T}}A=\left(\begin{array}{rc}9& -9\\ -9& 9\end{array}\right)$ and this matrix has $\lambda =18$ and $\lambda =0$ eigenvalues. Therefore we set ${\sigma }_1=3\sqrt{2}$ and ${\sigma }_2=0$. By solving $\left(\begin{array}{rr}-9& -9\\ -9& -9\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right)$ we obtain an eigenvector $\left(\begin{array}{r}1\\ -1\end{array}\right)$ which we renormalize to the unit vector $\left(\begin{array}{r}1/\sqrt{2}\\ -1/\sqrt{2}\end{array}\right)$. By solving $\left(\begin{array}{rr}9& -9\\ -9& 9\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right)$ we obtain an eigenvector $\left(\begin{array}{r}1\\ 1\end{array}\right)$ which we renormalize to the unit vector $\left(\begin{array}{r}1/\sqrt{2}\\ 1/\sqrt{2}\end{array}\right)$. We now have $V$ and $\Sigma$:

$$\Sigma =\left(\begin{array}{cc}3\sqrt{2}& 0\\ 0& 0\\ 0& 0\end{array}\right),V=\left(\begin{array}{rr}1/\sqrt{2}& 1/\sqrt{2}\\ -1/\sqrt{2}& 1/\sqrt{2}\end{array}\right).$$

Set

$${\mathbf{u}}_1={\sigma }_1^{-1}A{\mathbf{v}}_1=\frac{1}{3\sqrt{2}}\left(\begin{array}{r}2/\sqrt{2}\\ -4/\sqrt{2}\\ 4/\sqrt{2}\end{array}\right)=\left(\begin{array}{r}1/3\\ -2/3\\ 2/3\end{array}\right)$$

and we notice that $|{\mathbf{u}}_1|=1$. Now we need ${\mathbf{u}}_2,{\mathbf{u}}_3$ unit vectors orthogonal to each other and to ${\mathbf{u}}_1$. We first calculate a span of the kernel of the matrix ${\mathbf{u}}_1^{\mathsf{T}}$, and then perform Gram-Schmidt to orthogonalize it. For the kernel:

$$\left(\begin{array}{ccc}1/3& -2/3& 2/3\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)=0,$$

and therefore $x_1-2x_2+2x_3=0$ so we can set $x_2,x_3$ free and solve for $x_1$, thereby obtaining generators for the kernel:

$$\ker {\mathbf{u}}_1^{\mathsf{T}}=\{\left(\begin{array}{c}2x_2-2x_3\\ x_2\\ x_3\end{array}\right)\}=⟨{\mathbf{w}}_2=\left(\begin{array}{c}2\\ 1\\ 0\end{array}\right),{\mathbf{w}}_3=\left(\begin{array}{c}-2\\ 0\\ 1\end{array}\right)⟩.$$

Now we already have ${\mathbf{w}}_2\perp {\mathbf{u}}_1$ by our method of defining ${\mathbf{w}}_2$. So it just remains to do the last step of Gram-Schmidt. We calculate that

$${\mathbf{w}}_3-\frac{{\mathbf{w}}_3\cdot {\mathbf{u}}_1}{{\mathbf{u}}_1\cdot {\mathbf{u}}_1}{\mathbf{u}}_1-\frac{{\mathbf{w}}_3\cdot {\mathbf{w}}_2}{{\mathbf{w}}_2\cdot {\mathbf{w}}_2}{\mathbf{w}}_2=\left(\begin{array}{c}-2\\ 0\\ 1\end{array}\right)-\frac{0}{1}\left(\begin{array}{r}1/3\\ -2/3\\ 2/3\end{array}\right)-\frac{-4}{5}\left(\begin{array}{c}2\\ 1\\ 0\end{array}\right)=\left(\begin{array}{c}-2/5\\ 4/5\\ 1\end{array}\right).$$

Then

$${\mathbf{u}}_2=\frac{1}{|{\mathbf{w}}_2|}{\mathbf{w}}_2=\left(\begin{array}{c}2/\sqrt{5}\\ 1/\sqrt{5}\\ 0\end{array}\right),{\mathbf{u}}_3=\frac{5}{\sqrt{45}}\left(\begin{array}{c}-2/5\\ 4/5\\ 1\end{array}\right)=\left(\begin{array}{r}-2/\sqrt{45}\\ 4/\sqrt{45}\\ 5/\sqrt{45}\end{array}\right).$$

We have finished, and the SVD is given by:

$$A=U\Sigma V^{\mathsf{T}}=\left(\begin{array}{rcr}1/3& 2/\sqrt{5}& -2/\sqrt{45}\\ -2/3& 1/\sqrt{5}& 4/\sqrt{45}\\ 2/3& 0& 5/\sqrt{45}\end{array}\right)\left(\begin{array}{cc}3\sqrt{2}& 0\\ 0& 0\\ 0& 0\end{array}\right)\left(\begin{array}{rr}1/\sqrt{2}& -1/\sqrt{2}\\ 1/\sqrt{2}& 1/\sqrt{2}\end{array}\right).$$

Link to original

Exercise

01

Computing SVD by hand

Find an SVD for the matrix $A=\left(\begin{array}{rr}2& -1\\ 2& 2\end{array}\right)$.

Link to original

Exercise

02

Computing SVD by hand

Find an SVD for the matrix $A=\left(\begin{array}{rr}-3& 1\\ 6& -2\\ 6& -2\end{array}\right)$.

Link to original

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

Link to original