Quadratic forms and maximum stretch

Section 6.3 Quadratic forms and maximum stretch

Recall from Definition 5.4.1 that an \(n\times n\) matrix \(B\) determines the scalar-valued function

\begin{equation*} q_B(\mathbf{x})=\mathbf{x}^TB\mathbf{x}. \end{equation*}

In this section, \(B\) will be symmetric. By Theorem 5.3.11, \(B\) has an orthonormal basis of eigenvectors. Lagrange multipliers give these eigenvectors an optimization interpretation.

🔗

Fact 6.3.1. Extrema of a symmetric quadratic form on the unit sphere.

Let \(B\) be a symmetric \(n\times n\) matrix, and let

\begin{equation*} q_B(\mathbf{x})=\mathbf{x}^TB\mathbf{x}. \end{equation*}

If \(\lambda_{\min}\) and \(\lambda_{\max}\) are the smallest and largest eigenvalues of \(B\text{,}\) then

\begin{equation*} \min_{\|\mathbf{x}\|=1}q_B(\mathbf{x}) = \lambda_{\min} \end{equation*}

and

\begin{equation*} \max_{\|\mathbf{x}\|=1}q_B(\mathbf{x}) = \lambda_{\max}. \end{equation*}

These values are achieved at unit eigenvectors for \(\lambda_{\min}\) and \(\lambda_{\max}\text{.}\) More generally, every constrained critical point is a unit eigenvector of \(B\text{.}\)

🔗

Why is this true?.

Use the constraint

\begin{equation*} g(\mathbf{x})=\mathbf{x}^T\mathbf{x}=1. \end{equation*}

Since \(B\) is symmetric,

\begin{equation*} \nabla q_B(\mathbf{x})=2B\mathbf{x}, \qquad \nabla g(\mathbf{x})=2\mathbf{x}. \end{equation*}

On the unit sphere, \(\nabla g(\mathbf{x})\neq\mathbf{0}\text{,}\) so Theorem 6.2.3 applies. Its equations are

\begin{equation*} 2B\mathbf{x}=2\mu\mathbf{x}, \end{equation*}

\begin{equation*} B\mathbf{x}=\mu\mathbf{x}. \end{equation*}

Thus the constrained critical points are unit eigenvectors of \(B\text{.}\) In this calculation, the Lagrange multiplier \(\mu\) is the corresponding eigenvalue.

🔗

If \(B\mathbf{x}=\lambda\mathbf{x}\) and \(\|\mathbf{x}\|=1\text{,}\) then

\begin{align*} q_B(\mathbf{x})\\ \amp=\mathbf{x}^TB\mathbf{x}\\ \amp=\mathbf{x}^T(\lambda\mathbf{x})\\ \amp=\lambda\|\mathbf{x}\|^2\\ \amp=\lambda. \end{align*}

🔗

The unit sphere is closed and bounded, so absolute extrema exist by Theorem 6.1.2. Comparing the eigenvalues gives the smallest and largest values.

🔗

Principal-coordinate view.

The Lagrange calculation identifies the critical directions. Orthogonal diagonalization explains all possible values of the quadratic form.

🔗

By Theorem 5.3.11, write

\begin{equation*} B=QDQ^T, \qquad D= \begin{bmatrix} \lambda_1 \amp \amp 0\\ \amp \ddots \amp\\ 0 \amp \amp \lambda_n \end{bmatrix}, \end{equation*}

where the columns of \(Q\) are orthonormal eigenvectors of \(B\text{.}\) Set

\begin{equation*} \mathbf{c}=Q^T\mathbf{x}. \end{equation*}

Since \(Q\) is orthogonal, Lemma 5.3.3 gives

\begin{equation*} \|\mathbf{c}\|=\|\mathbf{x}\|. \end{equation*}

Also,

