Linear systems can be solved by rewriting them as fixed point equations. The focus keyword fixed point linear systems marks the method: write $Tx=x$ and prove that $T$ is a contraction under a suitable metric. Row sums, column sums, and square sums correspond to maximum, sum, and Euclidean metrics. :::definition[Linear Fixed Point Mapping] Consider $x_i=\sum_{j=1}^n a_{ij}x_j+b_i$ for $i=1,\ldots,n$. Define $T:\mathbb C^n\to\mathbb C^n$ by $(Tx)_i=\sum_{j=1}^n a_{ij}x_j+b_i$. A solution of the system is exactly a fixed point of $T$. ::: :::theorem[Linear System Criterion in the Maximum Metric] Let $d_\infty(x,y)=\max_i|x_i-y_i|$. If $\sum_{j=1}^n|a_{ij}|\leq\alpha<1$ for every $i$, then the system has exactly one solution. ::: :::proof Given the row sum bound. To prove unique solvability. For $x,y\in\mathbb C^n$, $|(Tx)_i-(Ty)_i|\leq\sum_j|a_{ij}||x_j-y_j|\leq\alpha d_\infty(x,y)$. Taking maximum over $i$ gives $d_\infty(Tx,Ty)\leq\alpha d_\infty(x,y)$. Thus $T$ is a contraction on complete $\mathbb C^n$, so the system has a unique solution. $\square$ ::: :::theorem[Linear System Criterion in the Sum Metric] Let $d_1(x,y)=\sum_i|x_i-y_i|$. If $\sum_i|a_{ij}|\leq\alpha<1$ for every $j$, then the system has exactly one solution. ::: :::proof Given the column sum bound. To prove unique solvability. We have $d_1(Tx,Ty)\leq\sum_i\sum_j|a_{ij}||x_j-y_j|=\sum_j(\sum_i|a_{ij}|)|x_j-y_j|\leq\alpha d_1(x,y)$. Hence $T$ is a contraction, and the contraction mapping principle gives a unique solution. $\square$ ::: :::theorem[Linear System Criterion in the Euclidean Metric] Let $d_2(x,y)=(\sum_i|x_i-y_i|^2)^{1/2}$. If $\sum_i\sum_j|a_{ij}|^2\leq\alpha^2<1$, then the system has exactly one solution. ::: :::proof Given the square-sum bound. To prove unique solvability. By Cauchy-Schwarz, $|(Tx)_i-(Ty)_i|^2\leq(\sum_j|a_{ij}|^2)(\sum_j|x_j-y_j|^2)$. Summing over $i$ gives $d_2(Tx,Ty)^2\leq\alpha^2 d_2(x,y)^2$. Hence $T$ is a contraction, and the system has a unique fixed point. $\square$ ::: :::solved-problem Show that $x=x/4+y/5+1$, $y=x/6+y/3+2$ has a unique solution by the maximum metric criterion. ::: :::solution The row sums are $1/4+1/5=9/20<1$ and $1/6+1/3=1/2<1$. Hence both row sums are bounded by $\alpha=1/2<1$. The associated mapping is a contraction in the maximum metric, so the system has a unique solution. ::: :::exercise 1. State the fixed point mapping associated with a linear system. 2. Which metric uses row sums? 3. Which metric uses column sums? ::: :::answer 1. $(Tx)_i=\sum_ja_{ij}x_j+b_i$. 2. The maximum metric. 3. The sum metric. :::