Advanced Linear Algebra quiz

Question 1

What is the Singular Value Decomposition (SVD) and what does it reveal about a matrix?

Accepted Answer

SVD works for any m×n matrix

Answer

SVD requires a square matrix

Answer

Singular values can be negative

Answer

U and V are the same matrix for square A

Question 2

What is eigendecomposition and when does a matrix have a complete eigendecomposition?

Accepted Answer

A symmetric matrix always has a complete eigendecomposition

Answer

Every square matrix is diagonalizable

Answer

Eigenvalues of symmetric matrices can be complex

Answer

Eigendecomposition requires the matrix to be invertible

Question 3

Describe the QR decomposition and its two main algorithms.

Accepted Answer

Householder reflections are more numerically stable than Gram-Schmidt

Answer

Gram-Schmidt is more numerically stable than Householder

Answer

QR decomposition requires a square matrix

Answer

QR decomposition is O(n²) for m×n matrices

Question 4

What is LU decomposition with partial pivoting and why is it more stable than without pivoting?

Accepted Answer

Partial pivoting permutes rows for numerical stability

Answer

Partial pivoting permutes columns

Answer

LU decomposition requires the matrix to be symmetric

Answer

Without pivoting, LU is always more stable

Question 5

What is the Cholesky decomposition and what are its computational advantages over LU for SPD matrices?

Accepted Answer

Cholesky runs in n³/3 FLOPs, half of LU

Answer

Cholesky requires twice the FLOPs of LU

Answer

Cholesky requires pivoting for stability

Answer

Cholesky works for any square matrix

Question 6

What is the pseudoinverse (Moore-Penrose) of a matrix and how is it computed via SVD?

Accepted Answer

A⁺ = V Σ⁺ U^T via SVD

Answer

A⁺ exists only for square matrices

Answer

A⁺ always equals (A^TA)^{-1}A^T regardless of rank

Answer

A⁺b minimizes ||x||² among all solutions only for full-rank A

Question 7

What is the trace of a matrix and list three of its key properties?

Accepted Answer

tr(AB) = tr(BA)

Answer

tr(AB) = tr(A)·tr(B)

Answer

tr(A) equals the sum of singular values

Answer

tr(A) requires A to be symmetric

Question 8

What is the determinant and how does it relate to eigenvalues and volume?

Accepted Answer

det(A) equals the product of eigenvalues

Answer

det(A) equals the sum of eigenvalues

Answer

det(AB) = det(A) + det(B)

Answer

det(A) > 0 always for invertible matrices

Question 9

Explain the concept of matrix rank and the rank-nullity theorem.

Accepted Answer

rank(A) + nullity(A) = n (number of columns)

Answer

rank(A) + nullity(A) = m (number of rows)

Answer

rank(A) always equals min(m,n)

Answer

Nullity of a full-rank square matrix equals 1

Question 10

What is matrix calculus notation and how do you compute the gradient of tr(AX) with respect to X?

Accepted Answer

∂tr(AX)/∂X = A^T

Answer

∂tr(AX)/∂X = A

Answer

∂tr(AX)/∂X = X

Answer

∂tr(AX)/∂X = X^T

Question 11

What is the nuclear norm of a matrix and how does it relate to SVD?

Accepted Answer

Nuclear norm = sum of all singular values

Answer

Nuclear norm = max singular value

Answer

Nuclear norm = Frobenius norm

Answer

Nuclear norm minimization promotes full-rank solutions

Question 12

What is the Sherman-Morrison-Woodbury formula and when is it used in ML?

Accepted Answer

Woodbury formula converts an n×n to a k×k matrix inversion

Answer

Woodbury formula requires A to be diagonal

Answer

Sherman-Morrison handles rank-k updates for any k

Answer

Woodbury formula increases computation for k << n

Question 13

What is the spectral radius of a matrix and how does it relate to power iteration?

Accepted Answer

Spectral radius = maximum absolute eigenvalue

Answer

Spectral radius = sum of absolute eigenvalues

Answer

Spectral radius = Frobenius norm

Answer

Power iteration fails when the largest eigenvalue is unique

Question 14

What is the Schur decomposition and how does it relate to eigendecomposition?

Accepted Answer

Schur decomposition always exists for any square matrix

Answer

Schur decomposition only works for symmetric matrices

Answer

Schur form is always diagonal

Answer

Schur decomposition is less stable than eigendecomposition

Question 15

What are the four fundamental subspaces of a matrix?

Accepted Answer

The null space has dimension n - rank (by rank-nullity)

Answer

The null space has dimension equal to the rank

Answer

Column space and null space are in the same R^n

Answer

The four subspaces are all orthogonal to each other

Question 16

What is an orthogonal projection matrix and what are its two key properties?

Accepted Answer

Projection matrix P satisfies P²=P (idempotent) and P^T=P (symmetric)

Answer

Projection matrix P satisfies P³=P but not P²=P

Answer

Projection matrix eigenvalues are -1 and 1

Answer

