GATE DA

LU decomposition and SVD

Projections, LU decomposition and singular value decomposition

Projections, LU decomposition and the SVD each break a matrix problem into easy pieces. A projection gives the closest point in a subspace, which is where least squares comes from. LU turns Ax = b into two triangular solves. The SVD shows rank, 2-norm and the best low-rank approximation. Typical calculations here are a projection or least-squares solution, a pivot or determinant from an LU factorisation, or a rank, norm or approximation error from singular values. Each is short once the formulas are known.

1 previous-year question · 1 solved · 5 practice questions

Convention and orthogonal projection

Convention. All matrices and vectors are real. Vectors are column vectors, written in bold; $A^{T}$ is the transpose, $∥ x ∥ = x^{T} x$ is the Euclidean norm, and $u \cdot v = u^{T} v$ . Eigenvalues are written $λ$ and singular values $σ$ .

The orthogonal projection of $b$ onto a subspace $W$ is the unique vector $p \in W$ such that the error $b - p$ is orthogonal to every vector in $W$ . It is also the point of $W$ closest to $b$ in the Euclidean norm, so the distance from $b$ to $W$ is $∥ b - p ∥$ .

PROJECTION ONTO A LINE

p = \frac{a ^{T} b}{a ^{T} a} a, P = \frac{a a ^{T}}{a ^{T} a}

Line through the origin along $a \neq = 0$ ; $b$ and $a$ are in $R^{n}$ , $P$ is $n \times n$ of rank $1$ , and $p = P b$ .

PROJECTION ONTO A COLUMN SPACE

P = A (A^{T} A)^{- 1} A^{T}, p = P b

$A$ is $m \times n$ with linearly independent columns (so $A^{T} A$ is invertible); $P$ is $m \times m$ and projects onto the column space of $A$ .

PROJECTION WITH AN ORTHONORMAL BASIS

P = Q Q^{T} = i = 1 \sum k q_{i} q_{i}^{T}

The columns $q_{1}, \dots, q_{k}$ of the $m \times k$ matrix $Q$ are orthonormal ( $Q^{T} Q = I_{k}$ ); $P$ is $m \times m$ and no inverse is needed.

Property of an orthogonal projection matrix $P$ ( $n \times n$ ) onto $W$	Statement
Idempotent	$P^{2} = P$ (projecting twice changes nothing)
Symmetric	$P^{T} = P$
Eigenvalues	each eigenvalue is $1$ (eigenvectors: non-zero vectors in $W$ ) or $0$ (eigenvectors: non-zero vectors orthogonal to $W$ )
Rank and trace	$rank P = trace P = dim W$
Complement	$I - P$ is the orthogonal projection onto the orthogonal complement of $W$
Reflection	$I - 2 P$ is symmetric and orthogonal, $(I - 2 P)^{2} = I$ , eigenvalues $\pm 1$ ; with $P = u u^{T}$ , $∥ u ∥ = 1$ , it reflects across the hyperplane orthogonal to $u$

EXAM TIP

Check any projection by testing that the error $b - p$ is orthogonal to $a$ , that is $a^{T} (b - p) = 0$ , or to every column of $A$ , that is $A^{T} (b - p) = 0$ . A non-zero result means an arithmetic slip.

Least squares and Gram-Schmidt

When $A x = b$ has no solution ( $b$ is not in the column space of the $m \times n$ matrix $A$ ), a least-squares solution $\hat{x}$ minimises $∥ A x - b ∥^{2}$ . Then $A \hat{x}$ is exactly the projection of $b$ onto the column space, which gives the normal equations.

NORMAL EQUATIONS

A^{T} A \hat{x} = A^{T} b ⟹ \hat{x} = (A^{T} A)^{- 1} A^{T} b

The normal equations always have a solution; it is unique (and given by the inverse form) only when the columns of $A$ are linearly independent.

RESIDUAL IS ORTHOGONAL TO THE COLUMNS

