Linear AlgebraThe Singular Value Decomposition4 of 6
The Singular Value Decomposition · 4

The Pseudoinverse: The Best Effort Inverse

We want to solve Ax=bAx = \target{b} even when the matrix AA has no inverse.

1

Why Inverses Break and the Two Rules for A+A^+

The pseudoinverse A+A^+ is the best-effort inverse of a matrix AA: when Ax=bAx = \target{b} cannot be solved the normal way, A+A^+ finds the shortest input vector x+\rowpart{x^+} that gets the output Ax+A\rowpart{x^+} as close as possible to the target b\target{b}.

Why Inverses Break and the Two Rules for A⁺
Ax=bA x = \htmlClass{lc-blue}{b}
input space\text{input space}
output space\text{output space}
xx
b\htmlClass{lc-blue}{b}
AA
A−1A^{-1}

When AA squashes space or has different input and output dimensions, A+A^+ replaces A−1A^{-1} by following one rule in the output space and one rule in the input space:

x+=A+⏟pseudoinversebsuch thatAx+=b^⏟closest point incolumn spaceandx+⏟shortest inputin row space⊥null space\displaystyle \begin{aligned} \rowpart{x^+} &= \underbrace{A^+}_{\text{pseudoinverse}} \target{b} \quad \text{such that} \\ A\rowpart{x^+} &= \underbrace{\reached{\hat{b}}}_{\substack{\text{closest point in} \\ \text{column space}}} \quad \text{and} \\ \underbrace{\rowpart{x^+}}_{\substack{\text{shortest input} \\ \text{in row space}}} &\perp \lost{\text{null space}} \end{aligned}

Moving the target b\target{b} perpendicular to the column space does not change its orthogonal projection b^\reached{\hat{b}} or the dashed line of inputs that map to it, and the shortest input x+\rowpart{x^+} always meets that solution line at a 90∘90^\circ angle inside the row space.

The shortest input stays on the row space for every output vector, and never changes when that output moves perpendicular to the column space.
2

Pseudoinverting Diagonal Matrices

To build a matrix that follows both rules, we start with the simplest case: finding the pseudoinverse Σ+\Sigma^+ of a diagonal matrix Σ\Sigma that only stretches or squashes along the standard axes.

Pseudoinverting Diagonal Matrices
A=[2000]A+=  ?\displaystyle \begin{aligned} A &= \begin{bmatrix} 2 & 0 \\ 0 & 0 \end{bmatrix} \\[6pt] A^{+} &= \;? \end{aligned}

For any diagonal matrix Σ\Sigma, transpose the matrix shape so outputs map back to inputs, invert every nonzero diagonal stretch σi→1σi\stretch{\sigma_i} \to \stretch{\frac{1}{\sigma_i}}, and leave every 0\lost{0} as 0\lost{0}:

Σ=[200500]3×2⟶Σ+=[12000150]2×3\displaystyle \Sigma = \begin{bmatrix} \stretch{2} & 0 \\ 0 & \stretch{5} \\ \lost{0} & \lost{0} \end{bmatrix}_{3 \times 2} \quad \longrightarrow \quad \Sigma^+ = \begin{bmatrix} \stretch{\frac{1}{2}} & 0 & \lost{0} \\ 0 & \stretch{\frac{1}{5}} & \lost{0} \end{bmatrix}_{2 \times 3}
input space\text{input space}
xx
yy
row space\htmlClass{lc-green}{\text{row space}}
null space\htmlClass{lc-orange}{\text{null space}}
x+=[30]\htmlClass{lc-green}{x^+ = \begin{bmatrix} 3 \\ 0 \end{bmatrix}}
x=3\htmlClass{lc-violet}{x = 3}
output space\text{output space}
xx
yy
column space\htmlClass{lc-violet}{\text{column space}}
b=[64]\htmlClass{lc-blue}{b = \begin{bmatrix} 6 \\ 4 \end{bmatrix}}
b^=[60]\htmlClass{lc-violet}{\hat{b} = \begin{bmatrix} 6 \\ 0 \end{bmatrix}}
Text solution
Invert the nonzero stretch and keep the zeroFor A=[2000]A = \begin{bmatrix} \stretch{2} & 0 \\ 0 & \lost{0} \end{bmatrix} and target b=[64]\target{b} = \target{\begin{bmatrix} 6 \\ 4 \end{bmatrix}}, turn the horizontal stretch 2\stretch{2} into 12\stretch{\frac{1}{2}} and leave the squashed vertical 0\lost{0} alone.
A=[2000]⟶A+=[12000]\displaystyle A = \begin{bmatrix} \stretch{2} & 0 \\ 0 & \lost{0} \end{bmatrix} \quad \longrightarrow \quad A^+ = \begin{bmatrix} \stretch{\frac{1}{2}} & 0 \\ 0 & \lost{0} \end{bmatrix}
Multiply A+bA^+\target{b} to find the shortest inputThe zero in the bottom-right entry zeroes out the unreachable 44 and puts a 00 in the null-space yy-coordinate.
x+=A+b=[12000][64]=[30]\displaystyle \rowpart{x^+} = A^+\target{b} = \begin{bmatrix} \stretch{\frac{1}{2}} & 0 \\ 0 & \lost{0} \end{bmatrix} \target{\begin{bmatrix} 6 \\ 4 \end{bmatrix}} = \rowpart{\begin{bmatrix} 3 \\ 0 \end{bmatrix}}
Multiply Ax+A\rowpart{x^+} to find the closest reachable outputMultiplying x+\rowpart{x^+} by AA lands on the orthogonal projection of b\target{b} onto the xx-axis.
b^=Ax+=[2000][30]=[60]\displaystyle \reached{\hat{b}} = A\rowpart{x^+} = \begin{bmatrix} \stretch{2} & 0 \\ 0 & \lost{0} \end{bmatrix} \rowpart{\begin{bmatrix} 3 \\ 0 \end{bmatrix}} = \reached{\begin{bmatrix} 6 \\ 0 \end{bmatrix}}

