Matrices and System of Linear Equations

Let $a_x$ be scalars. We can view a sequence or array $S=\langle a_1,\ldots,a_n\rangle$ as a function $f_S:\{1,\ldots,n\}\mapsto F$ where $f_S(i)=a_i$. Similarly a matrix, $M$ is a 2$d$ array which can be seen as a $f_M:\{1,\ldots,m\}\times\{1,\ldots,n\}\mapsto F$ where $f_M(i,j)=a_{i,j}$.

We define product of matrix $A$ and $B$ as follows $$C=AB\coloneqq C_{ij}=\sum^n_{r=1}A_{ir}B_{rj}$$ This definition does not look interesting by itself. We need an application to appreciate its definition and that application comes along with the matrices in representing linear transformation of vector spaces.

Let’s say we have a system of $m$ linear equation in $n$ variables:

$$e_i:\sum_{j=1}^nc_{i,j}x_j=0$$ where $e_i$ is the $i^\text{th}$ equation and $i\in\set{1,\ldots,m}$.

We can rewrite this equation in matrix form as follows

$$ \begin{align*} &\begin{pmatrix}\sum_{i=1}^na_{1,i}x_i\\\vdots\\\sum_{i=1}^na_{m,i}x_i\end{pmatrix}=\begin{pmatrix}0\\\vdots\\0\end{pmatrix}\\[2em] \implies&\begin{pmatrix}a_{1,1}&\cdots&a_{1,n}\\\vdots&\ddots&\vdots\\a_{m,1}&\cdots&a_{m,n}\end{pmatrix}\begin{pmatrix}x_1\\\vdots\\x_n\end{pmatrix}=\begin{pmatrix}0\\\vdots\\0\end{pmatrix}\\[2em] \implies&AX=0 \end{align*} $$

Elementary Row Operations

There are three elementary row operations:

  1. Row switching: $R_i\leftrightarrow R_j$
  2. Row multiplication: $R_i\rightarrow cR_i$
  3. Row addition: $R_i\rightarrow R_i+cR_j$

In $AX=0$, we can juxtapose $A$ and $X$ to create a new augmented matrix $A\mid X$

$$ \begin{pmatrix}a_{1,1}&\cdots&a_{1,n}&x_1\\\vdots&\ddots&\vdots&\vdots\\a_{m,1}&\cdots&a_{m,n}&x_n\end{pmatrix} $$

$A$ and $B$ are row equivalent if $A$ can be obtained from $B$ with finite elementary row operations. Note that applying these operations on the augmented matrix does not change the solution space of the system of linear equation.

Row Reduced Echelon Form

We want to use elementary row operations to simplify our matrix to solve $AX=0$. We can reduce $A$ into following two forms:

Row Reduced Form

  1. First non-zero entry in each row is 1.
  2. If $a_{ij}$ is the first non-zero entry of $R_i$ then $\forall\ k\ne j\ a_{ik}=0$

Row Reduced Echelon Form

  1. It is in row reduced form
  2. Rows with all zero entries come after rows with non zero entries
  3. If first non zero entry of each non zero row $i$ is $k_i$, then $i<j\longleftrightarrow k_i< k_j$

Every matrix $A$ is reducible to a row reduced echelon form. Every row equivalent matrix to $A$ reduces to that same echelon form.

Row Rank

We can consider $A_{m\times n}$ a collection of row vectors $\langle \alpha_{i\in m}\rangle$. Row space is the subspace of $F^n$ spanned by these vectors. Row Rank is the dimension of this row space.

The non zero rows in row reduced echelon form constructs a basis for its row space. Elementary row operation does not change the row space of a matrix.

Linear Transformation

A linear transformation is a function, $T:V\mapsto W$ that satisfies $T(c\alpha+\beta)=c(T\alpha)+T\beta$

Null space of $T$ is subset of $V$ that maps to $0$ in $W$. Rank of $T$ is the dimension of range of T and nullity of $T$ is the dimension of its null space.

Since null space is a subspace of $V$, it must be spanned by a set of independent vectors $\set{\alpha_1,\ldots\alpha_r}$ where $r$ is the nullity of $T$. One can extend this set to $\set{\alpha_1,\ldots\alpha_n}$ to span the entire $V$, where $n=\mathrm{dim}\ V$. The vectors $\set{\alpha_{r+1},\ldots,\alpha_n}$ then spans the range of $T$ on applying $T$.

$$\mathrm{rank}\ T+\mathrm{nullity}\ T=\mathrm{dim}\ T$$

Matrix as Linear Transformation

We can treat the space of linear transformation from $V$ to $W$ as a vector space $L(V,W)$ using following rules:

  1. Vector Addition: $(T+U)\alpha=T\alpha+U\alpha$
  2. Scalar Multiplication: $(cT)\alpha=c(T\alpha)$