A^{T} (b - A \hat{x}) = 0, ∥ b ∥^{2} = ∥ A \hat{x} ∥^{2} + ∥ b - A \hat{x} ∥^{2}

Pythagoras applies because the projection and the residual are perpendicular.

WORKED EXAMPLE

Find the least-squares line $y = c + d t$ through the points $(0, 1), (1, 2), (2, 2)$ , and the minimum sum of squared errors.

Solution

Write $A = 111012$ ( $3 \times 2$ ), $b = 122$ , unknown $x = [c d]$ .
$A^{T} A = [3335]$ and $A^{T} b = [56]$ .
Solve $3 c + 3 d = 5$ , $3 c + 5 d = 6$ . Subtracting gives $2 d = 1$ , so $d = \frac{1}{2}$ . From the first equation $c = \frac{5}{3} - d = \frac{5}{3} - \frac{1}{2} = \frac{7}{6}$ .
Fitted values $A \hat{x} = (\frac{7}{6}, \frac{5}{3}, \frac{13}{6})^{T}$ , residual $b - A \hat{x} = (- \frac{1}{6}, \frac{1}{3}, - \frac{1}{6})^{T}$ .
The residual is orthogonal to both columns ( $- \frac{1}{6} + \frac{1}{3} - \frac{1}{6} = 0$ and $0 + \frac{1}{3} - \frac{1}{3} = 0$ ). Squared error $= \frac{1}{36} + \frac{4}{36} + \frac{1}{36} = \frac{1}{6}$ .

Answer: $y = \frac{7}{6} + \frac{1}{2} t$ , minimum squared error $= \frac{1}{6}$ .

Gram-Schmidt turns linearly independent vectors $a_{1}, \dots, a_{k}$ into orthogonal ones by subtracting, from each new vector, its projections onto the earlier ones. Dividing by lengths gives an orthonormal set.

GRAM-SCHMIDT STEP

v_{1} = a_{1}, v_{j} = a_{j} - i < j \sum \frac{v _{i}^{T} a _{j}}{v _{i}^{T} v _{i}} v_{i}, q_{j} = \frac{v _{j}}{∥ v _{j} ∥}

For an $m \times k$ matrix $A$ with linearly independent columns this gives $A = QR$ : $Q$ is $m \times k$ with orthonormal columns and $R = Q^{T} A$ is $k \times k$ upper triangular with entries $r_{ij} = q_{i}^{T} a_{j}$ ( $i \leq j$ ) and positive diagonal. The span of the first $j$ vectors is preserved at every step.

EXAM TIP

Use the projection onto the already orthogonalised $v_{i}$ , not onto the original $a_{i}$ ; mixing them is a frequent slip. If some $v_{j} = 0$ , the vectors were linearly dependent.

LU decomposition

For a square $n \times n$ matrix $A$ , LU decomposition records Gaussian elimination as a product $A = LU$ . $U$ is the upper triangular matrix reached at the end of forward elimination. $L$ is unit lower triangular (ones on the diagonal), and its entry $ℓ_{ij}$ ( $i > j$ ) is the multiplier used to clear position $(i, j)$ : $ℓ_{ij} = \frac{entry being eliminated}{pivot}$ , with row $i \leftarrow$ row $i - ℓ_{ij} \cdot$ row $j$ .

LU FACTORISATION

A = LU, L = 1 ℓ_{21} ℓ_{31} 01 ℓ_{32} 001, U = u_{11} 00 u_{12} u_{22} 0 u_{13} u_{23} u_{33}

Shown for $3 \times 3$ . Elimination without row exchanges succeeds exactly when the first $n - 1$ pivots are non-zero, equivalently when the leading principal minors $Δ_{1}, \dots, Δ_{n - 1}$ are non-zero; the factorisation with unit lower $L$ is then unique. ( $u_{nn}$ may be $0$ , which happens exactly when $A$ is singular.)

PIVOTS FROM LEADING PRINCIPAL MINORS