So x+=[30]\rowpart{x^+} = \rowpart{\begin{bmatrix} 3 \\ 0 \end{bmatrix}} is the shortest input vector that lands on b^=[60]\reached{\hat{b}} = \reached{\begin{bmatrix} 6 \\ 0 \end{bmatrix}}, the closest point on the xx-axis to [64]\target{\begin{bmatrix} 6 \\ 4 \end{bmatrix}}.

3

The SVD Pseudoinverse: A+=VΣ+UTA^+ = V\Sigma^+U^T

Now we want to find A+A^+ for any matrix AA that squashes space at an angle, by factoring A=UΣVTA = U\Sigma V^T with the Singular Value Decomposition (SVD) and undoing each step.

The SVD Pseudoinverse: A⁺ = VΣ⁺Uᵀ
A=Urotate    Σstretch    VTrotateA+=  ?\displaystyle \begin{aligned} A &= \underset{\text{rotate}}{U}\;\; \underset{\text{stretch}}{\Sigma}\;\; \underset{\text{rotate}}{V^{T}} \\[6pt] A^{+} &= \;? \end{aligned}

Undoing the three steps of A=UΣVTA = U\Sigma V^T in reverse order gives the general formula for the pseudoinverse:

A\displaystyle A =UΣVT⟶A+\displaystyle = U\Sigma V^T \quad \longrightarrow \quad A^+ =VΣ+UT\displaystyle = V\Sigma^+U^T
Text solution
Find the output directions UU, input directions VV, and stretches Σ\SigmaFor A=[1−11−1]A = \begin{bmatrix} 1 & -1 \\ 1 & -1 \end{bmatrix} and b=[62]\target{b} = \target{\begin{bmatrix} 6 \\ 2 \end{bmatrix}}, divide the column-space direction [11]\reached{\begin{bmatrix} 1 \\ 1 \end{bmatrix}} by its length 2\sqrt{2} to get u1\reached{u_1}, do the same for the row-space direction [1−1]\rowpart{\begin{bmatrix} 1 \\ -1 \end{bmatrix}} to get v1\rowpart{v_1} and for their perpendiculars to get u2\lost{u_2} and v2\lost{v_2}, and use Av1=2u1A\rowpart{v_1} = \stretch{2}\reached{u_1} to find the stretches σ1=2\stretch{\sigma_1} = \stretch{2} and σ2=0\lost{\sigma_2} = \lost{0}.
U=12[1−111],Σ=[2000],V=12[11−11]\displaystyle \begin{aligned} U &= \frac{1}{\sqrt{2}}\begin{bmatrix} \reached{1} & \lost{-1} \\ \reached{1} & \lost{1} \end{bmatrix}, \\ \Sigma &= \begin{bmatrix} \stretch{2} & 0 \\ 0 & \lost{0} \end{bmatrix}, \\ V &= \frac{1}{\sqrt{2}}\begin{bmatrix} \rowpart{1} & \lost{1} \\ \rowpart{-1} & \lost{1} \end{bmatrix} \end{aligned}
Pseudoinvert the diagonal matrix Σ\SigmaInvert the nonzero singular value 2\stretch{2} and keep the zero on the diagonal.
Σ+=[12000]\displaystyle \Sigma^+ = \begin{bmatrix} \stretch{\frac{1}{2}} & 0 \\ 0 & \lost{0} \end{bmatrix}
Multiply VΣ+UTV\Sigma^+U^T in reverse orderCombine the two 12\frac{1}{\sqrt{2}} factors in front into 12\frac{1}{2} and multiply the three matrices to get A+A^+.
A+=VΣ+UT=(12[11−11])[12000](12[11−11])=12[120−120][11−11]=14[11−1−1]\displaystyle \begin{aligned} A^+ &= V\Sigma^+U^T \\ &= \left(\frac{1}{\sqrt{2}}\begin{bmatrix} \rowpart{1} & \lost{1} \\ \rowpart{-1} & \lost{1} \end{bmatrix}\right)\begin{bmatrix} \stretch{\frac{1}{2}} & 0 \\ 0 & \lost{0} \end{bmatrix} \\ &\qquad \left(\frac{1}{\sqrt{2}}\begin{bmatrix} \reached{1} & \reached{1} \\ \lost{-1} & \lost{1} \end{bmatrix}\right) \\ &= \frac{1}{2}\begin{bmatrix} \frac{1}{2} & 0 \\ -\frac{1}{2} & 0 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix} \\ &= \frac{1}{4}\begin{bmatrix} 1 & 1 \\ -1 & -1 \end{bmatrix} \end{aligned}
Multiply A+bA^+\target{b} to get the best-effort inputMultiply A+A^+ by the target vector b=[62]\target{b} = \target{\begin{bmatrix} 6 \\ 2 \end{bmatrix}}.
x+=A+b=14[11−1−1][62]=14[8−8]=[2−2]\displaystyle \rowpart{x^+} = A^+\target{b} = \frac{1}{4}\begin{bmatrix} 1 & 1 \\ -1 & -1 \end{bmatrix}\target{\begin{bmatrix} 6 \\ 2 \end{bmatrix}} = \frac{1}{4}\begin{bmatrix} 8 \\ -8 \end{bmatrix} = \rowpart{\begin{bmatrix} 2 \\ -2 \end{bmatrix}}