Projection matrix requires a square input matrix

Question 17

What is the Perron-Frobenius theorem and what does it guarantee for non-negative matrices?

Accepted Answer

Perron-Frobenius guarantees a unique largest real eigenvalue for positive matrices

Answer

Perron-Frobenius applies to any real matrix

Answer

The Perron eigenvector can have negative entries

Answer

The theorem requires the matrix to be symmetric

Question 18

What is the vec operator and how does it vectorize matrix equations?

Accepted Answer

vec(AXB) = (B^T⊗A)vec(X)

Answer

vec(AXB) = (A⊗B^T)vec(X)

Answer

vec(AXB) = (A^T⊗B)vec(X)

Answer

vec(AXB) = vec(A)⊗vec(B)⊗vec(X)

Question 19

What is the Cayley-Hamilton theorem and one of its practical applications?

Accepted Answer

Cayley-Hamilton: A satisfies its own characteristic polynomial p(A)=0

Answer

Cayley-Hamilton: A satisfies A^n = 0 for any A

Answer

Cayley-Hamilton only applies to symmetric matrices

Answer

Cayley-Hamilton requires the matrix to have distinct eigenvalues

Question 20

What is randomized SVD and why is it preferred for large sparse matrices?

Accepted Answer

Randomized SVD is O(mn log k + (m+n)k²) for rank-k approximation

Answer

Randomized SVD is O(mn·min(m,n)) like full SVD

Answer

Randomized SVD gives exact singular values

Answer

Randomized SVD requires two passes over the matrix always

Question 21

What is the QR algorithm for computing eigenvalues and why is it the standard method?

Accepted Answer

QR algorithm with shifts achieves cubic convergence

Answer

QR algorithm convergence is linear

Answer

QR algorithm requires O(n⁴) operations

Answer

QR algorithm cannot handle non-symmetric matrices

Question 22

What is the difference between direct and iterative methods for solving linear systems?

Accepted Answer

Iterative methods are preferred for large sparse systems

Answer

Direct methods are always faster than iterative methods

Answer

Direct methods require O(n²) operations for dense systems

Answer

GMRES only works for symmetric matrices

Question 23

What is a Toeplitz matrix and what fast algorithms exploit its structure?

Accepted Answer

Toeplitz matrix-vector product is O(n log n) with FFT via circulant embedding

Answer

Toeplitz matrix-vector product is O(n²) with FFT

Answer

Toeplitz matrices are always symmetric

Answer

Toeplitz matrices require O(n²) storage

Question 24

What is the Gershgorin circle theorem and how does it bound eigenvalues?

Accepted Answer

Gershgorin disks are centered at diagonal entries with radius = sum of off-diagonal magnitudes

Answer

Gershgorin disks are centered at off-diagonal entries

Answer

Gershgorin theorem requires a symmetric matrix

Answer

Each eigenvalue must lie in all Gershgorin disks simultaneously

Question 25

Describe the relationship between the SVD and the polar decomposition.

Accepted Answer

In A=UP, U is orthogonal and P is symmetric positive definite

Answer

In A=UP, P is orthogonal and U is symmetric

Answer

Polar decomposition is not unique for invertible matrices

Answer

The polar decomposition requires A to be square and symmetric

Question 26

What is the Nystrom approximation and how does it scale kernel methods?

Accepted Answer

Nystrom approximation reduces storage to O(mn) with m << n

Answer

Nystrom approximation requires O(n²) storage

Answer

Nystrom approximation gives exact kernel matrix

Answer

Nystrom requires all n points as landmarks

Question 27

What is the Hadamard inequality and when is it tight?

Accepted Answer

Hadamard inequality: |det(A)| ≤ product of column norms, with equality for orthogonal columns

Answer

Hadamard inequality: |det(A)| ≥ product of column norms

Answer

Hadamard inequality requires A to be square and symmetric

Answer

Hadamard inequality is only for {0,1} matrices

Question 28

What is the connection between eigenvalues and the long-run behavior of Markov chains?

Accepted Answer

Markov chain stationary distribution is the eigenvector for eigenvalue 1

Answer

Markov chain stationary distribution is the eigenvector for eigenvalue 0

Answer

Larger spectral gap means slower mixing

Answer

All Markov chain eigenvalues are positive

Question 29

What is the Kronecker factored curvature (K-FAC) and how does it approximate the Fisher Information Matrix?

Accepted Answer

K-FAC uses Kronecker structure to reduce inversion to O(n_l³ + n_{l-1}³)

Answer

K-FAC requires O(d³) per layer to invert

Answer

K-FAC approximates the Hessian, not the Fisher

Answer

K-FAC requires the loss to be convex

Question 30

What is the difference between covariance and correlation matrices and how are they used in ML?

Accepted Answer

Correlation matrix normalizes covariance to unit variance, scale-invariant

Answer

Correlation matrix is the same as covariance matrix

Answer

Covariance matrix is not always symmetric

Answer

Whitening uses the correlation matrix

Test yourself