Ill-Conditioning in Nearly Dependent Systems

When a Small Data Change Matters

A linear system can have a unique solution and still be difficult to solve reliably. The issue is sensitivity: if a small change in the data produces a much larger change in the solution, then the system is ill-conditioned. This often happens when rows or columns are nearly dependent. Nearly dependent rows make two equations almost redundant; nearly dependent columns make two directions in the output almost indistinguishable. In either case, recovering the solution may require magnifying a small difference in the data.

We will use the infinity norm to make these comparisons exact. For a vector \(\mathbf{x}\in\mathbb{R}^n\), \(\|\mathbf{x}\|_{\infty}\) is the largest absolute value of its entries. For a matrix \(\mathbf{A}\), the induced infinity norm is the largest absolute row sum. For a nonsingular square matrix, its infinity-norm condition number is the product of the norms of the matrix and its inverse.

Here, “nearly dependent” means that one row or column is close to a multiple or combination of others, so the corresponding difference is small. It does not mean that the system is singular: the systems below have unique solutions for every positive parameter. As the parameter gets smaller, however, the small difference that distinguishes the equations or columns becomes increasingly important.

Nearly Equal Rows and a Sensitive Solution

Why Near Dependence Signals Ill-Conditioning

The example’s subtraction step exposes the mechanism: the equations determine \(x_2\) through a coefficient of only \(\varepsilon\). A small change in the difference between the right-hand sides is divided by \(\varepsilon\). A corresponding effect occurs when two columns are close: a small output difference can require a large change in the coefficients of those columns.

Proof. Since \(\mathbf{A}\) is nonsingular and \(\mathbf{c}\ne\mathbf{0}\), the vector \(\mathbf{A}\mathbf{c}\ne\mathbf{0}\). Also, \(\mathbf{A}^{-1}(\mathbf{A}\mathbf{c})=\mathbf{c}\). By the defining bound for an induced matrix norm, \(\|\mathbf{A}^{-1}(\mathbf{A}\mathbf{c})\|_{\infty}\leq\|\mathbf{A}^{-1}\|_{\infty}\|\mathbf{A}\mathbf{c}\|_{\infty}\). The left side is \(\|\mathbf{c}\|_{\infty}\); dividing by the positive number \(\|\mathbf{A}\mathbf{c}\|_{\infty}\) proves the first inequality. Multiplying it by \(\|\mathbf{A}\|_{\infty}\) proves the second. \(\square\)

For a matrix whose columns are nearly dependent, choose coefficients \(\mathbf{c}\) that nearly cancel the columns. Then \(\mathbf{A}\mathbf{c}\) is small even though \(\mathbf{c}\) is not, and the proposition forces a large condition number. The same logic applies when rows are nearly dependent: the inverse can become large, as the explicit row-sum calculation in the example shows.

Comparing with a Well-Conditioned System

A large condition number is a worst-case sensitivity measure, not a prediction that every perturbation will be amplified by exactly that amount. The following comparison uses the same right-hand side and perturbation as before, but an identity matrix. It separates sensitivity caused by the system from the size of the data change itself.

Proof. Subtract the two equations \(\mathbf{A}\widetilde{\mathbf{x}}=\widetilde{\mathbf{b}}\) and \(\mathbf{A}\mathbf{x}=\mathbf{b}\). This gives \(\mathbf{A}(\widetilde{\mathbf{x}}-\mathbf{x})=\delta\mathbf{b}\), so \(\widetilde{\mathbf{x}}-\mathbf{x}=\mathbf{A}^{-1}\delta\mathbf{b}\). The induced norm bound yields \(\|\widetilde{\mathbf{x}}-\mathbf{x}\|_{\infty}\leq\|\mathbf{A}^{-1}\|_{\infty}\|\delta\mathbf{b}\|_{\infty}\). Also, \(\mathbf{b}=\mathbf{A}\mathbf{x}\), hence \(\|\mathbf{b}\|_{\infty}\leq\|\mathbf{A}\|_{\infty}\|\mathbf{x}\|_{\infty}\). Since \(\mathbf{b}\ne\mathbf{0}\) and \(\mathbf{A}\) is nonsingular, \(\mathbf{x}\ne\mathbf{0}\); divide the first bound by \(\|\mathbf{x}\|_{\infty}\), and use the second bound to obtain the stated inequality. \(\square\)

This result is an upper bound: it says the relative solution change cannot exceed the condition number times the relative right-hand-side change. It need not be attained for a particular perturbation. The exact examples show one direction of sensitivity for which the change is substantial, while the identity example shows that the same data change can have little effect in a well-conditioned system.

Common Pitfalls

Do not confuse a small parameter with a zero parameter. If \(\varepsilon=0\), the rows of \(\mathbf{A}_{\varepsilon}\) coincide and the matrix is singular, so the inverse and condition number are not defined. For \(\varepsilon>0\), the system has a unique solution, but its condition number grows as the row difference shrinks.

Check each row sum before taking a matrix infinity norm. For the inverse in the first example, the first absolute row sum is \(201\), while the second is \(200\). A tempting but incorrect calculation is to assign \(201\) to both rows, perhaps by using the first row’s sum twice. The correction is to calculate each row separately: the norm is still \(201\), because it is the maximum of \(201\) and \(200\), not because the two sums agree. Likewise, for general \(\varepsilon>0\), the first inverse row sum is \(\tfrac{2+\varepsilon}{\varepsilon}\), and the second is \(\tfrac{2}{\varepsilon}\); the maximum is the first.

A large condition number does not mean every change is amplified by that factor. The condition number bounds worst-case relative sensitivity. A particular perturbation may have a smaller effect; calculate the changed solution or apply the bound with the actual perturbation rather than treating the bound as an equality.

Nearly dependent systems matter whenever equations encode almost the same constraint or columns encode almost the same direction. The solution may be mathematically unique, but small uncertainty in the data can then lead to substantial uncertainty in the answer. Checking row or column relationships and comparing condition numbers helps distinguish uniqueness from practical stability.