u_{k k} = \frac{Δ _{k}}{Δ _{k - 1}}, Δ_{0} = 1

$Δ_{k}$ is the determinant of the top-left $k \times k$ block of $A$ ; valid when no row exchanges are needed ( $Δ_{1}, \dots, Δ_{n - 1} \neq = 0$ ).

PIVOTED FORM

P A = LU

When a zero pivot appears, rows are exchanged; $P$ is an $n \times n$ permutation matrix. A factorisation $P A = LU$ exists for every square $A$ , and $det A = (- 1)^{s} \prod_{i} u_{ii}$ , where $s$ is the number of row exchanges.

DETERMINANT FROM LU

det A = det L \cdot det U = i = 1 \prod n u_{ii}

Valid when no row exchanges were used; $det L = 1$ because $L$ is unit triangular.

SYMMETRIC MATRICES: LDLᵀ AND CHOLESKY

A = L D L^{T}, D = diag (u_{11}, \dots, u_{nn}); A = G G^{T}, G = L D^{1/2}

$A$ is symmetric $n \times n$ with $Δ_{1}, \dots, Δ_{n} \neq = 0$ ; then $U = D L^{T}$ . $A$ is positive definite exactly when every pivot $u_{k k} > 0$ (equivalently every $Δ_{k} > 0$ ), and then the Cholesky factor $G$ is lower triangular with positive diagonal.

Factorise once: $A = LU$ by elimination, saving each multiplier in $L$ .
Forward substitution: solve $L y = b$ from the top row down.
Back substitution: solve $U x = y$ from the bottom row up.
Then $A x = LU x = L y = b$ . The same $L, U$ serve every new right-hand side.

WORKED EXAMPLE

Factorise $A = 248137139$ as $LU$ , find $det A$ , and solve $A x = 126$ .

Solution

Pivot $2$ . Multipliers $ℓ_{21} = 4/2 = 2$ , $ℓ_{31} = 8/2 = 4$ . Row 2 becomes $[0, 1, 1]$ and row 3 becomes $[0, 3, 5]$ .
Pivot $1$ . Multiplier $ℓ_{32} = 3/1 = 3$ . Row 3 becomes $[0, 0, 2]$ .
So $U = 200110112$ , $L = 124013001$ , and $det A = 2 \cdot 1 \cdot 2 = 4$ . (Check: $Δ_{1} = 2$ , $Δ_{2} = 2$ , $Δ_{3} = 4$ give pivots $2, 1, 2$ .)
Forward: $y_{1} = 1$ ; $y_{2} = 2 - 2 (1) = 0$ ; $y_{3} = 6 - 4 (1) - 3 (0) = 2$ .
Back: $x_{3} = 2/2 = 1$ ; $x_{2} = 0 - 1 = - 1$ ; $x_{1} = (1 - (- 1) - 1) /2 = \frac{1}{2}$ . Check row 3: $8 (\frac{1}{2}) - 7 + 9 = 6$ .

Answer: $det A = 4$ and $x = (\frac{1}{2}, - 1, 1)^{T}$ .

EXAM TIP

Multipliers go into $L$ with their sign as computed (row $i$ minus $ℓ_{ij}$ times row $j$ ). Putting $- ℓ_{ij}$ in $L$ is a frequent error; a quick check is to multiply $L$ by $U$ and recover $A$ .

Singular value decomposition

Every real $m \times n$ matrix $A$ (square or not, invertible or not) has an SVD. Acting on $x$ , $A = U Σ V^{T}$ applies $V^{T}$ (a rotation or reflection), then $Σ$ (a stretch along the coordinate axes, possibly changing the dimension), then $U$ (another rotation or reflection).

SINGULAR VALUE DECOMPOSITION

A = U Σ V^{T}, Σ = diag (σ_{1}, \dots, σ_{r}, 0, \dots, 0), σ_{1} \geq σ_{2} \geq \dots \geq σ_{r} > 0

