Applied Linear Algebra - Packet 12

Packet 12

Matrices III: Inner Products

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

Orthogonal matrices

A matrix $Q$ is called orthogonal when it satisfies $A^{𝖳}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^{𝖳}Q=I_n$. Remember the rule for matrix products (e.g. in $3$D):

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

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

It follows that $Q^{𝖳}Q=I_n$ is another way of saying that ${𝐪}_j$ and ${𝐪}_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𝐮)\cdot (Q𝐯)=𝐮\cdot 𝐯.$$

Why $(Q𝐮)\cdot (Q𝐯)=𝐮\cdot 𝐯$

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

$$\begin{array}{cc}(Q𝐮)\cdot (Q𝐯)& ={(Q𝐮)}^{𝖳}(Q𝐯)\\ & =({𝐮}^{𝖳}{Q}^{𝖳})(Q𝐯)\\ & ={𝐮}^{𝖳}(Q^{𝖳}Q)𝐯\\ & ={𝐮}^{𝖳}(I_n)𝐯\\ & ={𝐮}^{𝖳}𝐯\\ & =𝐮\cdot 𝐯.\end{array}$$

Symmetric matrices

A symmetric matrix $A$ is a matrix that satisfies $A^{𝖳}=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^{𝖳}=-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^{𝖳}=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 $𝒬=\{{𝐪}_1,\dots ,{𝐪}_n\}$ such that $A$ becomes diagonal in this basis: $D=Q^{-1}AQ,\text{ where }Q=\left(\begin{array}{ccc}{𝐪}_1& \cdots & {𝐪}_n\end{array}\right)={\phantom{}}_{ℬ}{T}_{𝒬}$ in other words $A=QD{Q}^{-1}$. Notice that $Q$ is an orthogonal matrix, and ${𝐪}_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{𝐪}_1={\lambda }_1{𝐪}_1$ and $A{𝐪}_2={\lambda }_2{𝐪}_2$ and ${\lambda }_1\ne {\lambda }_2$. Assume, as we do for eigenvectors, that ${\lambda }_1\ne 0$. Then consider the sequence:

$$\begin{array}{cc}{𝐪}_1\cdot {𝐪}_2& ={\lambda }_1^{-1}({\lambda }_1{𝐪}_1\cdot {𝐪}_2)\\ & ={\lambda }_1^{-1}(A{𝐪}_1)\cdot {𝐪}_2\\ & ={\lambda }_1^{-1}{(A{𝐪}_1)}^{𝖳}{𝐪}_2\\ & ={\lambda }_1^{-1}({𝐪}_1^{𝖳}{A}^{𝖳}){𝐪}_2\\ & ={\lambda }_1^{-1}{𝐪}_1^{𝖳}(A{𝐪}_2)\\ & ={\lambda }_1^{-1}{𝐪}_1^{𝖳}({\lambda }_2{𝐪}_2)\\ & =({\lambda }_1^{-1}{\lambda }_2){𝐪}_1^{𝖳}{𝐪}_2\\ & =({\lambda }_1^{-1}{\lambda }_2){𝐪}_1\cdot {𝐪}_2.\end{array}$$

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

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

$$A={\lambda }_1({𝐪}_1{𝐪}_1^{𝖳})+{\lambda }_2({𝐪}_2{𝐪}_2^{𝖳})+\cdots +{\lambda }_n({𝐪}_n{𝐪}_n^{𝖳}).$$

In this formula, the ${𝐪}_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 next Packet!

A great thing about this formula is that each ${𝐪}_i{𝐪}_i^{𝖳}$ is actually a projection matrix onto ${𝐪}_i$:

$${𝐪}_i{𝐪}_i^{𝖳}=[{\mathrm{proj}}_{{𝐪}_i}].$$

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

Explaining the spectral decomposition formula

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

