Inverse models and sensitivity

A unique computed allocation may still react strongly to small data changes. Invertibility answers whether an exact inverse exists; conditioning asks how strongly it can amplify errors. Keeping those questions separate prevents a mathematically valid solve from being mistaken for a robust estimate.

Finite elimination terminates and preserves the solution set

Let $A\in\mathbb R^{m\times n}$, $b\in\mathbb R^m$, with positive finite integers $m,n$. The permitted row operations are an exchange of two distinct rows, multiplication of a row by a nonzero scalar, and addition of a scalar multiple of one row to a different row. Their inverses are respectively the same exchange, multiplication by the reciprocal, and subtraction of that multiple. Applying an operation to the entire augmented array therefore preserves exactly the solutions of $Ax=b$: the new equations are consequences of the old, and its inverse gives the reverse implication. Each operation is also multiplication on the left by the result of applying it to the identity matrix, an invertible elementary matrix.

Scan the coefficient columns from left to right, maintaining the next unused row. If the current column has a nonzero entry in an unused row, exchange that row into the next position, divide by its nonzero pivot, and subtract multiples of it from every other row to clear that column. Advance the unused-row index. If every unused entry in the column is zero, skip the column. Previously chosen pivot columns remain unit columns: the current unused rows have zeros in them, so the new pivot row and every subsequent subtraction preserve those zeros and earlier pivots. There are only $n$ column scans and at most $\min(m,n)$ pivots, each with finitely many row operations. Thus the algorithm terminates. At its end, the nonzero coefficient rows have increasing pivot columns and zeros below and above each pivot; any remaining coefficient row is zero. This proves the reduced echelon form used below, without assuming it will eventually appear.

Classification and the homogeneous freedom

Write $r$ for the number of pivots in the coefficient part. A zero coefficient row with a nonzero transformed right side is the impossible equation $0=c$, so the system has no solution. Otherwise assign arbitrary real values to all $n-r$ nonpivot variables. In each pivot row, its pivot variable equals the transformed right side minus the displayed linear combination of these free variables; no other pivot variable occurs. These formulas both construct a solution and recover every solution. If $r=n$ the solution is unique. If $r<n$, changing a free variable changes the vector, giving infinitely many solutions.

For $Az=0$ the free variables can all be zero, giving the zero solution. If $r<n$, set one free variable to one and the others to zero, and use the pivot formulas. This constructs a nonzero homogeneous solution. If $r=n$, the formulas force every homogeneous variable to zero. For a consistent system, fixing one solution $x_p$, subtraction proves that every solution has the form $x_p+z$ with $Az=0$, and substitution proves the converse.

For square $A$, if every column has a pivot, the coefficient form is $I$. The product $E$ of the finitely many elementary matrices satisfies $EA=I$. Since $E$ is invertible, $A=E^{-1}$ and therefore also $AE=I$: $E$ is a two-sided inverse. If a pivot is missing, the nonzero homogeneous solution constructed above rules out any inverse. This also justifies applying the same row operations to $[A\mid I]$ to obtain $[I\mid A^{-1}]$ in the invertible case.

1 Inverses and elimination

For square $A$, an inverse is a matrix $B$ with $AB=BA=I$. It is unique: if $B,C$ are inverses, $B=B(AC)=(BA)C=C$. If $A$ and $B$ are invertible, $(AB)^{-1}=B^{-1}A^{-1}$, as multiplication in both orders verifies. The order reverses because the inverse must undo the last operation first.

Row operations are left multiplication by invertible elementary matrices. If elimination takes $A$ to $I$ through product $E$, then $EA=I$ and $E=A^{-1}$. Applying the same operations to $[A\mid I]$ gives $[I\mid A^{-1}]$.

A missing pivot gives a nonzero solution $z$ of the homogeneous system $Az=0$, which rules out invertibility.

For a $2\times2$ matrix,