$U$ is $m \times m$ orthogonal (left singular vectors $u_{i}$ ), $V$ is $n \times n$ orthogonal (right singular vectors $v_{i}$ ), $Σ$ is $m \times n$ with the $min (m, n)$ singular values on its diagonal and zeros elsewhere; $r = rank A$ . Equivalently $A = \sum_{i = 1}^{r} σ_{i} u_{i} v_{i}^{T}$ .

SINGULAR VALUES FROM EIGENVALUES

σ_{i} = λ_{i} (A^{T} A) = λ_{i} (A A^{T}) (i = 1, \dots, r), A^{T} A v_{i} = σ_{i}^{2} v_{i}

$A^{T} A$ ( $n \times n$ ) and $A A^{T}$ ( $m \times m$ ) are symmetric positive semidefinite and have the same non-zero eigenvalues; all their other eigenvalues are $0$ . The columns of $V$ are orthonormal eigenvectors of $A^{T} A$ and the columns of $U$ are orthonormal eigenvectors of $A A^{T}$ .

LEFT VECTORS FROM RIGHT VECTORS

u_{i} = \frac{1}{σ _{i}} A v_{i} (σ_{i} > 0)

Fixes $u_{i}$ so that its sign agrees with $v_{i}$ ; choosing $u_{i}$ independently from $A A^{T}$ can give a wrong sign.

RANK-ONE MATRIX

A = u v^{T} ⟹ σ_{1} = ∥ u ∥ ∥ v ∥, σ_{2} = \dots = 0

$u \in R^{m}$ and $v \in R^{n}$ are non-zero, so $A$ is $m \times n$ of rank $1$ ; this follows from $A^{T} A = ∥ u ∥^{2} v v^{T}$ .

Form $A^{T} A$ (an $n \times n$ symmetric matrix) and find its eigenvalues $λ_{i} \geq 0$ . If $n > m$ it is quicker to use the $m \times m$ matrix $A A^{T}$ , which has the same non-zero eigenvalues.
Set $σ_{i} = λ_{i}$ in decreasing order; the number of non-zero ones is $rank A$ .
Find orthonormal eigenvectors $v_{i}$ of $A^{T} A$ to form $V$ .
Compute $u_{i} = A v_{i} / σ_{i}$ for each non-zero $σ_{i}$ ; complete $U$ to an orthonormal basis of $R^{m}$ if $m > r$ .

WORKED EXAMPLE

For $A = [3405]$ find the singular values, $∥ A ∥_{2}$ , and check them against $det A$ .

Solution

$A^{T} A = [25202025]$ , with eigenvalues $25 \pm 20$ , that is $45$ and $5$ .
Singular values: $σ_{1} = 45 = 35 \approx 6.708$ and $σ_{2} = 5 \approx 2.236$ .
The 2-norm is the largest singular value, $35$ .
Checks: $σ_{1} σ_{2} = 15 = ∣ det A ∣$ and $σ_{1}^{2} + σ_{2}^{2} = 50 = 3^{2} + 0^{2} + 4^{2} + 5^{2}$ .

Answer: $σ = 35, 5$ ; $∥ A ∥_{2} = 35$ .

Matrix	Singular values
$Q$ orthogonal ( $Q^{T} Q = I$ )	all equal to $1$
$A$ symmetric	$∣ λ_{i} ∣$ , the absolute values of its eigenvalues
$A$ symmetric positive semidefinite	$λ_{i}$ (the SVD is the eigendecomposition)
$A^{T}$	the same non-zero singular values as $A$

EXAM TIP

Singular values are square roots of eigenvalues of $A^{T} A$ , not eigenvalues of $A$ . For a square $A$ they equal the $∣ λ_{i} ∣$ exactly when $A$ is normal ( $A^{T} A = A A^{T}$ ), symmetric matrices being the usual case. For a general square $A$ the product of the $σ_{i}$ equals $∣ det A ∣$ , but their sum need not equal $∣ trace A ∣$ .

Rank, norms and low-rank approximation