$$\begin{array}{cc}A=QD{Q}^{𝖳}& =\left(\begin{array}{ccc}{𝐪}_1& \cdots & {𝐪}_n\end{array}\right)\left(\begin{array}{ccc}{\lambda }_1& & 0\\ & \ddots & \\ 0& & {\lambda }_n\end{array}\right)\left(\begin{array}{c}{𝐪}_1^{𝖳}\\ ⋮\\ {𝐪}_n^{𝖳}\end{array}\right)\\ & =\left(\begin{array}{ccc}{𝐪}_1& \cdots & {𝐪}_n\end{array}\right)\left(\begin{array}{c}{\lambda }_1{𝐪}_1^{𝖳}\\ ⋮\\ {\lambda }_n{𝐪}_n^{𝖳}\end{array}\right)\\ & =\left(\begin{array}{ccc}{𝐪}_1& \cdots & {𝐪}_n\end{array}\right)(\left(\begin{array}{c}{\lambda }_1{𝐪}_1^{𝖳}\\ \mathrm{𝟎}\\ ⋮\\ \mathrm{𝟎}\end{array}\right)+\left(\begin{array}{c}\mathrm{𝟎}\\ {\lambda }_2{𝐪}_2^{𝖳}\\ ⋮\\ \mathrm{𝟎}\end{array}\right)+\left(\begin{array}{c}\mathrm{𝟎}\\ \mathrm{𝟎}\\ ⋮\\ {\lambda }_n{𝐪}_n^{𝖳}\end{array}\right))\\ & ={𝐪}_1{\lambda }_1{𝐪}_1^{𝖳}+\cdots +{𝐪}_n{\lambda }_n{𝐪}_n^{𝖳}\\ & ={\lambda }_1({𝐪}_1{𝐪}_1^{𝖳})+{\lambda }_2({𝐪}_2{𝐪}_2^{𝖳})+\cdots +{\lambda }_n({𝐪}_n{𝐪}_n^{𝖳}).\end{array}$$

Quadratic forms and symmetric matrices

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

$$\begin{array}{cc}& \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 $(\mathrm{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.

Question 12-01

[Removed!]

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(𝐱)={𝐱}^{𝖳}A𝐱$.

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

Example

Quadratic form

$$\begin{array}{cc}Q(𝐱)={𝐱}^{𝖳}A𝐱& =\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}$$

Question 12-02

Matrix of a quadratic form

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

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 $𝐱$, then a linear change of variables would be a vector $𝐲$ defined by $𝐲={\phantom{}}_{{ℬ}^{\prime }}{T}_{ℬ}(𝐱)$ for some change of basis transfer matrix ${\phantom{}}_{{ℬ}^{\prime }}{T}_{ℬ}$.

Principal axes theorem: eliminating cross terms

Given a quadratic form $Q(𝐱)$ defined by the symmetric matrix $A$, suppose $A=PD{P}^{𝖳}$. Set $𝐲=P^{𝖳}𝐱$, so also $𝐱=P𝐲$. Then $Q(P𝐲)$ has no cross terms in the $𝐲$ variables.

Derivation

First plug in the new variables and manipulate:

$${𝐱}^{𝖳}A𝐱={(P𝐲)}^{𝖳}A(P𝐲)={𝐲}^{𝖳}(P^{𝖳}AP)𝐲={𝐲}^{𝖳}D𝐲$$

This last expression has no cross terms:

$$\begin{array}{cc}{𝐲}^{𝖳}D𝐲& =\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}$$

Example

Eliminating cross terms

Problem: Eliminate the cross terms in the quadratic form $Q(𝐱)=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}^{𝖳}$ 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 =-\mathrm{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 ${𝐯}_{-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}{cc}-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 ${𝐯}_3=\left(\begin{array}{c}3/\sqrt{10}\\ 1/\sqrt{10}\end{array}\right)$. Notice that ${𝐯}_{-7}\cdot {𝐯}_3=0$.

Now we set ${𝐪}_1={𝐯}_{-7}$ and ${𝐪}_2={𝐯}_3$ and write our expression for $A$:

$$\begin{array}{cc}A& =\left(\begin{array}{cc}2& 3\\ 3& -6\end{array}\right)=PD{P}^{𝖳}\\ & =\left(\begin{array}{cc}1/\sqrt{10}& 3/\sqrt{10}\\ -3/\sqrt{10}& 1/\sqrt{10}\end{array}\right)\left(\begin{array}{cc}-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 $𝐲$ variables, we have $Q(𝐱)=Q(P𝐲)=-7y_1^2+3y_2^2$. The formulas relating the variables to each other are given by interpreting $P^{𝖳}$ as the change of variable transfer matrix:

$$\begin{array}{cc}{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}$$

Exercise 12-01

Eliminating cross terms.

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

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(𝐱)$ where $𝐱$ is constrained to be a unit vector, so ${𝐱}^{𝖳}𝐱=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(𝐲)$ so as to eliminate cross terms:

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

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

If $Q(𝐱)$ 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 $𝐲={𝐞}_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 ${𝐪}_i$ corresponding to ${\lambda }_i$ has already been found, its components are by definition the components of $P{𝐞}_i$ that we seek.

Example

Optimizing $Q(𝐱)=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 ${𝐪}_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 ${𝐪}_1={𝐯}_{-7}$ in the standard basis.

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

Exercise 12-02

Optimizing $Q(𝐱)=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(𝐱)=2x_1^2-4x_1{x}_2-x_2^2$ for $𝐱$ a unit vector, and find the unit vectors that produce these extreme values.

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,𝐱)=\frac{{𝐱}^{𝖳}A𝐱}{{𝐱}^{𝖳}𝐱}.$$

Notice that the value of $R(A,𝐱)$ is the same as the value of the quadratic form generated by $A$, evaluated at the unit vector given by first normalizing the input $𝐱$. Therefore, maximizing $R(A,𝐱)$ over all possible $𝐱\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,𝐱)$, and these occur when $𝐱$ 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,𝐱)$ 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 $𝐱$ and plugging it into the quadratic form $Q$ arising from the symmetric matrix $A$.

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}{cc}A\text{ is positive definite:}A& =7{𝐪}_1{𝐪}_1^{𝖳}+{𝐪}_2{𝐪}_2^{𝖳}+3{𝐪}_3{𝐪}_3^{𝖳}\\ A\text{ is negative definite:}A& =-7{𝐪}_1{𝐪}_1^{𝖳}-{𝐪}_2{𝐪}_2^{𝖳}-3{𝐪}_3{𝐪}_3^{𝖳}\\ A\text{ is indefinite:}A& =7{𝐪}_1{𝐪}_1^{𝖳}-{𝐪}_2{𝐪}_2^{𝖳}+3{𝐪}_3{𝐪}_3^{𝖳}.\end{array}$$