So x+=[2−2]\rowpart{x^+} = \rowpart{\begin{bmatrix} 2 \\ -2 \end{bmatrix}} is the shortest input (squared length 88) that maps to b^=Ax+=[44]\reached{\hat{b}} = A\rowpart{x^+} = \reached{\begin{bmatrix} 4 \\ 4 \end{bmatrix}}, the closest point on the column-space line y=xy = x to [62]\target{\begin{bmatrix} 6 \\ 2 \end{bmatrix}}.

Rotating the output space by UTU^T lines the tilted column space up with the horizontal axis so the zero in Σ+\Sigma^+ zeroes out the vertical gap, and VV rotates the remaining horizontal vector straight into the tilted row space as x+\rowpart{x^+}.

The first rotation lines the tilted column space up with the horizontal axis so the middle step can zero out the vertical gap, and the last rotation turns what remains straight into the row space.
4

Shortcut for Tall Matrices with Independent Columns

Finding a full SVD takes work, so we want a direct shortcut when AA is a tall matrix with independent columns.

Shortcut for Tall Matrices with Independent Columns
A+=  ?A^{+} = \;?

Because the gap vector b−Ax+\lost{b - Ax^+} is perpendicular to every column of AA, multiplying the gap by ATA^T gives zero and lets us solve directly for x+\rowpart{x^+}:

AT(b−Ax+)=0⟹ATAx+=ATb⟹x+=(ATA)−1AT⏟A+ (independent columns)b\displaystyle \begin{aligned} A^T(\lost{b - Ax^+}) &= 0 \\ \Longrightarrow \quad A^TA\rowpart{x^+} &= A^T\target{b} \\ \Longrightarrow \quad \rowpart{x^+} &= \underbrace{(A^TA)^{-1}A^T}_{A^+\text{ (independent columns)}} \target{b} \end{aligned}

Be careful not to confuse ATbA^T\target{b} with the projection b^\reached{\hat{b}}: multiplying by ATA^T takes dot products with the columns of AA, which sends b\target{b} into the smaller input space while ignoring the perpendicular gap (ATb=ATb^A^T\target{b} = A^T\reached{\hat{b}}). Once you have x+=A+b\rowpart{x^+} = A^+\target{b}, multiply by AA on the left to get the projection b^=Ax+\reached{\hat{b}} = A\rowpart{x^+} back in the output space.

5

Shortcut for Wide Matrices with Independent Rows

Now take the opposite case: a direct shortcut for a wide matrix with independent rows, where Ax=bAx = \target{b} has many solutions and we want the shortest one.

Shortcut for Wide Matrices with Independent Rows
[110011][x1x2x3]=[33]x+=  ?\displaystyle \begin{aligned} \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} &= \htmlClass{lc-blue}{\begin{bmatrix} 3 \\ 3 \end{bmatrix}} \\[6pt] \htmlClass{lc-green}{x^{+}} &= \;? \end{aligned}