$$A=\begin{pmatrix}a&b\\c&d\end{pmatrix},\qquad A^{-1}=\frac1{ad-bc}\begin{pmatrix}d&-b\\-c&a\end{pmatrix}$$

when $ad-bc\ne0$. Direct multiplication gives $(ad-bc)I$ before division, proving the formula. When $ad-bc=0$, row reduction or an explicit dependent-column argument shows singularity. The scalar $ad-bc$ is the determinant. A small determinant by itself is not a scale-invariant measure of poor conditioning: $0.001I$ has a small determinant but preserves relative input errors perfectly.

2 Reciprocal allocation near a singular rule

For $1-\alpha\beta\ne0$, the equations $a=d_A+\alpha b$, $b=d_B+\beta a$ have the following coefficient matrix and inverse

$$A=\begin{pmatrix}1&-\alpha\\-\beta&1\end{pmatrix},\qquad A^{-1}=\frac1{1-\alpha\beta}\begin{pmatrix}1&\alpha\\\beta&1\end{pmatrix}.$$

For $\alpha,\beta\ge0$ and $\alpha\beta<1$, nonnegative direct costs give nonnegative totals. The denominator also shows why rules approaching full mutual recycling can produce large gross totals. At $\alpha=\beta=0.99$ and direct costs $(1,1)$, totals are $(100,100)$. Increasing each direct cost by 0.01 increases each total by 1.

This is a factor-100 amplification of absolute changes. It is not a factor-100 amplification of relative changes in this example: both direct and total costs rise by 1%. Relative sensitivity depends on directions and on the baseline state. Gross totals also include repeated internal services, so they should not be interpreted as newly created external spending.

3 Norms and a relative-error bound

For a vector, $\|x\|_\infty=\max_i|x_i|$. Its induced matrix norm is the maximum absolute row sum, $\|A\|_\infty=\max_i\sum_j|a_{ij}|$. The inequality $\|Ax\|_\infty\le\|A\|_\infty\|x\|_\infty$ follows by bounding each row's dot product. Induced norms are submultiplicative, since applying the vector bound twice gives $\|ABx\|\le\|A\|\|B\|\|x\|$.

If $Ax=b$ and the data change by $\delta b$ while $A$ stays fixed, then $\delta x=A^{-1}\delta b$. For nonzero $b$,

$$\frac{\|\delta x\|}{\|x\|}\le\kappa(A)\frac{\|\delta b\|}{\|b\|},\qquad \kappa(A)=\|A\|\|A^{-1}\|.$$

Proof. The first bound gives $\|\delta x\|\le\|A^{-1}\|\|\delta b\|$. Also $\|b\|=\|Ax\|\le\|A\|\|x\|$, so $1/\|x\|\le\|A\|/\|b\|$. Multiply. $\square$

The condition number is a worst-case bound, not an equality for every perturbation. It is at least 1 because $1=\|I\|\le\|A\|\|A^{-1}\|$. Its practical interpretation also depends on chosen units and scaling of observations and unknowns.

Worked example. Take $A=\operatorname{diag}(1,0.01)$, $b=(1,0.01)$, giving $x=(1,1)$. A data perturbation $(0,0.001)$ changes $x$ by $(0,0.1)$. In the infinity norm the data's relative change is 0.001, the solution's is 0.1, and $\kappa_\infty(A)=100$. The bound is attained here.

The induced infinity norm has the claimed lower bound too

For positive finite $m,n$ and $A\in\mathbb R^{m\times n}$, put $R=\max_i\sum_j|a_{ij}|$. The vector norm $\|x\|_\infty=\max_j|x_j|$ is positive away from zero and absolutely homogeneous. The coordinate inequalities $|x_j+y_j|\le|x_j|+|y_j|$ also prove its triangle inequality. Define the induced matrix norm as $\sup_{x\ne0}\|Ax\|_\infty/\|x\|_\infty$. Each row satisfies $|(Ax)_i|\le\sum_j|a_{ij}|\|x\|_\infty$, so the supremum is at most $R$.

