Solving Equation system

Notations

$A=\left[\begin{array}{cccc}{\mathbf{v}}_1& {\mathbf{v}}_2& \dots & {\mathbf{v}}_n\end{array}\right]$

$$b=A\mathbf{x}$$ $$b=\sum _{j=1}^n{x}_j{\mathbf{v}}_j$$

$A=\left[\begin{array}{c}{\mathbf{u}}_1^{\top }\\ {\mathbf{u}}_2^{\top }\\ ⋮\\ {\mathbf{u}}_m^{\top }\end{array}\right]$

$$b_i={\mathbf{u}}_i^{\top }\mathbf{x}$$

Method: Gauss elimination

Gaus elimination succeeds $\leftrightarrow$ The columns of $A$ are linearly independent

Method: Gauss-Jordan Elimination

Gauss-Jordan Elimination

All solutions of $A\mathbf{x}=\mathbf{b}$

Definition: The solution space

$\mathbf{Sol}(A,b)\stackrel{def}{=}\{\mathbf{x}\in {\mathbb{R}}^n:A\mathbf{x}=\mathbf{b}\}\subseteq {\mathbb{R}}^n$

It’s obvious that $\mathbf{Sol}(A,0)=\mathbf{N}(A)$ (see How to compute null space) and $\mathbf{Sol}(A,\mathbf{b})$ is just a shifted null space visualization of a shifted null space Thus,

$$\mathbf{Sol}(A,\mathbf{b})=\{\mathbf{s}+\mathbf{x}:\mathbf{x}\in \mathbf{N}(A)\}$$

To solve $\mathbf{Sol}(A,\mathbf{b})$, we just compute one solution using Gauss-Jordan Elimination and a basis $B=\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_{n-r}\}$ from $\mathbf{N}(A)$. Then

$$\mathbf{Sol}(A,\mathbf{b})=\left\{s+\sum _{i=1}^{n-r}{\lambda }_i{\mathbf{v}}_i:{\lambda }_i\in \mathbb{R}\text{ for }i\in [n-r]\right\}$$

Generally, a shifted copy of a subspace in a vector space is called an affine subspace

Theorem 6.2.2

Theorem 6.2.2

Suppose $\mathbf{Sol}(A,b)$ is not empty $\mathbf{Sol}(A,b)=x_1+N(A)$ where $x_1\in \mathbf{R}(A)$ is unique such that $A{x}_1=b$

Now we know that we can find a unique vector that can represent $\mathbf{Sol}(A,b)$ The vector $x_1$ is orthogonal to the $N(A)$ (the shortest position vector)

• Proof

Edge case

Question

What if $\mathbf{Sol}(A,b)$ is empty?

Let $A=[a_1|a_2|\dots |a_n]$ Consider the equation ${\sum }_{i=1}^n{\lambda }_i{a}_i+\mu \cdot b=0$ $b$ is linear independent from $\{a_1,\dots ,a_n\}$ The equation has a solution if $\mu =0$ $⟺b=-{\sum }_{i=1}^n\frac{{\lambda }_i{a}_i}{u}$

$\mathbf{Sol}(A,b)=\varnothing ⟺\{z\in {\mathbb{R}}^m|A^{\top }z=0,b^{\top }z=1\}\ne \varnothing$

Let $P=\mathbf{Sol}(A,b)$, $D=\{z\in {\mathbb{R}}^m|A^{\top }z=0,b^{\top }z=1\}$ Proof: $P$ and $D$ can have a same solution $z\in D$ and $x\in P$ $0=0^{\top }x=z^{\top }Ax=z^{\top }b=1$ $⟹Contradiction$

Proof: $P=\varnothing ⟹D\ne \varnothing$ $P=\varnothing ⟹b\notin C(A)⟺b-{\text{proj}}_{C(A)}(b)\ne 0$ $b={\text{proj}}_{C(A)}(b)+q$ with $q\in C(A{)}^{\perp }=N(A^{\top })$ This means $q\ne 0$ Let $z=\frac{1}{q^{\top }q}q$

$z\in N(A^{\top })⟹A^{\top }z=0$ $b^{\top }z=\frac{1}{q^{\top }q}{b}^{\top }q=\frac{1}{q^{\top }q}(p+q{)}^{\top }q=\frac{1}{q^{\top }q}\underset{0}{\underbrace{p^{\top }q}}+\frac{1}{q^{\top }q}{q}^{\top }q=1$

Application: Row Independent Equation Systems

If $A\in {\mathbb{R}}^{m\times n}$ and the rows are linear independent: $\{x\in {\mathbb{R}}^n|Ax=b\}$ is solvable for all $b\in {\mathbb{R}}^m$ Proof: $z^{\top }A=0⟹x=0⟹z^{\top }b=0\ne 1⟹D=\varnothing$

Application: Projection System

$A^{\top }Ax=A^{\top }b$ is always solvable for all $b\in {\mathbb{R}}^m$ Proof: $z^{\top }{A}^{\top }A=0⟺z\in N(A^{\top }A)=N(A)$ (See Lemma 5.1.10) $⟹Az=0⟹z^{\top }{A}^{\top }b=(Az{)}^{\top }b=0\ne 1⟹D=\varnothing$

Dimension of the solution space

Theorem 4.39

If $A\mathbf{x}=\mathbf{b}$ has a solution, then $\mathbf{Sol}(A,\mathbf{b})$ has dimension $n-r$, since $\text{dim}(\mathbf{Sol}(A,\mathbf{b}))=\text{dim}(\mathbf{N}(A))$

Lemma 6.2.1

Lemma 6.2.1

Let $A\in {\mathbb{R}}^{m\times n}$. Let $x,y\in \mathbf{C}(A^{\top })$. We have$$ Ax=Ay\Longleftrightarrow x=y

**Proof**: $x \in C(A^{\top}), y\in C(A^{\top}) \implies x-y\in C(A^{\top})$ $Ax=Ay\implies A(x-y)=0\implies x-y\in N(A)\implies x-y \in C(A^{\top})^{\perp}$ $(x-y\in C(A^{\top}))\wedge (x-y\in C(A^{\top})^{\perp})\implies x-y=0\implies x=y$ ## Certificate $A\in \mathbb{R}^{m\times n},b\in \mathbb{R}^{m},A=\begin{bmatrix}a_{1}^{\top} \\ a_{2}^{\top} \\ \vdots \\ a^{\top}_{m}\end{bmatrix}$ $a_{i}^{\top}\in \mathbb{R}^{n}$, consider $P=\{ x \in \mathbb{R}^{n}|a_{i}^{\top}x\leq b_{i}, \;i \in[m]\}=\{ x \in \mathbb{R}^{n}|Ax\leq b\}$ ### Theorem: Farkas $P=\{ x \in \mathbb{R}^{n}|Ax\leq b\}=\varnothing\Longleftrightarrow \{ z\in \mathbb{R}^{m}|A^{\top}z=0,b^{\top}z=-1,z\geq0 \}$ OR formally ![[Pasted image 20251114115652.png]]