Linear-Algebra-Done-Right · Unit 21 · Video 4 · Interactive Practice

Matrix SVD: Computing It and Factoring A = BDC*

IKey Formulas

Formula	Name	What it says
$T^*T e_k = \lambda_k e_k$ with $\lambda_k > 0$ , $\ s_k = \sqrt{\lambda_k}$ , $\ f_k = \dfrac{Te_k}{s_k}$	Computing an SVD	The $e_k$ are an orthonormal basis of each eigenspace $E(\lambda, T^*T)$ with $\lambda > 0$ , put together; the $f_k$ then come out orthonormal automatically
$Tv = s_1\langle v, e_1\rangle f_1 + \cdots + s_m\langle v, e_m\rangle f_m$	Singular value decomposition	$m$ = number of positive singular values $= \dim \operatorname{range} T$
$A = BDC^*$	Matrix version	$A \in \mathbf{F}^{p,n}$ of rank $m \ge 1$ : $B = (f_1 \cdots f_m)$ is $p \times m$ , $D = \operatorname{diag}(s_1, \dots, s_m)$ is $m \times m$ , $C = (e_1 \cdots e_m)$ is $n \times m$
$m(p + m + n) < pn$	Storage saving	$B, D, C$ hold $pm + m^2 + nm$ entries against the $pn$ entries of $A$

Key Insight: When $m < n$ , $CC^* \ne I$ , yet $ACC^* = A$ : $CC^*$ fixes each $e_k$ , and on $(\operatorname{span}(e_1, \dots, e_m))^\perp$ both $A$ and $C^*$ are zero.

IIEvery Choice in the Recipe, Checked by $BDC^*$

For the video's $T$ , with $s_1 = 5$ and $s_2 = \sqrt{2}$ , the product $BDC^*$ equals $\mathcal{M}(T)$ only for orthonormal $e$ 's with $f_k = Te_k/s_k$ .

e_1

e_2

f

$T(x_1, x_2, x_3, x_4) = (-5x_4,\ 0,\ x_1 + x_2)$ , $\ \mathcal{M}(T) = \begin{pmatrix} 0&0&0&-5\\ 0&0&0&0\\ 1&1&0&0 \end{pmatrix}$

III $CC^* \ne I$ , Yet $ACC^* = A$

For a rank-one $A$ , $CC^*$ projects onto $\operatorname{span}(e_1)$ , and $A$ sends the discarded part $v_2$ to $0$ .

$A = \begin{pmatrix} 1&1\\ -1&-1 \end{pmatrix}$ , rank $1$ : $\ e_1 = \tfrac{1}{\sqrt2}(1, 1)$ , $s_1 = 2$ , $f_1 = \tfrac{1}{\sqrt2}(1, -1)$ , $\ CC^* = \begin{pmatrix} \tfrac12&\tfrac12\\ \tfrac12&\tfrac12 \end{pmatrix} \ne I$

IVWhen the Factors Save Storage

$A$ takes $pn$ entries and $B, D, C$ take $m(p + m + n)$ , so only a small rank saves.

Size

p \times n

Rank

m

VQuiz Questions

Problem 1 · Singular Values from $T^*T$

Given: $T \in \mathcal{L}(\mathbf{F}^3, \mathbf{F}^2)$ , $T(x_1, x_2, x_3) = (3x_2,\ x_1 + x_3)$ , so that $T^*T(x_1, x_2, x_3) = (x_1 + x_3,\ 9x_2,\ x_1 + x_3)$ . Find the positive singular values of $T$ .

✅ Correct! The positive eigenvalues of

T^*T

are

9

and

2

, and the singular values are their square roots:

s_1 = 3

s_2 = \sqrt{2}

❌ Not quite.

9

and

2

are the positive eigenvalues of

T^*T

; each singular value is the square root

s_k = \sqrt{\lambda_k}

❌ Close, but… the eigenvalue

0

T^*T

is dropped: only positive singular values enter the decomposition, and there are

\dim \operatorname{range} T = 2

of them.

❌ Not quite. The diagonal entries

1, 9, 1

\mathcal{M}(T^*T)

are not its eigenvalues, because that matrix is not diagonal:

T^*T(1, 0, 0) = (1, 0, 1)

, so

(1, 0, 0)

is not an eigenvector.

Show solution

Step one is given. Step two: find the positive eigenvalues of $T^*T$ .

T^*T(0, 1, 0) = (0, 9, 0) = 9(0, 1, 0), \qquad T^*T(1, 0, 1) = (2, 0, 2) = 2(1, 0, 1),