\begin{align*} q_B(\mathbf{x})\\ \amp=\mathbf{x}^TB\mathbf{x}\\ \amp=\mathbf{c}^TD\mathbf{c}\\ \amp=\lambda_1c_1^2+\cdots+\lambda_nc_n^2. \end{align*}

On the unit sphere,

\begin{equation*} c_1^2+\cdots+c_n^2=1. \end{equation*}

Thus \(q_B(\mathbf{x})\) is a weighted average of the eigenvalues, with nonnegative weights \(c_i^2\text{.}\) It must lie between the smallest and largest eigenvalues.

🔗

Activity 6.3.2. A non-diagonal quadratic form on the unit circle (U6-LO4, U5-LO3, U5-LO4).

Return to the symmetric matrix from Activity 5.3.6:

\begin{equation*} B= \begin{bmatrix} 2 \amp -1\\ -1 \amp 2 \end{bmatrix}. \end{equation*}

Let

\begin{equation*} \mathbf{x}= \begin{bmatrix} x\\ y \end{bmatrix}, \qquad q_B(\mathbf{x})=\mathbf{x}^TB\mathbf{x}. \end{equation*}

🔗

Write \(q_B(x,y)\) in scalar form.
🔗

🔗
Set up the Lagrange equations for finding the extrema of \(q_B\) subject to

\begin{equation*} x^2+y^2=1. \end{equation*}

🔗

🔗
Find all constrained critical points and their \(q_B\)-values.
🔗

🔗
Find an orthogonal matrix \(Q\) and diagonal matrix \(D\) such that

\begin{equation*} B=QDQ^T, \end{equation*}

with the larger eigenvalue first.

🔗

🔗
If

\begin{equation*} \mathbf{c}=Q^T\mathbf{x}, \end{equation*}

rewrite \(q_B\) in principal coordinates and use this form to identify its absolute maximum and minimum.

🔗

🔗

Solution.

We have

\begin{align*} q_B(x,y)\\ \amp= \begin{bmatrix} x \amp y \end{bmatrix} \begin{bmatrix} 2 \amp -1\\ -1 \amp 2 \end{bmatrix} \begin{bmatrix} x\\ y \end{bmatrix}\\ \amp=2x^2-2xy+2y^2. \end{align*}

🔗

Its gradient is

\begin{equation*} \nabla q_B(x,y) = \begin{bmatrix} 4x-2y\\ -2x+4y \end{bmatrix}. \end{equation*}

🔗

For

\begin{equation*} g(x,y)=x^2+y^2, \end{equation*}

we have

\begin{equation*} \nabla g(x,y) = \begin{bmatrix} 2x\\ 2y \end{bmatrix}. \end{equation*}

🔗

The Lagrange equations are therefore

\begin{equation*} \begin{bmatrix} 4x-2y\\ -2x+4y \end{bmatrix} = \mu \begin{bmatrix} 2x\\ 2y \end{bmatrix}, \qquad x^2+y^2=1. \end{equation*}

Dividing the gradient equation by \(2\) gives

\begin{equation*} B\mathbf{x}=\mu\mathbf{x}. \end{equation*}

🔗

The characteristic polynomial is

\begin{align*} \det(B-\mu I)\\ \amp=(2-\mu)^2-1\\ \amp=(\mu-1)(\mu-3). \end{align*}

🔗

For \(\mu=1\text{,}\) the eigenvectors satisfy \(x=y\text{.}\) The corresponding unit vectors are

\begin{equation*} \frac{1}{\sqrt2} \begin{bmatrix} 1\\ 1 \end{bmatrix} \qquad\text{and}\qquad -\frac{1}{\sqrt2} \begin{bmatrix} 1\\ 1 \end{bmatrix}. \end{equation*}

At either point,

\begin{equation*} q_B(\mathbf{x})=1. \end{equation*}

🔗

For \(\mu=3\text{,}\) the eigenvectors satisfy \(x=-y\text{.}\) The corresponding unit vectors are