If $R=0$, all entries are zero and the supremum is zero. If $R>0$, choose a row $i_*$ attaining the finite maximum and set $x_j=1$ when $a_{i_*j}>0$, $x_j=-1$ when $a_{i_*j}<0$, and $x_j=0$ otherwise. At least one entry of this vector has magnitude one, so $\|x\|_\infty=1$. Moreover $(Ax)_{i_*}=\sum_j|a_{i_*j}|=R$. The supremum is therefore at least $R$, proving $\|A\|_\infty=R$. The argument constructs a maximizing sign vector; an upper estimate alone would not prove this equality.

A convergent matrix geometric series in every induced real norm

Why a norm on a finite real coordinate space is complete

Fix an integer $n\ge1$ and the Euclidean norm on $\mathbb R^n$. A set is bounded if it lies in some finite-radius ball, closed if its complement is open, and compact if every cover by open subsets of $\mathbb R^n$ has a finite subcover. We use real completeness, including the nested closed interval property.

Heine–Borel in finite-dimensional Euclidean space

Theorem. A set $K\subseteq\mathbb R^n$ is compact if and only if it is closed and bounded. The empty set satisfies all three properties.

Compact implies bounded. The open balls $B(0,m)$, $m\ge1$ an integer, cover $K$. A finite subcover puts $K$ inside the largest of these balls.

Compact implies closed. Suppose $K\ne\varnothing$ and $y\notin K$. The balls $B(x,\|x-y\|/2)$, $x\in K$, cover $K$. Choose a finite subcover with centers $x_1,\ldots,x_r$ and set $\delta=\min_i\|x_i-y\|/2>0$. If $z$ lies in the ball centered at $x_i$, the triangle inequality gives $\|z-y\|>\|x_i-y\|/2\ge\delta$. Hence $B(y,\delta)$ misses $K$, so the complement is open.

Closed and bounded implies compact. Let nonempty $K$ be closed and bounded. Enclose it in a closed cube $Q_0=[-M,M]^n$ with $M>0$. Suppose an open cover of $K$ has no finite subcover. Divide each coordinate interval into two closed halves. The resulting $2^n$ closed subcubes cover $Q_0$. At least one subcube has intersection with $K$ that is not finitely coverable by the given family; otherwise the finite union of the finite subcovers would cover $K$. Select such a subcube and repeat. This produces nested closed cubes $Q_j$ with side length $2M/2^j$ and $K\cap Q_j$ not finitely coverable, hence nonempty.

For each coordinate, the nested interval property gives a common coordinate value. Together these give $p\in\bigcap_jQ_j$. Every pair of points in $Q_j$ has distance at most $2M\sqrt n/2^j$, so the intersection contains only $p$. Choose $x_j\in K\cap Q_j$. Then $\|x_j-p\|\le2M\sqrt n/2^j\to0$. A closed set contains such a limit: if $p$ were in its open complement, a ball around $p$ would eventually contain $x_j$ outside $K$, a contradiction. Thus $p\in K$.

One member $O$ of the cover contains $p$, and openness gives $B(p,\varepsilon)\subseteq O$ for some $\varepsilon>0$. For sufficiently large $j$, every point of $Q_j$ is within $\varepsilon$ of $p$, so $O$ alone covers $K\cap Q_j$. This contradicts the selection of $Q_j$. Therefore every open cover has a finite subcover. The number $2^n$ is finite; replacing it by infinitely many subpieces would invalidate this argument.

Continuous images and extreme values

Theorem. If $K\subseteq\mathbb R^n$ is compact and $F:K\to\mathbb R^m$ is continuous relative to $K$, then $F(K)$ is compact. In particular, a continuous $f:K\to\mathbb R$ on nonempty compact $K$ is bounded and attains its maximum and minimum.