Since the spectral decomposition reveals the quadratic form in the new variables, where ${𝐪}_i=P{𝐞}_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(𝐱)$ is always positive for $𝐱\ne \mathrm{𝟎}$.
• When $A$ is negative definite, then its form $Q(𝐱)$ is always negative for $𝐱\ne \mathrm{𝟎}$.

Inner products and symmetric matrices

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

$$⟨-,-⟩:(𝐮,𝐯)\mapsto ⟨𝐮,𝐯⟩\in ℝ,$$

which is linear in both inputs considered separately.

Rules of inner products:

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

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

$$\begin{array}{cc}{⟨𝐮,𝐯⟩}_{\text{dot}}& =𝐮\cdot 𝐯=\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)\\ & ={𝐮}^{𝖳}𝐯=\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^{𝖳}$ and then taking the usual dot product:

$${⟨𝐮,𝐯⟩}_A={⟨𝐮,A𝐯⟩}_{\text{dot}}=𝐮\cdot A𝐯.$$

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

$$\begin{array}{cc}{⟨𝐮,𝐯⟩}_A& ={𝐮}^{𝖳}A𝐯\\ & ={({𝐮}^{𝖳}A𝐯)}^{𝖳}({\lambda }^{𝖳}=\lambda \text{ for scalars})\\ & ={𝐯}^{𝖳}{A}^{𝖳}{({𝐮}^{𝖳})}^{𝖳}\\ & ={𝐯}^{𝖳}A𝐮\\ & ={⟨𝐯,A𝐮⟩}_A.\end{array}$$

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

$${⟨𝐱,𝐱⟩}_A={𝐱}^{𝖳}A𝐱=Q(𝐱).$$

The last property of inner products (namely that $⟨𝐮,𝐮⟩>0$ etc.) means that a quadratic form created in this way by setting $Q(𝐱)={⟨𝐱,𝐱⟩}_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}=⟨{𝐞}_i,{𝐞}_j⟩$. This works because $A{𝐞}_j$ gives the $j^{\text{th}}$ column vector of $A$, and then ${𝐞}_i^{𝖳}A{𝐞}_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.

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 }𝐱=\mathrm{𝟎}$, and then we can try to find the eigenvectors $𝐱$ 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 $𝐱$.

Notice that if $𝐱$ is an eigenvector, then $\alpha 𝐱$ 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 }𝐱=\mathrm{𝟎}$ 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)$.

Problems due 10 Apr 2024 by 12:00pm

Exercises for submission with HW (if not in class)

Quadratic form: eliminating cross terms and optimizing

• (a) Eliminate cross terms in the quadratic form $Q(𝐱)=2x_1^2-4x_1{x}_2-x_2^2$.
• (b) Find the min and max values of $Q(𝐱)$ from (a) where $𝐱$ is a unit vector, and find the unit vectors $𝐱$ that produce these extreme values. (Use your result in (a) to minimize in changed variables, and then change variables back again.)

Problem 12-01

Finding a spectral decomposition

Let $A=\left(\begin{array}{ccc}4& 2& 2\\ 2& 4& 2\\ 2& 2& 4\end{array}\right)$.