RANK AND NORMS FROM SINGULAR VALUES

rank A = # {σ_{i} > 0}, ∥ A ∥_{2} = σ_{1}, ∥ A ∥_{F}^{2} = i \sum σ_{i}^{2} = trace (A^{T} A)

$∥ A ∥_{2} = max_{∥ x ∥ = 1} ∥ A x ∥$ is the spectral norm; $∥ A ∥_{F}$ is the Frobenius norm (square root of the sum of squared entries).

SQUARE MATRICES

∣ det A ∣ = i = 1 \prod n σ_{i}, κ_{2} (A) = \frac{σ _{1}}{σ _{n}} (A invertible)

$A$ is $n \times n$ ; $A$ is invertible exactly when $σ_{n} > 0$ , and $κ_{2}$ is the 2-norm condition number.

RANK-$K$ TRUNCATION

A_{k} = i = 1 \sum k σ_{i} u_{i} v_{i}^{T}

Keeps the $k$ largest singular values, $k \leq r$ ; $A_{k}$ has rank $k$ .

BEST LOW-RANK APPROXIMATION (ECKART-YOUNG)

rank B \leq k min ∥ A - B ∥_{2} = σ_{k + 1}, rank B \leq k min ∥ A - B ∥_{F} = i > k \sum σ_{i}^{2}

$B$ ranges over $m \times n$ matrices; the minimum is attained by $B = A_{k}$ in both norms; take $σ_{k + 1} = 0$ if $k \geq r$ .

LEAST SQUARES THROUGH THE SVD

\hat{x} = A^{+} b = σ_{i} > 0 \sum \frac{u _{i}^{T} b}{σ _{i}} v_{i}

$A^{+} = V Σ^{+} U^{T}$ ( $n \times m$ ) is the pseudo-inverse, where $Σ^{+}$ ( $n \times m$ ) has $1/ σ_{i}$ in place of each non-zero $σ_{i}$ ; this gives the least-squares solution of smallest norm, and it equals $(A^{T} A)^{- 1} A^{T} b$ when the columns of $A$ are independent.

Decomposition	Form	Exists for	Main use
LU	$A = LU$ (or $P A = LU$ )	square $A$ with $Δ_{1}, \dots, Δ_{n - 1} \neq = 0$ ; with row exchanges, every square $A$	solving $A x = b$ , determinant
QR (Gram-Schmidt)	$A = QR$	$m \times n$ with independent columns	projections, least squares
SVD	$A = U Σ V^{T}$	every real matrix	rank, 2-norm, low-rank approximation

EXAM TIP

In the Eckart-Young error, the 2-norm error is a single singular value $σ_{k + 1}$ , while the Frobenius error is the square root of the sum of squares of all the discarded ones. Read the question to see which norm is asked.

PREVIOUS-YEAR QUESTIONS

1 question from the DA papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE DA 2024

GATE 2024 DA Q.61

GATE 2024 · DAQ.61 · 2 marks · NAT

Let $u = 12345$ , and let $σ_{1}, σ_{2}, σ_{3}, σ_{4}, σ_{5}$ be the singular values of the matrix $M = u u^{T}$ (where $u^{T}$ is the transpose of $u$ ). The value of $\sum_{i = 1}^{5} σ_{i}$ is ______.

Answer and solution

GATE 2024 DA Q.61: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 DA Q.61: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 11 mark · NAT

In $R^{3}$ (column vectors, Euclidean norm), let $a = (1, 2, 2)^{T}$ and $b = (2, 1, 4)^{T}$ . What is the length of the orthogonal projection of $b$ onto the line spanned by $a$ ?

Answer and solution

Answer: $4$ (accepted range $\pm 0.01$ )

$a^{T} b = 2 + 2 + 8 = 12$ and $a^{T} a = 1 + 4 + 4 = 9$ .
Projection $p = \frac{12}{9} a = \frac{4}{3} (1, 2, 2)^{T}$ .
Length $= \frac{4}{3} ∥ a ∥ = \frac{4}{3} \cdot 3 = 4$ (equivalently $∣ a^{T} b ∣/ ∥ a ∥ = 12/3$ ).

