Condition Number and Singularity

What is the condition number?

A n x n matrix with fewer than n nonzero singular values is singular, such a matrix has a condition number of infinity.

Why does condition number matter?

Any matrix that isn’t of full rank is singular. Any singular matrix has a condition number infinity. Any matrix with a very large condition number is considered ill-conditioned. The larger the condition number, the closer the matrix is to being singular.

A matrix being ill-condition is bad since when doing computerized matrix arithmetic, small errors will add up when dealing with ill-conditioned matrices, resulting in large errors in the solution.

How does low rank approxmation work?

Say you have a ill-conditioned matrix with rank r. Instead of doing SVD on the whole matrix, take a number k such that $1\le k\le r$ and decompose the matrix like so:

$A_k=P_k{\Sigma }_k{Q}_k^T$.

where: $P_k\in {\mathbb{R}}^{m\times r}$: first k columns of P ${\Sigma }_k=diag({\sigma }_1,...,{\sigma }_r)$: top left k x k block of singular values $Q_k^T\in {\mathbb{R}}^{r\times n}$: first k columns of Q

$A_k$ has rank k and among all matrices B of rank k, $A_k$ minimizes $||A-B|{|}_2$.

What is the Gershgorin Circle Theorem?

All real and complex eigenvalues of the matrix A like in its Gershgorin domain $D_A\subset \mathbb{C}$. Let $A=(a_{ij})$ be an n x n matrix. For each $1\le i\le n$, define the ith Gershgorin disk: $D_i=z\in \mathbb{C}:|z-a_{ii}|\le r_i$ , where $r_i={\sum }_{j\ne i}|a_{ij}|$.

The full Gershgorin domain is the union of all $D_i$.

What is Diagonal Dominance?

A matrix $A=(a_{i}j)$ is strictly diagonally dominant if: $|a_{ij}|>{\sum }_{j\ne i}|a_{ij}|$, for all i. A strictly diagonally dominant matrix is non-singular.