Announcements¶

• Homework 7 due tonight at 8pm
• Homework 8 will be out later today
• Upcoming office hours:
  • Today: Peer tutor Daniel Cho from 12:30-3:30pm in CCDS 16th floor
  • Today: Abhishek Tiwari from 4-5pm on CCDS 13th floor
• Reading
  • Deisenroth-Faisal-Ong Section 4.2 and 4.4
  • 3Blue1Brown video 13 and video 14

Recap: Diagonalization¶

Last time, we formed a theory of diagonalizing a square matrix $A$ into $A=PD{P}^{-1}$.

Diagonalization is not always possible.

• If it exists, its format is related to the eigenvalues and eigenvectors of $A$
• If it exists, it makes many matrix problems substantially easier, such as taking matrix powers $A^k$

We also proved the following theorem.

Theorem. (The Diagonalization Theorem)

A square $n\times n$ matrix $A$ is diagonalizable if and only if $A$ has $n$ linearly independent eigenvectors.

28.5 Diagonalization as a Change of Basis¶

We can now turn to a geometric understanding of how diagonalization informs us about the properties of $A$.

Let's interpret the diagonalization $A=PD{P}^{-1}$ in terms of how $A$ acts as a linear operator.

When thinking of $A$ as a linear operator, diagonalization has a specific interpretation:

Diagonalization separates the influence of each vector component from the others.

To see what this means, let's first consider an easier case: a diagonal matrix. When we multiply a vector $x$ by a diagonal matrix $D$, the change to each component of $x$ depends only on that component.

That is, multiplying by a diagonal matrix simply scales the components of the vector.

Example. Let $D=\left[\begin{array}{cc}5& 0\\ 0& 3\end{array}\right].$ Then, $$D\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}5x_1\\ 3x_2\end{array}\right].$$

On the other hand, when we multiply by a matrix $A$ that has off-diagonal entries, the components of $x$ affect each other.

So diagonalizing a matrix allows us to bring intuition to its behavior as as linear operator.

Interpreting Diagonalization Geometrically¶

When we compute $Px,$ we are taking a vector sum of the columns of $P$:

Now $P$ is square and invertible, so its columns are a basis for $R^n$. Let's call that basis $B=\{p_1,p_2,\dots ,p_n\}.$

So, we can think of $Px$ as "the point that has coordinates $x$ in the basis $B$."

On the other hand, what if we wanted to find the coordinates of a vector in basis $B$?

Let's say we have some $y$ written in the standard basis, and we want to find its coordinates in the basis $B$.

So $y=Px=x_1{p}_1+x_2{p}_2+\cdots +x_n{p}_n=[x{]}_B.$

Then since $P$ is invertible, $x=P^{-1}y.$

Thus, $P^{-1}y$ is "the coordinates of $y$ in the basis $B.$"

So we can interpret $Ax=PD{P}^{-1}x$ as:

1. Compute the coordinates of $x$ in the basis $B$.

   This is $P^{-1}x.$

2. Scale those coordinates according to the diagonal matrix $D$.

   This is $D{P}^{-1}x.$

3. Find the point that has those scaled coordinates in the basis $B.$

   This is $PD{P}^{-1}x.$

Example. Let's visualize diagonalization geometrically.

Consider a fixed-but-unwritten matrix $A$. Here's a picture showing how it transforms a point $x=\left[\begin{array}{c}2.47\\ 1.25\end{array}\right]$.

So far, we cannot say much about what the linear transformation $A$ does in general.

Now, let's compute $P^{-1}x.$

Remember that the columns of $P$ are the eigenvectors of $A$.

So $P^{-1}x$ is the coordinates of the point $x$ in the eigenvector basis:

The coordinates of $x$ in this basis are (2,1).

In other words $P^{-1}x=\left[\begin{array}{c}2\\ 1\end{array}\right].$

Now, we compute $D{P}^{-1}x.$ Since $D$ is diagonal, this is just scaling each of the $B$-coordinates.