\begin{equation*} \frac{1}{\sqrt2} \begin{bmatrix} 1\\ -1 \end{bmatrix} \qquad\text{and}\qquad -\frac{1}{\sqrt2} \begin{bmatrix} 1\\ -1 \end{bmatrix}. \end{equation*}

At either point,

\begin{equation*} q_B(\mathbf{x})=3. \end{equation*}

🔗

Choose

\begin{equation*} Q= \frac{1}{\sqrt2} \begin{bmatrix} 1 \amp 1\\ -1 \amp 1 \end{bmatrix}, \qquad D= \begin{bmatrix} 3 \amp 0\\ 0 \amp 1 \end{bmatrix}. \end{equation*}

The columns of \(Q\) are orthonormal eigenvectors of \(B\text{,}\) so

\begin{equation*} B=QDQ^T. \end{equation*}

🔗

\begin{equation*} \mathbf{c}=Q^T\mathbf{x}, \end{equation*}

then

\begin{equation*} q_B(\mathbf{x})=3c_1^2+c_2^2. \end{equation*}

On the unit circle,

\begin{equation*} c_1^2+c_2^2=1. \end{equation*}

Therefore the absolute maximum is \(3\text{,}\) attained when \(c_1^2=1\text{,}\) and the absolute minimum is \(1\text{,}\) attained when \(c_2^2=1\text{.}\) These are the same values and directions found from the Lagrange equations.

🔗

Maximum stretch of a matrix.

Now let \(A\) be an \(m\times n\) matrix. The matrix \(A\) need not be square or symmetric. One way to study the matrix map

\begin{equation*} \mathbf{x}\longmapsto A\mathbf{x} \end{equation*}

is to ask which unit inputs produce the largest output lengths.

🔗

Because lengths are nonnegative, maximizing \(\|A\mathbf{x}\|\) is equivalent to maximizing its square. We have

\begin{align*} \|A\mathbf{x}\|^2\\ \amp=(A\mathbf{x})^T(A\mathbf{x})\\ \amp=\mathbf{x}^TA^TA\mathbf{x}. \end{align*}

Thus maximum stretch is a quadratic-form problem for the symmetric matrix \(A^TA\text{.}\)

🔗

The eigenvalues of \(A^TA\) are nonnegative. Indeed, if

\begin{equation*} A^TA\mathbf{v}=\lambda\mathbf{v} \end{equation*}

for a nonzero vector \(\mathbf{v}\text{,}\) then

\begin{align*} \lambda\|\mathbf{v}\|^2\\ \amp=\mathbf{v}^TA^TA\mathbf{v}\\ \amp=\|A\mathbf{v}\|^2\\ \amp\geq 0. \end{align*}

Therefore \(\lambda\geq 0\text{.}\)

🔗

Order the eigenvalues of \(A^TA\) from largest to smallest and take their nonnegative square roots:

\begin{equation*} \sigma_i=\sqrt{\lambda_i}. \end{equation*}

These numbers are the singular values of \(A\text{.}\) A unit eigenvector \(\mathbf{v}_i\) of \(A^TA\) is a right singular vector of \(A\text{.}\) Since

\begin{align*} \|A\mathbf{v}_i\|^2\\ \amp=\mathbf{v}_i^TA^TA\mathbf{v}_i\\ \amp=\lambda_i, \end{align*}

we have

\begin{equation*} \|A\mathbf{v}_i\|=\sigma_i. \end{equation*}

Thus the right singular vectors are special input directions, and the singular values are their stretch factors. In particular,

\begin{equation*} \max_{\|\mathbf{x}\|=1}\|A\mathbf{x}\| = \sigma_1. \end{equation*}

🔗

Activity 6.3.3. A small stretch computation (U6-LO4).

Let

\begin{equation*} A= \begin{bmatrix} 3 \amp 0\\ 0 \amp 1 \end{bmatrix}. \end{equation*}