• (a) Find the eigenvalues of $A$. There will be two distinct numbers, ${\lambda }_1,{\lambda }_2$, not three.
• (b) Row reduce $A_{{\lambda }_1}$ and $A_{{\lambda }_2}$ to solve the two equations $A_{{\lambda }_1}𝐱=\mathrm{𝟎}$ and $A_{{\lambda }_2}𝐱=\mathrm{𝟎}$. In this way, write down a set of 3 eigenvectors, two of which have one of the eigenvalues, and the third has the other eigenvalue.
• (c) For the ‘double’ eigenvalue, convert its two eigenvectors to orthogonal vectors (subtract a projection like in Gram-Schmidt, unless they are already perpendicular).
• (d) Normalize all your orthogonal eigenvectors to get unit eigenvectors. Call them ${𝐪}_1,{𝐪}_2,{𝐪}_3$. Now the matrix $Q=\left(\begin{array}{ccc}{𝐪}_1& {𝐪}_2& {𝐪}_3\end{array}\right)$ is an orthogonal matrix, its inverse is $Q^{-1}=Q^{𝖳}$, and we know that $A=QD{Q}^{𝖳}$ where $D$ has the eigenvectors ${\lambda }_1,{\lambda }_2,{\lambda }_3$ along the diagonal. (In order, so $A{𝐪}_i={\lambda }_i{𝐪}_i$ for $i=\mathrm{1,2,3}$.)
• (e) Write out the spectral decomposition: $A={\lambda }_1{𝐪}_1{𝐪}_1^{𝖳}+{\lambda }_2{𝐪}_2{𝐪}_2^{𝖳}+{\lambda }_3{𝐪}_3{𝐪}_3^{𝖳}$. In other words, simply compute the three projection matrices ${𝐪}_i{𝐪}_i^{𝖳}$, and plug them into this formula. Check that if you were to take the sum, you would get $A$.

Problem 12-02

Quadratic form

Let $A$ be the matrix as in Problem 12-01. Use results of 12-01 for this problem: you do not need to find the eigenvalues / eigenvectors again.

• (a) What is the quadratic form $Q(𝐱)$ associated to $A$?
• (b) What is the quadratic form $Q(𝐲)$ in the variables $𝐲$ that eliminate cross terms?
• (c) What is the max and min of $Q(𝐱)$ for $|𝐱|=1$?
• (d) What are the vectors $𝐱$ that yield the max and min found in (d)?

Problem 12-03

Functions of symmetric matrices

• (a) Write out in coefficients the matrix $A=7{𝐪}_1{𝐪}_1^{𝖳}+{𝐪}_2{𝐪}_2^{𝖳}+3{𝐪}_3{𝐪}_3^{𝖳}$ when ${𝐪}_i={𝐞}_i$.
• (b) Compute the matrix product $A^2$ when ${𝐪}_i={𝐞}_i$. (Notice that you have found $B=A^2$.)
• (c) Write out in coefficients the matrix $A=49{𝐪}_1{𝐪}_1^{𝖳}+{𝐪}_2{𝐪}_2^{𝖳}+9{𝐪}_3{𝐪}_3^{𝖳}$ when ${𝐪}_i={𝐞}_i$.
• (d) Guess the coefficients ${\lambda }_1,{\lambda }_2,{\lambda }_3$ in $B={\lambda }_1{𝐪}_1{𝐪}_1^{𝖳}+{\lambda }_2{𝐪}_2{𝐪}_2^{𝖳}+{\lambda }_3{𝐪}_3{𝐪}_3^{𝖳}$ such that $B^2=A$ for $A$ as in (a). Verify your guess by writing out $B$ in coefficients and then calculating $B^2$. (Notice that you have found $B=\sqrt{A}$.)
• (e) Now drop the assumption that ${𝐪}_i={𝐞}_i$, and yet find $A^2$ by FOILing the product $(7{𝐪}_1{𝐪}_1^{𝖳}+{𝐪}_2{𝐪}_2^{𝖳}+3{𝐪}_3{𝐪}_3^{𝖳})(7{𝐪}_1{𝐪}_1^{𝖳}+{𝐪}_2{𝐪}_2^{𝖳}+3{𝐪}_3{𝐪}_3^{𝖳})$. To simplify the result, figure out what ${𝐪}_i{𝐪}_i^{𝖳}{𝐪}_j{𝐪}_j^{𝖳}$ is for $i=j$ and $i\ne j$.
• (f) Based on (a)-(e), can you guess what ${\lambda }_1,{\lambda }_2,{\lambda }_3$ should be in the matrix $e^A$? (Hint: consider that $e^x$ has a power series expansion: $e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\cdots$.)

Problem 12-04

Positive definite matrices

Suppose $A^{𝖳}=A$ and $A^{-1}$ exists. (Symmetric and invertible.) Notice that the Spectral Theorem applies.

• (a) What are the eigenvalues of $A^{-1}$ in terms of the eigenvalues of $A$?
• (b) Suppose that $Q(𝐱)={𝐱}^{𝖳}A𝐱$ is positive definite. Show that $Q^{\prime }(𝐱)={𝐱}^{𝖳}{A}^{-1}𝐱$ is also positive definite. (Hint: make use of (a).)