In this example the eigenvalue corresponding to $p_1$ is 2, and the eigenvalue corresponding to $p_2$ is 3.

So the coordinates of $Ax$ in the basis $B$ are

Now we convert back to the standard basis -- that is, we ask which point has coordinates (4,3) in basis $B.$

We rely on the fact that if $y$ has coordinates $x$ in the basis $B$, then $y=Px.$

So

We find that $Ax$ = $PD{P}^{-1}x=\left[\begin{array}{c}5.46\\ 3.35\end{array}\right].$

In conclusion: notice that the transformation $x\mapsto Ax$ may be a complicated one in which each component of $x$ affects each component of $Ax$.

However, by changing to the basis defined by the eigenspaces of $A$, the action of $A$ becomes simple to understand.

Diagonalization of $A$ changes to a basis in which the action of $A$ is particularly easy to understand and compute with.

Lecture 29: Symmetric Matrices¶

[This lecture is based on Prof. Crovella's CS 132 lecture notes.]

Next week, we will design a generalization of this technique that applies to all matrices. It is called singular value decomposition, and it is the main mathematical tool we have been building up to in this course. We will then explore its data science applications.

But we need one more mathematical tool in our toolbelt first.

Today we'll study a very important class of matrices: symmetric matrices.

Definition. A symmetric matrix is a matrix $A$ such that $A^{\top }=A$.

Example. Here are three symmetric matrices:

We have already seen symmetric matrices within the normal equation: $\left(A^{\top }A\right)$ is always symmetric because

We'll see that symmetric matrices have properties that relate to both eigendecomposition and orthogonality.

Furthermore, symmetric matrices open up a broad class of problems we haven't yet touched on: constrained optimization.

As a result, symmetric matrices arise very often in applications.

29.1 Diagonalizing a symmetric matrix¶

At first glance, a symmetric matrix may not seem that special!

But in fact symmetric matrices have a number of interesting properties.

First, we'll look at a remarkable fact:

the eigenvectors of a symmetric matrix are orthogonal

Example. Diagonalize the following symmetric matrix:

Solution. Remember that diagonalization is a four-step process: (1) find the eigenvalues of $A$, (2) find the eigenvectors of $A$, (3) construct $P$, and (4) construct $D$.

The characteristic equation of $A$ is

So the eigenvalues are 8, 6, and 3.

We construct a basis for each eigenspace (using our standard method of finding the nullspace of $A-\lambda I$):

These three vectors form a basis for $R^3.$

But here is the remarkable thing: these three vectors form an orthogonal set.

That is, any two eigenvectors are orthogonal.

For example,

As a result, $\{v_1,v_2,v_3\}$ form an orthogonal basis for $R^3.$

Let's normalize these vectors so they each have length 1:

The orthogonality of the eigenvectors of a symmetric matrix is quite important.

To see this, let's write the diagonalization of $A$ in terms of these eigenvectors and eigenvalues:

Then, $A=PD{P}^{-1}$ as usual.

But, here is the interesting thing:

$P$ is square and has orthonormal columns.

So $P$ is an orthogonal matrix (also known as an orthonormal matrix).

So, that means that $P^{-1}=P^{\top }.$

So, $A=PD{P}^{\top }.$

The Spectral Theorem¶

Here is a theorem that shows that we always get orthogonal eigenvectors when we diagonalize a symmetric matrix:

Theorem. If $A$ is symmetric, then any two eigenvectors of $A$ from different eigenspaces are orthogonal.

Proof.

Let $v_1$ and $v_2$ be eigenvectors that correspond to distinct eigenvalues, say, ${\lambda }_1$ and ${\lambda }_2.$

To show that $v_1^{\top }{v}_2=0,$ compute

So we conclude that ${\lambda }_1\left(v_1^{\top }{v}_2\right)={\lambda }_2\left(v_1^{\top }{v}_2\right).$

But ${\lambda }_1\ne {\lambda }_2,$ so this can only happen if $v_1^{\top }{v}_2=0.$

So $v_1$ is orthogonal to $v_2.$

The same argument applies to any other pair of eigenvectors with distinct eigenvalues.

So any two eigenvectors of $A$ from different eigenspaces are orthogonal.

Orthogonal Diagonalization¶

We can now introduce a special kind of diagonalizability:

An $n\times n$ matrix is said to be orthogonally diagonalizable if there are an orthogonal matrix $P$ (with $P^{-1}=P^{\top }$) and a diagonal matrix $D$ such that

Such a diagonalization requires $n$ linearly independent and orthonormal eigenvectors.

When is this possible?

If $A$ is orthogonally diagonalizable, then

So $A$ is symmetric!

It turns out the converse is true (though we won't prove it).

Hence we obtain the following theorem:

Theorem. An $n\times n$ matrix is orthogonally diagonalizable if and only if it is a symmetric matrix.

Recall from last time: we found that it was a difficult process, in general, to determine if an arbitrary matrix was diagonalizable.

But here, we have a very nice rule: every symmetric matrix is (orthogonally) diagonalizable.

29.2 Quadratic Forms¶

An important role that symmetric matrices play has to do with quadratic expressions.

Up until now, we have mainly focused on linear equations -- equations in which the $x_i$ terms occur only to the first power.

Actually, though, we have looked at some quadratic expressions when we considered least-squares problems.

For example, we looked at expressions such as $\parallel x{\parallel }^2$ which is $\sum x_i^2.$

We'll now look at quadratic expressions generally. We'll see that there is a natural and useful connection to symmetric matrices.

Definition. A quadratic form is a function of variables, eg, $x_1,x_2,\dots ,x_n,$ in which every term has degree two.

Examples:

$4x_1^2+2x_1{x}_2+3x_2^2$ is a quadratic form.

$4x_1^2+2x_1$ is not a quadratic form.

Quadratic forms arise in many settings, including signal processing, graph analysis, physics, economics, and statistics.

Within data science, quadratic forms arise in many optimization problems, among other areas.

Essentially, what an expression like $x^2$ is to a scalar, a quadratic form is to a vector.

Fact. Every quadratic form can be expressed as $x^{\top }Ax$, where $A$ is a symmetric matrix.

There is a simple way to go from a quadratic form to a symmetric matrix, and vice versa.

To see this, let's look at some examples.

Example. Let $x=\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right].$ Compute $x^{\top }Ax$ for the matrix $A=\left[\begin{array}{cc}4& 0\\ 0& 3\end{array}\right].$

Solution.

Example. Compute $x^{\top }Ax$ for the matrix $A=\left[\begin{array}{cc}3& -2\\ -2& 7\end{array}\right].$

Solution.

Notice the simple structure: $$a_{11}\text{is multiplied by}{x}_1{x}_1$$ $$a_{12}\text{is multiplied by}{x}_1{x}_2$$ $$a_{21}\text{is multiplied by}{x}_2{x}_1$$ $$a_{22}\text{is multiplied by}{x}_2{x}_2$$

We can write this concisely:

Example. For $x$ in $R^3$, let

Write this quadratic form $Q\left(x\right)$ as $x^{\top }Ax$.

Solution.

The coefficients of $x_1^2,x_2^2,x_3^2$ go on the diagonal of $A$.

Based on the previous example, we can see that the coefficient of each cross term $x_i{x}_j$ is the sum of two values in symmetric positions on opposite sides of the diagonal of $A$.

So to make $A$ symmetric, the coefficient of $x_i{x}_j$ for $i\ne j$ must be split evenly between the $(i,j)$- and $(j,i)$-entries of $A$.

You can check that

Visualizing Quadratic Forms¶

Notice that $x^{\top }Ax$ is a scalar.

In other words, when $A$ is an $n\times n$ matrix, the quadratic form $Q\left(x\right)=x^{T}Ax$ is a function that maps vectors in the domain $R^n$ to real numbers in the codomain $R$.

Here are four quadratic forms with domain $R^2$.

Notice that except at $x=0,$ the values of $Q\left(x\right)$ are all positive in the first case, and all negative in the last case.

29.3 Classifying Quadratic Forms¶

The differences between these surfaces is important for problems such as optimization.

In an optimization problem, one seeks the minimum or maximum value of a function (perhaps over a subset of its domain).

Definition. A quadratic form $Q$ is:

1. positive definite if $Q\left(x\right)>0$ for all $x\ne 0.$
2. positive semidefinite if $Q\left(x\right)\ge 0$ for all $x\ne 0.$
3. indefinite if $Q\left(x\right)$ assumes both positive and negative values.
4. negative definite if $Q\left(x\right)<0$ for all $x\ne 0.$
5. negative semidefinite if $Q\left(x\right)\le 0$ for all $x\ne 0.$

If $Q=x^{\top }Ax$, then we will refer to $A$ as a positive (semi)definite or negative (semi)definite matrix.

Knowing which kind of quadratic form one is dealing with is important for optimization. Consider these two quadratic forms:

Notice that that matrices differ in only one position.

Let's say we would like to find

• the minimum value of $P\left(x\right)$ over all $x$, or
• the minimum value of $Q\left(x\right)$ over all $x$

In each case, we need to ask: is it possible? Does a minimum value even exist?

Clearly, we cannot minimize $x^{T}Ax$ over all $x$,

... but we can minimize $x^{T}Bx$ over all $x$.

How can we distinguish between these two cases in general?

That is, in high dimension, without the ability to visualize?

There is a remarkably simple way to determine, for any quadratic form, which class it falls into.

Theorem. Let $A$ be an $n\times n$ symmetric matrix.

Then a quadratic form $x^{T}Ax$ is

1. positive definite if and only if the eigenvalues of $A$ are all positive.
2. positive semidefinite if and only if the eigenvalues of $A$ are all nonnegative.
3. indefinite if and only if $A$ has both positive and negative eigenvalues.
4. negative definite if and only if the eigenvalues of $A$ are all negative.
5. negative semidefinite if and only if the eigenvalues of $A$ are all nonpositive.

Let's see why this theorem holds for the positive semidefinite case. (The others are similar.)

Let's consider $u_i$, an eigenvector of $A$. Then

If all eigenvalues are positive or zero, then all such terms are positive or zero.

Since $A$ is symmetric, it is diagonalizable and so its eigenvectors span $R^n$.

So any $x={\sum }_i{c}_i{u}_i$ can be expressed as a weighted sum of $A$'s eigenvectors $u_1,\dots ,u_n$.

Writing out the expansion of $x^{T}Ax$ in terms of $A$'s eigenvectors, we get only positive or zero terms.

Proof (semi-definite case). Let $\lambda$ be an eigenvalue of $A$ with corresponding eigenvector $u\ne 0$. Then:

If $\lambda <0$ then $Q\left(u\right)$ is negative, so $A$ cannot be positive semi-definite.

Or to state the contrapositive of this statement: if $A$ is positive-semidefinite, then $A$ can only have positive or zero eigenvalues.

Example. Let's look at the four quadratic forms above. Their associated matrices are

Remember that for a diagonal matrix, its eigenvalues equal its diagonal entries.

Example. Is $Q\left(x\right)=3x_1^2+2x_2^2+x_3^2+4x_1{x}_2+4x_2{x}_3$ positive definite?

Solution. Because of all the plus signs, this form "looks" positive definite. But the matrix of the form is

and the eigenvalues of this matrix turn out to be 5, 2, and -1.

So $Q$ is an indefinite quadratic form.

Next lecture we'll talk about constrained optimization problems and how to solve them using eigenvalues.