and $T^*T(1, 0, -1) = (0, 0, 0)$ , so the eigenvalues are $9$ , $2$ , $0$ , each with a one-dimensional eigenspace. The eigenvalue $0$ is dropped.

Step three: $s_1 = \sqrt{9} = 3$ and $s_2 = \sqrt{2}$ . Two positive singular values, matching $\dim \operatorname{range} T = 2$ (the range is all of $\mathbf{F}^2$ ).

Problem 2 · Which Change Keeps the Decomposition?

Given: the same $T(x_1, x_2, x_3) = (3x_2,\ x_1 + x_3)$ has the singular value decomposition $Tv = 3\langle v, e_1\rangle f_1 + \sqrt{2}\langle v, e_2\rangle f_2$ with $e_1 = (0, 1, 0)$ , $f_1 = (1, 0)$ , $e_2 = \tfrac{1}{\sqrt2}(1, 0, 1)$ , $f_2 = (0, 1)$ . Which change, keeping $s_1 = 3$ and $s_2 = \sqrt{2}$ and leaving the other vectors alone, still gives a singular value decomposition of $T$ ?

✅ Correct!

3\langle v, -e_1\rangle(-f_1) = 3\langle v, e_1\rangle f_1

, so the sum is unchanged; and

-f_1 = T(-e_1)/3

is exactly what step four produces from

-e_1

❌ Not quite. Flipping only

e_1

makes the first term

3\langle v, -e_1\rangle f_1 = (-3x_2, 0)

, the wrong sign. Step four would give

f_1 = T(-e_1)/3 = (-1, 0)

: the signs of

e_1

and

f_1

change together.

❌ Not quite.

\|(1, 0, 1)\| = \sqrt{2}

, so this

e_2

is not a unit vector, and

f_2 = (0, \sqrt2)

is not one either. The second term becomes

\sqrt{2}(x_1 + x_3)(0, \sqrt{2}) = (0, 2(x_1 + x_3))

: twice too big.

❌ Not quite.

(0, -1)

is a unit vector on the line of

Te_2

, but it is not

Te_2/s_2 = (0, 1)

. The second term becomes

(0, -(x_1 + x_3))

, the wrong sign.

Show solution

Every $f_k$ is tied to its $e_k$ by $f_k = Te_k/s_k$ . Check each option against $Tv = (3x_2,\ x_1 + x_3)$ , using $\langle v, e_1\rangle = x_2$ and $\langle v, e_2\rangle = \tfrac{x_1 + x_3}{\sqrt2}$ .

(a) $3\langle v, -e_1\rangle f_1 = -3x_2(1, 0)$ : first coordinate $-3x_2$ . Fails.
(b) $3\langle v, -e_1\rangle(-f_1) = 3x_2(1, 0)$ : unchanged. Still orthonormal lists. Works.
(c) $\sqrt2\langle v, (1,0,1)\rangle(0, \sqrt2) = (0, 2(x_1 + x_3))$ . Fails (and neither vector is a unit vector).
(d) $\sqrt2 \cdot \tfrac{x_1 + x_3}{\sqrt2}(0, -1) = (0, -(x_1 + x_3))$ . Fails.

Changing the signs of $e_k$ and $f_k$ together always gives another valid decomposition; changing only one of them breaks it.

Problem 3 · Factor a Rank-One Matrix

Given: $A = \begin{pmatrix} 2&2\\ 1&1\\ 2&2 \end{pmatrix}$ has rank $1$ and $A^*A = \begin{pmatrix} 9&9\\ 9&9 \end{pmatrix}$ . Take $C = \tfrac{1}{\sqrt2}\begin{pmatrix} 1\\ 1 \end{pmatrix}$ , so $C^* = \begin{pmatrix} \tfrac{1}{\sqrt2} & \tfrac{1}{\sqrt2} \end{pmatrix}$ . Find $D$ and $B$ with $A = BDC^*$ as in the matrix version of the SVD.

What is $D$ ?

What is $B$ ?

✅ Correct!

BDC^* = \tfrac13\begin{pmatrix} 2\\ 1\\ 2 \end{pmatrix} 3\sqrt2 \begin{pmatrix} \tfrac{1}{\sqrt2} & \tfrac{1}{\sqrt2} \end{pmatrix} = \begin{pmatrix} 2\\ 1\\ 2 \end{pmatrix}\begin{pmatrix} 1 & 1 \end{pmatrix} = A

❌ Not quite.

18

is the positive eigenvalue of

A^*A

; the diagonal of

D

holds the singular value

s_1 = \sqrt{18}

❌ Not quite.

D

m \times m

with

m = \operatorname{rank} A = 1

, and every diagonal entry of

D

is positive; the zero belongs to the

p \times n

