Matrix Condition

Matrix Norm from Vector Norm

Have you ever wondered how we can measure the "size" of a matrix? Just like vectors that have length, matrices also require the concept of "size" called matrix norm. What's interesting is that we can build matrix norms directly from vector norms that we already know.

If we have a vector norm on space $\mathbb{R}^n$ , then we can define a corresponding matrix norm on $\mathbb{R}^{n \times n}$ through the formula:

\|A\| = \sup_{x \in \mathbb{R}^n} \frac{\|Ax\|}{\|x\|} = \max_{x \in \mathbb{R}^n: \|x\|=1} \|Ax\|

The norm produced this way is called the natural matrix norm that is induced by the vector norm. This norm has two important properties that make it very useful in numerical analysis.

Compatibility Property: For all matrices $A \in \mathbb{R}^{n \times n}$ and vectors $x \in \mathbb{R}^n$ , the following holds:

$\|Ax\| \leq \|A\| \cdot \|x\|$
Multiplicative Property: For all matrices $A, B \in \mathbb{R}^{n \times n}$ , the following holds:

$\|AB\| \leq \|A\| \cdot \|B\|$

Both properties are very fundamental because they ensure that matrix norms behave consistently with matrix and vector multiplication operations.

Examples of Special Matrix Norms

Let's look at some concrete examples of matrix norms that are often used in practice.

Maximum Column Norm: If we use the norm $\|x\|_1 = \sum_{i=1}^n |x_i|$ on vectors, then the induced matrix norm is:

$\|A\|_1 = \max_{j=1,\ldots,n} \sum_{i=1}^n |a_{ij}|$

This means we look for the column with the largest sum of absolute values.
Maximum Row Norm: If we use the maximum norm $\|x\|_\infty = \max_{i=1,\ldots,n} |x_i|$ on vectors, then the induced matrix norm is:

$\|A\|_\infty = \max_{i=1,\ldots,n} \sum_{j=1}^n |a_{ij}|$

This means we look for the row with the largest sum of absolute values.

Both norms are very easy to compute and provide good estimates for numerical algorithm stability analysis.

Linear System Stability

Why do we need to understand matrix condition? The answer lies in the problem of numerical stability. When we solve linear equation systems $Ax = b$ using computers, there is always the possibility of small errors in data or calculations.

Imagine we have a slightly perturbed system. Instead of solving $Ax = b$ , we actually solve the perturbed system $\tilde{A}\tilde{x} = \tilde{b}$ where $\tilde{A} = A + \delta A$ and $\tilde{b} = b + \delta b$ .

The crucial question is how much influence do small perturbations $\delta A$ and $\delta b$ have on the solution $\tilde{x}$ ?

If matrix $A$ is regular and the perturbation is small enough such that $\|\delta A\| < \frac{1}{\|A^{-1}\|}$ , then the perturbed matrix $\tilde{A} = A + \delta A$ is also regular.

For the relative error in the solution, we obtain the estimate:

\frac{\|\delta x\|}{\|x\|} \leq \frac{\text{cond}(A)}{1 - \text{cond}(A)\|\delta A\|/\|A\|} \left( \frac{\|\delta b\|}{\|b\|} + \frac{\|\delta A\|}{\|A\|} \right)

where $\text{cond}(A)$ is the condition number of matrix $A$ .

The condition number measures the sensitivity of linear system solutions to small perturbations in input data.

Spectral Radius and Eigenvalues

Before discussing condition numbers further, we need to understand the concept of spectral radius. The spectral radius of a matrix $A$ is defined as:

\text{spr}(A) = \max\{|\lambda| : \lambda \text{ is an eigenvalue of } A\}

The spectral radius provides information about the eigenvalue with the largest magnitude of the matrix.

There is an interesting relationship between spectral radius and matrix norms. For every eigenvalue $\lambda$ of matrix $A$ , the following holds:

|\lambda| \leq \|A\|

This means that matrix norms provide an upper bound for all eigenvalues.

A more specific result applies to the spectral norm or 2-norm of matrices. For symmetric matrices $A \in \mathbb{R}^{n \times n}$ , the spectral norm equals the spectral radius:

\|A\|_2 = \max\{|\lambda| : \lambda \text{ eigenvalue of } A\} = \text{spr}(A)

For general matrices, the spectral norm is computed as:

\|A\|_2 = \sqrt{\text{spr}(A^T A)}

Condition Number

Now we arrive at the central concept in numerical analysis, namely the condition number. For invertible matrices $A \in \mathbb{R}^{n \times n}$ , the condition number is defined as follows.

\text{cond}(A) = \|A\| \cdot \|A^{-1}\|

The condition number measures how "bad" a matrix is in the context of numerical stability. The larger the condition number, the more sensitive the system is to small perturbations.

Spectral Condition

For symmetric matrices, we can compute the condition number explicitly using eigenvalues. The spectral condition of symmetric matrices is:

\text{cond}_2(A) = \frac{|\lambda_{\max}|}{|\lambda_{\min}|}

where $\lambda_{\max}$ and $\lambda_{\min}$ are the eigenvalues with the largest and smallest magnitudes.

The spectral condition provides a very clear interpretation. A matrix has bad condition if:

Its eigenvalues are very different in magnitude (large ratio)
There are eigenvalues that are very small (approaching singular)

Conversely, matrices with good condition have eigenvalues that are relatively uniform in magnitude.

The condition number provides a quantitative measure of how sensitive linear system solutions are to small perturbations in input data.