PRACTICE 22 marks · NAT

Let $A = 214 45 - 1 229$ . Gaussian elimination without row exchanges gives $A = LU$ with $L$ unit lower triangular and $U$ upper triangular ( $3 \times 3$ ). What is the product of the pivots $u_{11} u_{22} u_{33}$ ?

Answer and solution

Answer: $48$ (accepted range $\pm 0.01$ )

Pivot $u_{11} = 2$ . Multipliers $ℓ_{21} = 1/2$ , $ℓ_{31} = 4/2 = 2$ .
Row 2 $\to [0, 5 - 2, 2 - 1] = [0, 3, 1]$ . Row 3 $\to [0, - 1 - 8, 9 - 4] = [0, - 9, 5]$ .
Pivot $u_{22} = 3$ , multiplier $ℓ_{32} = - 9/3 = - 3$ . Row 3 $\to [0, 0, 5 + 3] = [0, 0, 8]$ , so $u_{33} = 8$ .
Product $= 2 \cdot 3 \cdot 8 = 48 = det A$ . Cross-check by cofactors along row 1: $2 (45 + 2) - 4 (9 - 8) + 2 (- 1 - 20) = 94 - 4 - 42 = 48$ .

PRACTICE 31 mark · MSQ

A real $3 \times 3$ matrix $A$ has singular values $4$ , $2$ and $0$ . Which of the following statements are true?

(A)
$rank A = 2$
(B)
$∥ A ∥_{2} = 4$
(C)
The eigenvalues of $A^{T} A$ are $4$ , $2$ and $0$
(D)
$A$ is singular

Answer and solution

Answer: (A), (B), (D)

Rank equals the number of non-zero singular values, which is 2, so (A) is true.
The 2-norm is the largest singular value, $4$ , so (B) is true.
The eigenvalues of $A^{T} A$ are the squares of the singular values: $16$ , $4$ , $0$ . So (C) is false.
$∣ det A ∣ = 4 \cdot 2 \cdot 0 = 0$ , so $A$ is singular and (D) is true.

PRACTICE 42 marks · NAT

A real $4 \times 3$ matrix $A$ has singular values $6$ , $3$ and $2$ . Over all real $4 \times 3$ matrices $B$ of rank at most $1$ , what is the minimum possible value of $∥ A - B ∥_{F}$ (Frobenius norm)? Give your answer correct to two decimal places.

Answer and solution

Answer: $3.61$ (accepted range $\pm 0.01$ )

By the Eckart-Young result, the best rank-1 approximation keeps $σ_{1}$ and discards the rest.
Minimum error $= σ_{2}^{2} + σ_{3}^{2} = 9 + 4 = 13$ .
$13 \approx 3.606$ , so the answer is $3.61$ .

PRACTICE 51 mark · MCQ

Let $A = [12]$ (a $2 \times 1$ matrix) and $b = [31]$ . What is the minimum value of $∥ A x - b ∥^{2}$ over real scalars $x$ ?

(A)
1
(B)
3
(C)
5
(D)
10

Answer and solution

Answer: (C)

Normal equation: $A^{T} A x = A^{T} b$ , i.e. $5 x = 3 + 2 = 5$ , so $\overset{x}{^} = 1$ .
$A \overset{x}{^} = (1, 2)^{T}$ and the residual is $b - A \overset{x}{^} = (2, - 1)^{T}$ .
Minimum $= 4 + 1 = 5$ . The residual is orthogonal to $A$ : $1 \cdot 2 + 2 \cdot (- 1) = 0$ . (Check: $∥ b ∥^{2} = 10 = ∥ A \overset{x}{^} ∥^{2} + 5$ .)

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE DA

projections, LU decomposition, singular value decomposition

Preparing in Kolkata? IAE Academy's course for GATE DA.