To avoid any extra length in the null space, x+\rowpart{x^+} must be a combination of the rows of AA, written as x+=ATy\rowpart{x^+} = A^Ty for some weight vector yy:

A(ATy)=b⟹y=(AAT)−1b⟹x+=AT(AAT)−1⏟A+ (independent rows)b\displaystyle \begin{aligned} A(A^Ty) &= \target{b} \\ \Longrightarrow \quad y &= (AA^T)^{-1}\target{b} \\ \Longrightarrow \quad \rowpart{x^+} &= \underbrace{A^T(AA^T)^{-1}}_{A^+\text{ (independent rows)}} \target{b} \end{aligned}
Text solution
Multiply AATAA^T to form the small square matrixFor [110011][x1x2x3]=[33]\begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \target{\begin{bmatrix} 3 \\ 3 \end{bmatrix}}, multiply the 2×32 \times 3 matrix AA by its 3×23 \times 2 transpose ATA^T.
AAT=[110011][101101]=[2112]\displaystyle AA^T = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}
Invert AATAA^T and multiply by ATA^T on the leftUse det⁡(AAT)=4−1=3\det(AA^T) = 4 - 1 = 3 to invert the 2×22 \times 2 matrix, then multiply AT(AAT)−1A^T(AA^T)^{-1} to get A+A^+.
(AAT)−1=13[2−1−12]⟹A+=AT(AAT)−1=[101101]13[2−1−12]=13[2−111−12]\displaystyle \begin{aligned} (AA^T)^{-1} &= \frac{1}{3}\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} \\ \Longrightarrow \quad A^+ &= A^T(AA^T)^{-1} \\ &= \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix}\frac{1}{3}\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} \\ &= \frac{1}{3}\begin{bmatrix} 2 & -1 \\ 1 & 1 \\ -1 & 2 \end{bmatrix} \end{aligned}
Multiply A+bA^+\target{b} to find the shortest solutionMultiply A+A^+ by the target vector b=[33]\target{b} = \target{\begin{bmatrix} 3 \\ 3 \end{bmatrix}}.
x+=A+b=13[2−111−12][33]=13[363]=[121]\displaystyle \rowpart{x^+} = A^+\target{b} = \frac{1}{3}\begin{bmatrix} 2 & -1 \\ 1 & 1 \\ -1 & 2 \end{bmatrix}\target{\begin{bmatrix} 3 \\ 3 \end{bmatrix}} = \frac{1}{3}\begin{bmatrix} 3 \\ 6 \\ 3 \end{bmatrix} = \rowpart{\begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix}}

So x+=[121]\rowpart{x^+} = \rowpart{\begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix}} solves the system with squared length 12+22+12=61^2 + 2^2 + 1^2 = 6, shorter than other solutions like [030]\begin{bmatrix} 0 \\ 3 \\ 0 \end{bmatrix} (squared length 99) because it has no part in the null space.

Every point xx along the solution line in 3D input space maps to the exact same output b\target{b}, and moving away from the 90∘90^\circ row-space intersection x+\rowpart{x^+} only adds null-space length to ∥x∥2\|x\|^2.

Every point on the line of solutions gives the exact same output, and moving away from the row space along the line only adds length from the null space.
6

AA+AA^+ and A+AA^+A as Projection Matrices

Finally, we want to know what happens when we multiply AA and A+A^+ together. Because any part of the target off the column space can never be reached, and any part of the input squashed into the null space is gone for good, AA+AA^+ and A+AA^+A are not always the identity matrix II. Instead, they are orthogonal projection matrices.

AA⁺ and A⁺A as Projection Matrices
input space\text{input space}
row space\htmlClass{lc-green}{\text{row space}}
null space\htmlClass{lc-orange}{\text{null space}}
xx
A+ ⁣A=  ?A^{+}\!A = \;?
output space\text{output space}
column space\htmlClass{lc-violet}{\text{column space}}
b\htmlClass{lc-blue}{b}
AA+=  ?A A^{+} = \;?

Multiplying in each order projects a vector onto the subspace that isn't squashed:

AA+⏟column-spaceprojectionb=A(A+b)=Ax+=b^,A+A⏟row-spaceprojectionx=A+(Ax)=xrow\displaystyle \begin{aligned} \underbrace{AA^+}_{\substack{\text{column-space} \\ \text{projection}}} \target{b} &= A(A^+\target{b}) = A\rowpart{x^+} = \reached{\hat{b}}, \\ \underbrace{A^+A}_{\substack{\text{row-space} \\ \text{projection}}} x &= A^+(\reached{Ax}) = \rowpart{x_{\text{row}}} \end{aligned}