Let

\begin{equation*} \mathbf{e}_1= \begin{bmatrix} 1\\ 0 \end{bmatrix}, \qquad \mathbf{e}_2= \begin{bmatrix} 0\\ 1 \end{bmatrix}. \end{equation*}

🔗

Compute \(A\mathbf{e}_1\) and \(A\mathbf{e}_2\text{.}\)
🔗

🔗
Compute \(\|A\mathbf{e}_1\|\) and \(\|A\mathbf{e}_2\|\text{.}\)
🔗

🔗
Compute \(A^TA\text{.}\)
🔗

🔗
Find the eigenvalues of \(A^TA\text{.}\)
🔗

🔗
What are the singular values of \(A\text{?}\)
🔗

🔗
Which unit direction is stretched most?
🔗

🔗

Solution.

We have

\begin{equation*} A\mathbf{e}_1= \begin{bmatrix} 3\\ 0 \end{bmatrix}, \qquad A\mathbf{e}_2= \begin{bmatrix} 0\\ 1 \end{bmatrix}. \end{equation*}

Thus

\begin{equation*} \|A\mathbf{e}_1\|=3, \qquad \|A\mathbf{e}_2\|=1. \end{equation*}

Also

\begin{equation*} A^TA= \begin{bmatrix} 3 \amp 0\\ 0 \amp 1 \end{bmatrix}^T \begin{bmatrix} 3 \amp 0\\ 0 \amp 1 \end{bmatrix} = \begin{bmatrix} 9 \amp 0\\ 0 \amp 1 \end{bmatrix}. \end{equation*}

The eigenvalues of \(A^TA\) are \(9\) and \(1\text{.}\) Therefore the singular values of \(A\) are

\begin{equation*} \sigma_1=3, \qquad \sigma_2=1. \end{equation*}

The direction \(\mathbf{e}_1\) is stretched most. This is the simplest version of the question

\begin{equation*} \max_{\|\mathbf{x}\|=1}\|A\mathbf{x}\|. \end{equation*}

🔗

Activity 6.3.4. Reading the same stretch in code (U6-LO4).

The following code repeats the previous activity using \(A^TA\text{.}\)

🔗

import numpy as np

A = np.array([[3., 0.],
              [0., 1.]])

B = A.T @ A
eigvals, eigvecs = np.linalg.eigh(B)

singular_values = np.sqrt(eigvals[::-1])
dominant_direction = eigvecs[:, -1]

B, eigvals, singular_values, dominant_direction

Output:

🔗

(array([[9., 0.],
        [0., 1.]]),
 array([1., 9.]),
 array([3., 1.]),
 array([1., 0.]))

What mathematical matrix is stored in B?
🔗

🔗
Why are the entries of eigvals squared stretch factors?
🔗

🔗
Why does the code take a square root?
🔗

🔗
Why does eigvecs[:, -1] give the most-stretched input direction?
🔗

🔗
What value of \(\max_{\|\mathbf{x}\|=1}\|A\mathbf{x}\|\) does the code predict?
🔗

🔗

Solution.

The matrix B is \(A^TA\text{.}\) The entries of eigvals are eigenvalues of \(A^TA\text{,}\) so they are values of \(\|A\mathbf{x}\|^2\) for special unit input directions. The code takes a square root because singular values measure \(\|A\mathbf{x}\|\text{,}\) not \(\|A\mathbf{x}\|^2\text{.}\) The command np.linalg.eigh lists eigenvalues in increasing order, so the largest eigenvalue is last, and eigvecs[:, -1] is its eigenvector. The largest singular value is \(3\text{,}\) so

\begin{equation*} \max_{\|\mathbf{x}\|=1}\|A\mathbf{x}\|=3. \end{equation*}

🔗

The same quadratic-form problem appears when a matrix stores centered data. Section 6.4 uses it to choose directions that capture variation in a data set.

🔗

Prev Top Next