Proof. An open cover $(O_i)$ of $F(K)$ pulls back to relatively open sets $F^{-1}(O_i)=K\cap U_i$, with $U_i$ open in $\mathbb R^n$. These $U_i$ cover $K$, so finitely many suffice. Their corresponding $O_i$ cover $F(K)$, proving compactness. For scalar $f$, the image is nonempty, closed and bounded by the theorem already proved in dimension one. Let $a=\sup f(K)$. For each $j\ge1$, the definition of supremum supplies $y_j\in f(K)$ with $a-1/j<y_j\le a$. Then $y_j\to a$, and closedness places $a$ in the image. Thus the maximum is attained. Applying the same argument to $-f$ gives the minimum. This proves existence, not a formula for the maximizing input.

Let $d\ge1$ be finite and let $N$ be any norm on $\mathbb R^d$: it is positive except at zero, absolutely homogeneous, and satisfies the triangle inequality. Write $e_j$ for the standard coordinate vectors and $\|x\|_2=(\sum_jx_j^2)^{1/2}$. Put $C=\sum_{j=1}^dN(e_j)>0$. Expanding in the standard basis gives

$$N(x)\le\sum_j|x_j|N(e_j)\le C\|x\|_2.$$

The reverse triangle inequality gives $|N(x)-N(y)|\le N(x-y)\le C\|x-y\|_2$, so $N$ is Euclidean-continuous. The proved compactness theorem applies to the nonempty Euclidean unit sphere. Hence $N$ attains a minimum $m$ there; $m>0$ because every point of that sphere is nonzero. For $x\ne0$, apply this minimum to $x/\|x\|_2$. Including $x=0$, we obtain

$$m\|x\|_2\le N(x)\le C\|x\|_2.$$

If $(x_k)$ is $N$-Cauchy, each coordinate is real-Cauchy, since $|(x_k-x_l)_j|\le\|x_k-x_l\|_2\le N(x_k-x_l)/m$. Real completeness supplies limits $a_j$. The finite sum of the squared coordinate differences tends to zero, so $\|x_k-a\|_2\to0$ and then $N(x_k-a)\le C\|x_k-a\|_2\to0$. Thus every $N$-Cauchy sequence converges in $N$. The zero-dimensional space has just the zero vector and is complete separately. No infinite-dimensional completeness or equivalence-of-norms claim is being made.

Fix a real norm $N$ on $\mathbb R^n$, $n\ge1$, and define the induced matrix norm by $\|A\|=\sup_{x\ne0}N(Ax)/N(x)$. The established inequalities $m\|x\|_2\le N(x)\le C\|x\|_2$ make this supremum finite: the elementary bounds $|(Ax)_i|\le(\sum_j|a_{ij}|)\|x\|_2$ give $\|Ax\|_2\le(\sum_{i,j}|a_{ij}|)\|x\|_2$, since the Euclidean norm of a nonnegative list is at most its sum. Hence the ratio is at most $(C/m)\sum_{i,j}|a_{ij}|$. Homogeneity and the triangle inequality follow by taking suprema of the corresponding vector inequalities. If $A\ne0$, some standard vector $e_j$ has $Ae_j\ne0$, so $\|A\|>0$. Thus this is a norm on the finite real vector space of $n\times n$ matrices, and that space is complete by the proved finite-coordinate result. Moreover $\|I\|=1$, $N(Ax)\le\|A\|N(x)$, and applying this bound twice gives $\|AB\|\le\|A\|\|B\|$.

Let $q=\|M\|<1$. For $k\ge1$, $\|M^k\|\le q^k$; the separate zeroth term is $M^0=I$, of norm one. If $q=0$, $M=0$ and the series is just $I$. Otherwise $0<q<1$ and $q^k\to0$: write $1/q=1+\delta$, $\delta>0$, and use $(1+\delta)^k\ge1+k\delta$. The finite geometric identity gives $\sum_{k=s}^tq^k\le q^s/(1-q)$. Consequently the partial sums $S_N=\sum_{k=0}^NM^k$ are Cauchy in the complete matrix space, so they converge to a matrix $S$ and $\|S\|\le1/(1-q)$.