Writing both products using the SVD shows that ΣΣ+\Sigma\Sigma^+ and Σ+Σ\Sigma^+\Sigma are diagonal matrices with 1\stretch{1}s along the directions that survive and 0\lost{0}s along the unreachable or squashed directions:

AA+=U(ΣΣ+)UT,A+A=V(Σ+Σ)VT\displaystyle \begin{aligned} AA^+ &= U(\Sigma\Sigma^+)U^T, \\ A^+A &= V(\Sigma^+\Sigma)V^T \end{aligned}

Because AA squashes xnull\lost{x_{\text{null}}} to zero, the round trip A+AxA^+Ax keeps only the row-space part xrow\rowpart{x_{\text{row}}}, and gives back xx only if xx started in the row space.

A round trip forward and back through the pseudoinverse drops the null-space part of any input and lands on its shadow in the row space.

Key concepts

Whenever you need to solve Ax=bAx = \target{b}, first check whether you need a pseudoinverse at all: if AA is a square matrix with independent columns (det⁡(A)≠0\det(A) \neq 0, such as A=[2003]A = \begin{bmatrix} \stretch{2} & 0 \\ 0 & \stretch{3} \end{bmatrix}), every output can be reached from a single input and the regular inverse x=A−1b=[120013]bx = A^{-1}\target{b} = \begin{bmatrix} \stretch{\tfrac{1}{2}} & 0 \\ 0 & \stretch{\tfrac{1}{3}} \end{bmatrix}\target{b} solves it directly. When AA is rectangular or has determinant 00, x+=A+b\rowpart{x^+} = A^+\target{b} gives the shortest input in the row space that lands on the closest point b^=Ax+\reached{\hat{b}} = A\rowpart{x^+} in the column space.

Pick the formula for A+A^+ by checking which case you have:

Key concept

If the matrix is already a diagonal stretch Σ\Sigma, transpose the matrix shape, invert the nonzero entries (σi→1σi\stretch{\sigma_i} \to \stretch{\tfrac{1}{\sigma_i}}), and leave zeros as 0\lost{0}: for Σ=[2000]\Sigma = \begin{bmatrix} \stretch{2} & 0 \\ 0 & \lost{0} \end{bmatrix}, Σ+=[12000]\Sigma^+ = \begin{bmatrix} \stretch{\tfrac{1}{2}} & 0 \\ 0 & \lost{0} \end{bmatrix}.

Key concept

If AA is tall with independent columns (such as a 3×23 \times 2 matrix whose columns are not multiples of each other), ATAA^TA is the small invertible 2×22 \times 2 square matrix, so use A+=(ATA)−1ATA^+ = (A^TA)^{-1}A^T.

Key concept

If AA is wide with independent rows (such as a 2×32 \times 3 matrix whose rows are not multiples of each other), AATAA^T is the small invertible 2×22 \times 2 square matrix, so use A+=AT(AAT)−1A^+ = A^T(AA^T)^{-1}.

Key concept

If AA has dependent columns and dependent rows (such as A=[1−11−1]A = \begin{bmatrix} 1 & -1 \\ 1 & -1 \end{bmatrix}, where det⁡(ATA)=0\det(A^TA) = 0 and det⁡(AAT)=0\det(AA^T) = 0), neither shortcut matrix is invertible, so factor A=UΣVTA = U\Sigma V^T and undo the steps in reverse with A+=VΣ+UTA^+ = V\Sigma^+U^T.

Once you have A+A^+, multiplying AA and A+A^+ gives orthogonal projections: AA+AA^+ has AA on the left and projects any output vector b\target{b} onto the column space (b^=AA+b\reached{\hat{b}} = AA^+\target{b}), while A+AA^+A has A+A^+ on the left and projects any input vector xx onto the row space (xrow=A+Ax\rowpart{x_{\text{row}}} = A^+Ax, with null-space part xnull=x−xrow\lost{x_{\text{null}}} = x - \rowpart{x_{\text{row}}}).

7

Practice

1

Given the 3×23 \times 2 diagonal stretch matrix Σ=[400000]\Sigma = \begin{bmatrix} 4 & 0 \\ 0 & 0 \\ 0 & 0 \end{bmatrix} and the target vector b=[83−5]\target{b} = \target{\begin{bmatrix} 8 \\ 3 \\ -5 \end{bmatrix}}, find the pseudoinverse Σ+\Sigma^+, the best-effort input x+=Σ+b\rowpart{x^+} = \Sigma^+\target{b}, and the closest reachable output b^=Σx+\reached{\hat{b}} = \Sigma \rowpart{x^+}.

Σ\Sigma maps 22 inputs to 33 outputs. What dimensions must Σ+\Sigma^+ have to map 33 outputs back to 22 inputs, and what happens to the 44 and the 00s?

