Matrix Properties via SVD

Nullspace
Range, rank
Fundamental theorem of linear algebra
Matrix norms and condition number

Nullspace

Finding a basis for the nullspace

The SVD allows to compute an orthonormal basis for the nullspace of a matrix. To understand this, let us first consider a matrix of the form

The nullspace of this matrix is readily found by solving the equation tilde{ {S}}x = 0

. We obtain that x = (x_1,x_2,x_3)

is in the nullspace if and only if the first two components of

are zero:

What about a general matrix

, which admits the SVD as given in the SVD theorem? Since

is orthogonal, we can pre-multiply the nullspace equation Ax = 0

, and solve in terms of the ‘‘rotated’’ variable $tilde{x} : = V^Tx$ . We obtain the condition on

The above is equivalent to the first

components of tilde{x}

being zero. Since x = Vtilde{x}

, this corresponds to the fact that

belongs to the span of the last n-r

columns of

. Note that these columns form a set of mutually orthogonal, normalized vectors that span the nullspace: hence they form an orthonormal basis for it.

Theorem: nullspace via SVD

The nullspace of a matrix with SVD

$A = U tilde{S} V^T, ;; tilde{S} := left( begin{array}{cc}S & 0 0 & 0 end{array} right) , ;; S = mbox{bf diag}(sigma_1 , ldots, sigma_r),$

where $U in mathbf{R}^{m times m}$ , $V in mathbf{R}^{n times n}$ are both orthogonal matrices, admits the last n-r columns of as an orthonormal basis.

Full column-rank matrices

One-to-one (or, full column rank) matrices are the matrices with nullspace reduced to {0}

. If the dimension of the nullspace is zero, then we must have n=r

. Thus, full column rank matrices are ones with SVD of the form

Range, rank via the SVD

Basis of the range

As with the nullspace, we can express the range in terms of the SVD of the matrix

. Indeed the range of

is the set of vectors of the form

where $x in mathbf{R}^n$ . Since

is orthogonal, when

spans $mathbf{R}^n$ , so does $tilde{x} := V^Tx$ . Decomposing the latter vector in two sub-vectors $tilde{x} = (tilde{x}_r,tilde{x}_{n-r})$ , we obtain that the range is the set of vectors Utilde{y}

, with

$tilde{y} = left( begin{array}{cc} {S} & 0 0 & 0 end{array} right)left( begin{array}{c} tilde{x}_r tilde{x}_{n-r} end{array}right) = left( begin{array}{c} {S} tilde{x}_r 0 end{array}right) ,$

where $tilde{x}_r$ is an arbitrary vector of $mathbf{R}^r$ . Since {S}

is invertible, $z := {S} tilde{x}_r$ also spans $mathbf{R}^r$ . We obtain that the range is the set of vectors Utilde{y}

, where

is of the form (z,0)

with $z in mathbf{R}^r$ arbitrary. This means that the range is the span of the first

columns of the orthogonal matrix

, and that these columns form an orthonormal basis for it. Hence, the number

of dyads appearing in the SVD decomposition is indeed the rank (dimension of the range).

Theorem: range and rank via SVD

The range of a matrix with SVD

$A = U tilde{ {S}} V^T, ;; tilde{ {S}} = mbox{bf diag}(sigma_1,ldots,sigma_r,0,ldots,0)$

where $U in mathbf{R}^{m times m}$ , $V in mathbf{R}^{n times n}$ are both orthogonal matrices, admits the first columns of as an orthonormal basis.

Full row rank matrices

An onto (or, full row rank) matrix has a range r=m

. These matrices are characterized by an SVD of the form

Fundamental theorem of linear algebra

Let $A in mathbf{R}^{m times n}$ . The sets mathbf{N} (A) and $mathbf{R} (A^T)$ form an orthogonal decomposition of $mathbf{R}^n$ , in the sense that any vector $x in mathbf{R}^n$ can be written as

$x = y + z, ;; y in mathbf{N} (A), ;; z in mathbf{R} (A^T), ;; y^Tz = 0.$

In particular, we obtain that the condition on a vector to be orthogonal to any vector in the nullspace implies that it must be in the range:

$x^Ty = 0 mbox{ whenever } Ay = 0 Longleftrightarrow exists : lambda in mathbf{R}^m ~:~ x = A^Tlambda.$

Matrix norms, condition number

Matrix norms are useful to measure the size of a matrix. Some of them can be interpreted in terms of input-output properties of the corresponding linear map; for example, the Frobenius norm measure the average response to unit vectors, while the largest singular (LSV) norm measures the peak gain. These two norms can be easily read from the SVD.

Frobenius norm

$|A|_F^2 = mbox{bf Tr} (V tilde{ {S}}^T tilde{ {S}} V^T) = mbox{bf Tr} (V^TV tilde{ {S}}^T tilde{ {S}}) = mbox{bf Tr} (tilde{ {S}}^T tilde{ {S}}) = sum_{i=1}^r sigma_i^2.$

Hence the squared Frobenius norm is nothing else than the sum of the squares of the singular values.

Largest singular value norm

An alternate way to measure matrix size is based on asking the maximum ratio of the norm of the output to the norm of the input. When the norm used is the Euclidean norm, the corresponding quantity

is called the largest singular value (LSV) norm. The reason for this wording is given by the following theorem.

Theorem: largest singular value norm

For any matrix ,

$|A|_{LSV} = max_{x ::: |x|_2 le 1} : |Ax|_2 = sigma_1(A),$

where sigma_1(A) is the largest singular value of . Any left singular vector associated with the singular value achieves the maximum in the above.

Condition number

The condition number of an invertible n times n

matrix

is the ratio between the largest and the smallest singular values:

As seen in the next section, this number provides a measure of the sensitivity of the solution of a linear equation to changes in