diagonal matrix of Video 3, which the matrix version drops.

❌ Not quite.

6 = \|A(1, 1)^t\| = \|(4, 2, 4)\|

, but

(1, 1)

has norm

\sqrt2

. With the unit vector

e_1 = \tfrac{1}{\sqrt2}(1, 1)

\|Ae_1\| = 6/\sqrt2 = 3\sqrt2

❌ Check $D$ . Its diagonal holds the square roots of the positive eigenvalues of

A^*A

❌ Not quite. The column of

B

must be a unit vector, and

\|(2, 1, 2)\| = 3

. It is

f_1 = Ae_1/s_1

❌ Not quite. That is

C

, a vector in

\mathbf{F}^2

B

p \times m = 3 \times 1

: its column is

f_1 = Ae_1/s_1 \in \mathbf{F}^3

❌ Not quite.

-\tfrac13(2, 1, 2)

is a unit vector on the right line, but with this

C

it gives

BDC^* = -A

. Once

e_1

is fixed,

f_1 = Ae_1/s_1

leaves nothing to choose.

❌ Check $B$ . Its column is

f_1 = Ae_1/s_1

Show solution

$A^*A(1, 1) = (18, 18)$ , so the only positive eigenvalue is $18$ , with $e_1 = \tfrac{1}{\sqrt2}(1, 1)$ , the column of $C$ . Then $s_1 = \sqrt{18} = 3\sqrt2$ and $D = \begin{pmatrix} 3\sqrt2 \end{pmatrix}$ , a $1 \times 1$ matrix since $m = 1$ .

f_1 = \frac{Ae_1}{s_1} = \frac{\tfrac{1}{\sqrt2}(4, 2, 4)}{3\sqrt2} = \frac{(4, 2, 4)}{6} = \tfrac13(2, 1, 2), \qquad \|f_1\| = \tfrac13\sqrt{4 + 1 + 4} = 1.

So $B = \tfrac13(2, 1, 2)^t$ , and

BDC^* = \tfrac13\begin{pmatrix} 2\\ 1\\ 2 \end{pmatrix}\cdot 3\sqrt2 \cdot \begin{pmatrix} \tfrac{1}{\sqrt2} & \tfrac{1}{\sqrt2} \end{pmatrix} = \begin{pmatrix} 2&2\\ 1&1\\ 2&2 \end{pmatrix} = A.

Here $m(p + m + n) = 1 \cdot (3 + 1 + 2) = 6 = pn$ : the factors hold exactly as many entries as $A$ .

Problem 4 · When Does the Factorization Pay?

Given: $A$ is a $200 \times 500$ matrix of rank $m \ge 1$ . For which ranks do $B$ , $D$ and $C$ from $A = BDC^*$ together hold fewer entries than $A$ ?

✅ Correct!

121 \cdot 821 = 99{,}341 < 100{,}000

, while

122 \cdot 822 = 100{,}284 > 100{,}000

❌ Close, but…

m \le 142

solves

m(p + n) < pn

, which leaves out the

m^2

entries of

D

. At

m = 142

the factors hold

142 \cdot 842 = 119{,}564

entries.

❌ Not quite. At

m = 200

the factors hold

200 \cdot (200 + 200 + 500) = 180{,}000

entries, more than

pn = 100{,}000

❌ Not quite. That is true of the full-size factors of Video 3 (

p \times p

p \times n

n \times n

). The matrix version keeps only

m

columns: at

m = 10

it holds

10 \cdot 710 = 7{,}100

entries.

Show solution

$A$ has $pn = 200 \cdot 500 = 100{,}000$ entries. $B$ ( $200 \times m$ ), $D$ ( $m \times m$ ) and $C$ ( $500 \times m$ ) hold $200m + m^2 + 500m = m(m + 700)$ .

m(m + 700) < 100{,}000 \iff m^2 + 700m - 100{,}000 < 0 \iff m < \frac{-700 + \sqrt{890{,}000}}{2} \approx 121.7.

So the saving happens exactly for $1 \le m \le 121$ . Check: $121 \cdot 821 = 99{,}341 < 100{,}000$ and $122 \cdot 822 = 100{,}284 > 100{,}000$ .

Solved: 0 / 4

Matrix SVD: Computing It and Factoring A = BDC*

IKey Formulas

IIEvery Choice in the Recipe, Checked by BDC∗BDC^*BDC∗

IIICC∗≠ICC^* \ne ICC∗=I, Yet ACC∗=AACC^* = AACC∗=A

IVWhen the Factors Save Storage

VQuiz Questions

IIEvery Choice in the Recipe, Checked by $BDC^*$

III $CC^* \ne I$ , Yet $ACC^* = A$