Transpose the 3×23 \times 2 shape into 2×32 \times 3, invert the nonzero stretch 4→14\stretch{4} \to \stretch{\frac{1}{4}}, and leave every 0\lost{0} as 0\lost{0} (do not leave Σ+\Sigma^+ as a 3×23 \times 2 matrix, which cannot multiply the 3×13 \times 1 target b\target{b}):
Σ+=[1400000]\displaystyle \Sigma^+ = \begin{bmatrix} \stretch{\frac{1}{4}} & 0 & \lost{0} \\ 0 & \lost{0} & \lost{0} \end{bmatrix}
Multiply Σ+b\Sigma^+\target{b} to find x+\rowpart{x^+}, then multiply Σx+\Sigma \rowpart{x^+} to find b^\reached{\hat{b}} (do not stop at x+\rowpart{x^+} and write [200]\begin{bmatrix} 2 \\ 0 \\ 0 \end{bmatrix} for b^\reached{\hat{b}}, since multiplying by Σ\Sigma stretches the first coordinate back by 4\stretch{4}):
x+=Σ+b=[1400000][83−5]=[20],b^=Σx+=[400000][20]=[800]\displaystyle \begin{aligned} \rowpart{x^+} &= \Sigma^+\target{b} = \begin{bmatrix} \stretch{\frac{1}{4}} & 0 & \lost{0} \\ 0 & \lost{0} & \lost{0} \end{bmatrix}\target{\begin{bmatrix} 8 \\ 3 \\ -5 \end{bmatrix}} = \rowpart{\begin{bmatrix} 2 \\ 0 \end{bmatrix}}, \\ \reached{\hat{b}} &= \Sigma \rowpart{x^+} = \begin{bmatrix} \stretch{4} & 0 \\ 0 & \lost{0} \\ \lost{0} & \lost{0} \end{bmatrix}\rowpart{\begin{bmatrix} 2 \\ 0 \end{bmatrix}} = \reached{\begin{bmatrix} 8 \\ 0 \\ 0 \end{bmatrix}} \end{aligned}
2

The tall matrix A=[111101]A = \begin{bmatrix} 1 & 1 \\ 1 & 1 \\ 0 & 1 \end{bmatrix} has independent columns. Find its pseudoinverse A+=(ATA)−1ATA^+ = (A^TA)^{-1}A^T, then find the best-effort input x+\rowpart{x^+} and the column-space projection b^=Ax+\reached{\hat{b}} = A\rowpart{x^+} for the unreachable target b=[261]\target{b} = \target{\begin{bmatrix} 2 \\ 6 \\ 1 \end{bmatrix}}.

Multiply ATAA^TA first to get a 2×22 \times 2 matrix you can invert; once you have x+=A+b\rowpart{x^+} = A^+\target{b}, which matrix sends x+\rowpart{x^+} back into the 3D output space?

Compute ATAA^TA and invert it using det⁡(ATA)=6−4=2\det(A^TA) = 6 - 4 = 2 (watch the minus signs on the off-diagonal entries when inverting ATAA^TA, since leaving them positive gives 12[3222]\frac{1}{2}\begin{bmatrix} 3 & 2 \\ 2 & 2 \end{bmatrix} and the wrong input [2117]\begin{bmatrix} 21 \\ 17 \end{bmatrix}):
ATA=[110111][111101]=[2223]⟹(ATA)−1=12[3−2−22]\displaystyle \begin{aligned} A^TA &= \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & 1 \\ 0 & 1 \end{bmatrix} \\ &= \begin{bmatrix} 2 & 2 \\ 2 & 3 \end{bmatrix} \\ \Longrightarrow \quad (A^TA)^{-1} &= \frac{1}{2}\begin{bmatrix} 3 & -2 \\ -2 & 2 \end{bmatrix} \end{aligned}
Multiply (ATA)−1AT(A^TA)^{-1}A^T to find A+A^+, then compute x+=A+b\rowpart{x^+} = A^+\target{b} and b^=Ax+\reached{\hat{b}} = A\rowpart{x^+} (do not confuse ATb=[89]A^T\target{b} = \begin{bmatrix} 8 \\ 9 \end{bmatrix} in the 2D input space with the 3D projection b^=Ax+\reached{\hat{b}} = A\rowpart{x^+}):
A+=12[3−2−22][110111]=[1212−1001],x+=A+b=[31],b^=Ax+=[441]\displaystyle \begin{aligned} A^+ &= \frac{1}{2}\begin{bmatrix} 3 & -2 \\ -2 & 2 \end{bmatrix}\begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} \\ &= \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & -1 \\ 0 & 0 & 1 \end{bmatrix}, \\ \rowpart{x^+} &= A^+\target{b} = \rowpart{\begin{bmatrix} 3 \\ 1 \end{bmatrix}}, \\ \reached{\hat{b}} &= A\rowpart{x^+} = \reached{\begin{bmatrix} 4 \\ 4 \\ 1 \end{bmatrix}} \end{aligned}
3