Finite multiplication telescopes in both orders:

$$(I-M)S_N=S_N(I-M)=I-M^{N+1}.$$

Submultiplicativity makes multiplication by the fixed matrix $I-M$ continuous, while $\|M^{N+1}\|\le q^{N+1}\to0$. Taking limits proves $(I-M)S=S(I-M)=I$. Thus the series is the two-sided inverse of $I-M$, with the displayed norm bound. For the perturbation formula take $M=-A^{-1}E$; the factorization $A+E=A(I+A^{-1}E)$ then gives $\|(A+E)^{-1}\|\le\|A^{-1}\|/(1-\|A^{-1}E\|)$. No diagonalization or infinite-dimensional Banach-space premise was left implicit.

4 Perturbing the model coefficients

If $A$ changes to $A+E$, factor it as $A(I+A^{-1}E)$. For any induced norm with $\|A^{-1}E\|<1$, the geometric matrix series

$$(I+A^{-1}E)^{-1}=\sum_{k=0}^\infty(-A^{-1}E)^k$$

converges absolutely. Finite partial products telescope to $I-(-A^{-1}E)^{N+1}$, whose remainder tends to zero; this proves it is the inverse, without diagonalizability. Consequently

$$\|(A+E)^{-1}\|\le\frac{\|A^{-1}\|}{1-\|A^{-1}E\|}.$$

If the perturbed system has right-hand side $b+\delta b$, subtract equations to obtain $(A+E)\delta x=\delta b-Ex$. This identity exposes both observation error and coefficient error. Small entrywise changes in an ill-conditioned model need not mean small solution changes.

5 Graded practice

E1 Foundation. Invert $A=\begin{pmatrix}2&1\\1&1\end{pmatrix}$ and solve $Ax=(3,2)^T$.

E2 Conditioning. Continue with the matrix and baseline right-hand side $b=(3,2)^T$ from E1. Find $\kappa_\infty(A)$. For $\delta b=(\varepsilon,-\varepsilon)$, calculate $\delta x$ and compare the relative bound.

E3 Scaling. Explain why $A=10^{-6}I$ has a tiny determinant in dimension 2 but condition number 1.

E4 Coefficient error. For $A=I$ and $\|E\|\le0.1$, give a bound for $\|(I+E)^{-1}\|$ and for the relative solution change when the right-hand side is fixed and nonzero. State separately what happens for zero right-hand side.

6 Full solutions

S1. The determinant is 1 and $A^{-1}=\begin{pmatrix}1&-1\\-1&2\end{pmatrix}$. Multiplying by $(3,2)$ gives $(1,1)$, checked in the original system.

S2. The maximum row sum of $A$ is 3 and of its inverse is 3, so $\kappa_\infty=9$. The solution perturbation is $(2\varepsilon,-3\varepsilon)$. The baseline solution has norm 1, so relative solution error is $3|\varepsilon|$; baseline $b$ has norm 3, so the condition bound is $9|\varepsilon|/3=3|\varepsilon|$, attained here.

S3. Its determinant is $10^{-12}$, but its inverse is $10^6I$. Thus the product of induced norms is $10^{-6}10^6=1$. Uniform scaling changes absolute size without distorting relative directions.

S4. The inverse norm is at most $1/(1-0.1)=10/9$. With fixed nonzero data $b$, the baseline solution $x=b\ne0$ and $(I+E)\delta x=-Ex$, so $\|\delta x\|/\|x\|\le(10/9)(0.1)=1/9$. If $b=0$, both unique solutions are zero; their absolute change is zero, but a relative ratio with zero baseline norm is undefined. The hypothesis is a norm bound, not merely a statement that every entry is below 0.1.

Summary

Invertibility establishes a unique exact inverse; conditioning measures its sensitivity. Absolute and relative amplification are different. Norm inequalities provide defensible bounds, and a convergent matrix geometric series controls coefficient perturbations without assuming diagonalizability or treating a small determinant as a complete stability diagnosis.