1.Orthogonal projectors and linear systems

Consider the linear system $𝑨𝒙=𝒃$ with $𝑨\in {ℝ}^{m\times n}$, $𝒃\in {ℝ}^m$ given. The scaling coefficients $𝒙\in {ℝ}^n$ are sought and are said to be a solution of the linear system when the equation $𝑨𝒙=𝒃$ is satisfied. Orthogonal projectors and knowledge of the four fundamental matrix subspaces allows us to succintly express whether there exist no solutions, a single solution of an infinite number of solutions:

• Consider the factorization $𝑸𝑹=𝑨$, the orthogonal projector $𝑷=𝑸{𝑸}^T$, and the complementary orthogonal projector $𝑰-𝑷$

• If $||(𝑰-𝑷)𝒃||\ne 0$, then $𝒃$ has a component outside the column space of $𝑨$, and $𝑨𝒙=𝒃$ has no solution

• If $||(𝑰-𝑷)𝒃||=0$, then $𝒃\in C\left(𝑸\right)=C\left(𝑨\right)$ and the system has at least one solution

• If $N\left(𝑨\right)=\left\{𝟎\right\}$ (null space only contains the zero vector, i.e., null space of dimension 0) the system has a unique solution

• If $\dim N\left(𝑨\right)=n-r>0$, then a vector $𝒚\in N\left(𝑨\right)$ in the null space is written as

  ${\displaystyle 𝒚=c_1{𝒛}_1+\dots +c_{n-r}{𝒛}_{n-r}}$

  and if $𝒙$ is a solution of $𝑨𝒙=𝒃$, so is $𝒙+𝒚$, since

  ${\displaystyle 𝑨(𝒙+𝒚)=𝑨𝒙+c_1𝑨{𝒛}_1+\dots +c_{n-r}𝑨{𝒛}_{n-r}=𝒃+𝟎+\dots +𝟎=𝒃}$

  The linear system has an $(n-r)$-parameter family of solutions

If a solution exists, it can be found by backsubstitution solution of $𝑹𝒙={𝑸}^T𝒃$. If multiple solutions exist, an orthonormal basis $𝒁$ is found for the null space and the family of solutions is $𝒙+𝒁𝒚$.

2.Gaussian elimination and row echelon reduction

Suppose now that $𝑨𝒙=𝒃$ admits a unique solution. The $QR$ factorization approach of reducing the problem to $𝑹𝒙={𝑸}^T𝒃$ is one procedure to compute the solution. It has the benefit of working with the orthonormal $𝑸$ matrix. Finding the orthonormal $𝑸$ matrix is however a computational expense. Recall that orthogonality implied linear independence. Other approaches might exist that only impose linear independence, without orthogonality. Gaussian elimination is the main such approach. Consider the system

The idea is to combine equations such that we have one fewer unknown in each equation. Ask: with what number should the first equation be multiplied in order to eliminate $x_1$ from sum of equation 1 and equation 2? This number is called a Gaussian multiplier, and is in this case $-2$. Repeat the question for eliminating $x_1$ from third equation, with multiplier $-3$.

Now, ask: with what number should the second equation be multiplied to eliminate $x_2$ from sum of second and third equations. The multiplier is in this case $-7/5$.

Starting from the last equation we can now find $x_3=1$, replace in the second to obtain $-5x_2=-5$, hence $x_2=1$, and finally replace in the first equation to obtain $x_1=1$.

The above operations only involve coefficients. A more compact notation is therefore to work with what is known as the "bordered matrix" and work with coefficients arising in rows

In Julia the above operations would be carried out as

∴ 

A=[1. 2 -1 2; 2 -1 1 2; 3 -1 -1 1]; A[2,:]=A[2,:]-2*A[1,:]; A[3,:]=A[3,:]-3*A[1,:]; 

∴ 

A

∴ 

A[3,:]=A[3,:]-(7/5)*A[2,:]; A

∴ 

Once the above triangular form has been obtained, the solution is found by back substitution, in which we seek to form the identity matrix in the first 3 columns, and the solution is obtained in the last column.