The wide system [122011][x1x2x3]=[52]\begin{bmatrix} 1 & 2 & 2 \\ 0 & 1 & 1 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \target{\begin{bmatrix} 5 \\ 2 \end{bmatrix}} has independent rows and infinitely many solutions. Compute A+=AT(AAT)−1A^+ = A^T(AA^T)^{-1} and find the shortest input vector x+\rowpart{x^+} that solves the system.

Check the dimensions and determinant of AATAA^T before inverting, and keep ATA^T on the left when you multiply AT(AAT)−1A^T(AA^T)^{-1}.

Multiply AATAA^T and invert the resulting 2×22 \times 2 matrix (do not forget to divide by det⁡(AAT)=18−16=2\det(AA^T) = 18 - 16 = 2, or every entry will be doubled and give x+=[222]x^+ = \begin{bmatrix} 2 \\ 2 \\ 2 \end{bmatrix}, which maps to [104]\begin{bmatrix} 10 \\ 4 \end{bmatrix} instead of [52]\target{\begin{bmatrix} 5 \\ 2 \end{bmatrix}}):
AAT=[122011][102121]=[9442]⟹(AAT)−1=12[2−4−49]\displaystyle \begin{aligned} AA^T &= \begin{bmatrix} 1 & 2 & 2 \\ 0 & 1 & 1 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ 2 & 1 \\ 2 & 1 \end{bmatrix} \\ &= \begin{bmatrix} 9 & 4 \\ 4 & 2 \end{bmatrix} \\ \Longrightarrow \quad (AA^T)^{-1} &= \frac{1}{2}\begin{bmatrix} 2 & -4 \\ -4 & 9 \end{bmatrix} \end{aligned}
Multiply AT(AAT)−1A^T(AA^T)^{-1} and multiply A+A^+ by b=[52]\target{b} = \target{\begin{bmatrix} 5 \\ 2 \end{bmatrix}}:
A+=[102121]12[2−4−49]=[1−2012012],x+=A+b=[1−2012012][52]=[111]\displaystyle \begin{aligned} A^+ &= \begin{bmatrix} 1 & 0 \\ 2 & 1 \\ 2 & 1 \end{bmatrix}\frac{1}{2}\begin{bmatrix} 2 & -4 \\ -4 & 9 \end{bmatrix} \\ &= \begin{bmatrix} 1 & -2 \\ 0 & \frac{1}{2} \\ 0 & \frac{1}{2} \end{bmatrix}, \\ \rowpart{x^+} &= A^+\target{b} = \begin{bmatrix} 1 & -2 \\ 0 & \frac{1}{2} \\ 0 & \frac{1}{2} \end{bmatrix}\target{\begin{bmatrix} 5 \\ 2 \end{bmatrix}} = \rowpart{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} \end{aligned}
4

For A=[1−22−4]A = \begin{bmatrix} 1 & -2 \\ 2 & -4 \end{bmatrix} and b=[155]\target{b} = \target{\begin{bmatrix} 15 \\ 5 \end{bmatrix}}, neither ATAA^TA nor AATAA^T is invertible. Find the SVD A=UΣVTA = U\Sigma V^T, use it to compute A+=VΣ+UTA^+ = V\Sigma^+U^T, and find the best-effort solution x+=A+b\rowpart{x^+} = A^+\target{b}.

Both columns are multiples of [12]\reached{\begin{bmatrix} 1 \\ 2 \end{bmatrix}} and both rows are multiples of [1−2]\rowpart{\begin{bmatrix} 1 \\ -2 \end{bmatrix}}. Divide those vectors by their length to get the unit vectors u1\reached{u_1} and v1\rowpart{v_1}, then multiply Av1A\rowpart{v_1} to find the stretch σ1\stretch{\sigma_1}.

Divide the column-space direction [12]\reached{\begin{bmatrix} 1 \\ 2 \end{bmatrix}} and row-space direction [1−2]\rowpart{\begin{bmatrix} 1 \\ -2 \end{bmatrix}} by their length 5\sqrt{5} (forgetting the 15\frac{1}{\sqrt{5}} length factors leaves out a factor of 15\frac{1}{5} in A+A^+ and gives [5−10]\begin{bmatrix} 5 \\ -10 \end{bmatrix}), and use Av1=5u1A\rowpart{v_1} = \stretch{5}\reached{u_1} to get σ1=5\stretch{\sigma_1} = \stretch{5}:
U=15[1−221],Σ=[5000],V=15[12−21]\displaystyle \begin{aligned} U &= \frac{1}{\sqrt{5}}\begin{bmatrix} \reached{1} & \lost{-2} \\ \reached{2} & \lost{1} \end{bmatrix}, \\ \Sigma &= \begin{bmatrix} \stretch{5} & 0 \\ 0 & \lost{0} \end{bmatrix}, \\ V &= \frac{1}{\sqrt{5}}\begin{bmatrix} \rowpart{1} & \lost{2} \\ \rowpart{-2} & \lost{1} \end{bmatrix} \end{aligned}
Invert the nonzero stretch 5→15\stretch{5} \to \stretch{\frac{1}{5}} in Σ+\Sigma^+ and multiply VΣ+UTV\Sigma^+U^T in reverse order (multiplying in forward order UΣ+VTU\Sigma^+V^T flips the signs of the off-diagonal entries and gives [1525]\begin{bmatrix} \tfrac{1}{5} \\ \tfrac{2}{5} \end{bmatrix} in the column space instead of the row space):
Σ+=[15000],A+=VΣ+UT=125[12−2−4],x+=A+b=125[12−2−4][155]=[1−2]\displaystyle \begin{aligned} \Sigma^+ &= \begin{bmatrix} \stretch{\frac{1}{5}} & 0 \\ 0 & \lost{0} \end{bmatrix}, \\ A^+ &= V\Sigma^+U^T \\ &= \frac{1}{25}\begin{bmatrix} 1 & 2 \\ -2 & -4 \end{bmatrix}, \\ \rowpart{x^+} &= A^+\target{b} \\ &= \frac{1}{25}\begin{bmatrix} 1 & 2 \\ -2 & -4 \end{bmatrix}\target{\begin{bmatrix} 15 \\ 5 \end{bmatrix}} = \rowpart{\begin{bmatrix} 1 \\ -2 \end{bmatrix}} \end{aligned}
5

For A=[3400]A = \begin{bmatrix} 3 & 4 \\ 0 & 0 \end{bmatrix}, find A+A^+, compute the column-space projection matrix AA+AA^+ and the row-space projection matrix A+AA^+A, and use A+AA^+A to split the input x=[50]x = \begin{bmatrix} 5 \\ 0 \end{bmatrix} into its row-space part xrow\rowpart{x_{\text{row}}} and null-space part xnull\lost{x_{\text{null}}}.

Row 1 points along the row space with length 32+42=5\sqrt{3^2 + 4^2} = 5 while row 2 is zero; once you have A+A^+, check which order (AA+AA^+ vs A+AA^+A) lands in the input's row space.

With u1=[10]\reached{u_1} = \reached{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}, v1=15[34]\rowpart{v_1} = \rowpart{\frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix}}, and σ1=5\stretch{\sigma_1} = \stretch{5}, build A+A^+ and compute both projection matrices:
A+=125[3040],AA+=[1000],A+A=125[9121216]\displaystyle \begin{aligned} A^+ &= \frac{1}{25}\begin{bmatrix} 3 & 0 \\ 4 & 0 \end{bmatrix}, \\ AA^+ &= \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}, \\ A^+A &= \frac{1}{25}\begin{bmatrix} 9 & 12 \\ 12 & 16 \end{bmatrix} \end{aligned}
Multiply xx by the row-space projection A+AA^+A to find xrow\rowpart{x_{\text{row}}}, then subtract from xx to find xnull\lost{x_{\text{null}}} (do not multiply xx by AA+=[1000]AA^+ = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}, which projects onto the output column space and wrongly gives xrow=[50]x_{\text{row}} = \begin{bmatrix} 5 \\ 0 \end{bmatrix} and xnull=[00]x_{\text{null}} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}):
xrow=(A+A)x=125[9121216][50]=[95125],xnull=x−xrow=[50]−[95125]=[165−125]\displaystyle \begin{aligned} \rowpart{x_{\text{row}}} &= (A^+A)x \\ &= \frac{1}{25}\begin{bmatrix} 9 & 12 \\ 12 & 16 \end{bmatrix}\begin{bmatrix} 5 \\ 0 \end{bmatrix} = \rowpart{\begin{bmatrix} \frac{9}{5} \\ \frac{12}{5} \end{bmatrix}}, \\ \lost{x_{\text{null}}} &= x - \rowpart{x_{\text{row}}} \\ &= \begin{bmatrix} 5 \\ 0 \end{bmatrix} - \rowpart{\begin{bmatrix} \frac{9}{5} \\ \frac{12}{5} \end{bmatrix}} = \lost{\begin{bmatrix} \frac{16}{5} \\ -\frac{12}{5} \end{bmatrix}} \end{aligned}