The operations arising in Gaussian elimination are successive linear combinations of rows that maintain the solution of the linear system. This idea is useful in identifying the fundamental subspaces associated with a matrix. The matrices arising at successive stages of the procedure are said to be similar to one another

and since ${𝑨}_k$ is obtained by linear combination of the rows of ${𝑨}_{k-1}$, the row space is not changed

During the procedure a pivot element is identified in the diagonal position, as shown bordered above. If a zero value is encountered rows are permuted to bring a non-zero element to the pivot position. If a non-zero pivot value cannot be found by row permutation, one is sought by column permutations also. If a non-zero pivot cannot be found by either row or column permutations, the matrix is rank-deficient $r=\mathrm{rank}\left(𝑨\right)<min(m,n)$ and has a non-trivial null space as in the following examples

The $𝑨𝒙=𝒃$ has an infinite number of solutions, while the $𝑨𝒙=𝒄$ system has no solutions. Note that ${𝑨}_1$ has a row of zeros, hence the rows must be linearly dependent and $N\left(𝑨\right)\ne \left\{𝟎\right\}$. By the FTLA when $𝒃\in C\left(𝑨\right)$ an infinite number of solutions is obtained, and for $𝒄\notin C\left(𝑨\right)$ no solutions are obtained.

The rows with non-zero pivot elements are linearly independent, and reduction to the above row-echelon form is useful to identify the rank of a matrix. The first non-zero entry on a row is called either a pivot or a leading entry. A matrix is said to be brought to reduced row-echelon form when:

• all zero rows are below non-zero rows;

• in each non-zero row, the leading entry is to the left of lower leading entries;

• each leading entry equals 1 and is the only non-zero entry in its column.

In contrast to the Gram-Schmidt procedure, Gaussian elimination does not impose orthogonality between rows, nor that a row have unit norm. This leads to fewer computations, and is therefore well-suited to hand computation of small-dimensional matrices.

Algorithm Gauss elimination without pivoting

for $s=1$ to $m-1$

for $i=s+1$ to $m$

$t=-a_{is}/a_{ss}$

for $j=s+1$ to $m$

$a_{ij}=a_{ij}+t\cdot a_{sj}$

$b_i=b_i+t\cdot b_s$

for $s=m$ downto 1

$x_s=b_s/a_{ss}$

for $i=1$ to $s-1$

$b_i=b_i-a_{is}\cdot x_s$

Algorithm Gauss elimination with partial pivoting

$p=1:m$ (initialize row permutation vector)

for $s=1$ to $m-1$

piv = $\mathrm{abs}\left(a_{p\left(s\right),s}\right)$

for $i=s+1$ to $m$

mag = $\mathrm{abs}\left(a_{p\left(i\right),s}\right)$

if $\mathrm{mag}>\mathrm{piv}$ then

$\mathrm{piv}=\mathrm{mag};k=p\left(s\right);p\left(s\right)=p\left(i\right);p\left(i\right)=k$

if $\mathrm{piv}<ϵ$ then break(“Singular matrix”)

$t=-a_{p\left(i\right)s}/a_{p\left(s\right)s}$

for $j=s+1$ to $m$

$a_{p\left(i\right)j}=a_{p\left(i\right)j}+t\cdot a_{p\left(s\right)j}$

$b_{p\left(i\right)}=b_{p\left(i\right)}+t\cdot b_{p\left(s\right)}$

for $s=m$ downto 1

$x_s=b_{p\left(s\right)}/a_{p\left(s\right)s}$

for $i=1$ to $s-1$

$b_{p\left(i\right)}=b_{p\left(i\right)}-a_{p\left(i\right)s}\cdot x_s$

1. $𝑨$ invertible

2. $𝑨𝒙=𝒃$ has a unique solution for all $𝒃\in {ℝ}^m$

3. $𝑨𝒙=𝟎$ has a unique solution

4. The reduced row echelon form of $𝑨$ is $𝑰$

5. $𝑨$ can be written as product of elementary matrices