01. Linear System and Matrices

---

1.1 Systems of linear equations

Linear System (of equations)

Set of $m$ simultaneous equations in $n$ real variables $x_1,x_2,\cdots ,x_n$ that can be written as

$$\begin{array}{rlrlrlrl}{a}_{11}& x_1+a_{12}& & x_2+\cdots +a_{1n}& & x_n=& & b_1;\\ a_{21}& x_1+a_{22}& & x_2+\cdots +a_{2n}& & x_n=& & b_2;\\ & ⋮& & ⋮& & ⋮& & \\ a_{m1}& x_1+a_{m2}& & x_2+\cdots +a_{mn}& & x_n=& & b_m;\end{array}$$

with $a_{ij},b_i\in \mathbb{R}$

Link to original

Terminology

• Solution: Any vector $(x_1,x_2,\cdots ,x_n)$ that satisfies the Linear System
• General Solution: Any description of all the solutions of the system
• Consistent - If there are one or more solutions
• Augmented Matrix - Written as $(A\mid \mathbf{b})$

Link to original

Augmented Matrix

$$(A\mid \mathbf{b})=\left(\begin{array}{ccccc}{a}_{11}& a_{12}& \cdots & a_{1n}& b_1\\ a_{21}& a_{22}& \cdots & a_{2n}& b_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}& b_m\end{array}\right)$$

Link to original

Linear Systems can have none, one or $\infty$ solutions

Link to original

Elementary Row Operations (given a linear system)

Brackets is when applying it to a matrix (e.g. an Augmented Matrix)

1. Swapping the order of two equations (or rows)
2. Multiplying an equation (or row) by a non-zero scalar
3. Adding a multiple of one equation (or row) to another equation (or row)

Link to original

Notation when applying it to matrices (or equations)

1. Row Swap: Swap two rows ( $R_i\leftrightarrow R_j$ )
   → Notation: $S_{ij}$

2. Row Scaling: Multiply a row by a nonzero scalar ( $\lambda$ )
   → Notation: $M_i(\lambda )$, where ( $R_i\to \lambda R_i$ )

3. Row Addition: Add a multiple of one row to another
   → Notation: $A_{ij}(\lambda )$, where ( $R_j\to R_j+\lambda R_i$)

Not standard notation but convenient to use, $R_i$ refers to the $i^{th}$ row

Link to original

---

1.2 Matrices and matrix algebra

Matrix

Two-dimensional array of numbers

Link to original

$m\times n$ matrix

Array of numbers arranged in $m$ rows and $n$ columns

Link to original

Entries of a $m\times n$ matrix $A$

Generally

$$A=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right)$$

Entry in the $i$th row and $j$th column
→ Notation: $a_{ij}$ ($1\le i\le m$ and $1\le j\le n$)

Then we can write

$$A=(a_{ij})$$

Link to original

Rows and Columns of matrix $A$

$$i\text{th row}=(a_{i_1},a_{i_2},\cdots ,a_{in})$$ $$j\text{th column}=\left(\begin{array}{c}{a}_{1j}\\ a_{2j}\\ ⋮\\ a_{mj}\end{array}\right)$$

Link to original

Matrix Notation

• $M_{mn}$: Set of real $m\times n$ matrices
• $M_{1n}={\mathbb{R}}^n$: Set of real $n-$row vectors
• $M_{n_1}={\mathbb{R}}_{\mathrm{col}}^n$: Set of real $n$-column vectors

Link to original

Matrix Addition

Let $A=(a_{ij})$ and $B=(b_{ij})$ be $m\times n$ matrices

$C=A+B=(c_{ij})$ such that

$$c_{ij}=a_{ij}+b_{ij}$$

for $1\le i\le m$ and $1\le j\le n$

Requires matrices of the same size

Link to original

General Operation Identities for Matrix Addition and Scalar Multiplication

Let $A,B,C$ be $m\times n$ matrices and $\lambda ,\mu \in \mathbb{R}$

$$\begin{array}{rlrlrlrlrlrl}& A+0_{mn}& & =A;& & A+B& & =B+A;& & 0A& & =0_{mn}\\ & A+(-A)& & =0_{mn};& & (A+B)+C& & =A+(B+C);& & 1A& & =A\\ & (\lambda +\mu )A& & =\lambda A+\mu A;& & \lambda (A+B)& & =\lambda A+\lambda B;& & \lambda (\mu A)& & =(\lambda \mu )A\end{array}$$

These show that $M_{mn}$ is a real vector space

Link to original

Zero Matrix $0_{mn}=(0_{ij})$ ($m\times n$)

Entry $0_{ij}=0$ for $1\le i\le m,1\le j\le n$

Usually $0_{mn}$ is just represented as $0$

Link to original

Scalar Multiplication

Let $A=(a_{ij})$ be a $m\times n$ matrix and $k\in \mathbb{R}$

$B=kA=(b_{ij})$ such that

$$b_{ij}=k{a}_{ij}$$

for $1\le i\le m$ and $1\le j\le n$

Link to original

General Operation Identities for Matrix Addition and Scalar Multiplication

Let $A,B,C$ be $m\times n$ matrices and $\lambda ,\mu \in \mathbb{R}$

$$\begin{array}{rlrlrlrlrlrl}& A+0_{mn}& & =A;& & A+B& & =B+A;& & 0A& & =0_{mn}\\ & A+(-A)& & =0_{mn};& & (A+B)+C& & =A+(B+C);& & 1A& & =A\\ & (\lambda +\mu )A& & =\lambda A+\mu A;& & \lambda (A+B)& & =\lambda A+\lambda B;& & \lambda (\mu A)& & =(\lambda \mu )A\end{array}$$

These show that $M_{mn}$ is a real vector space

Link to original

Matrix Multiplication

Let $A=(a_{ij})$ be a $m\times n$ matrix and $B=(b_{ij})$ be a $n\times p$ matrix

$C=AB=(c_{ij})$ is $m\times p$ matrix such that

$$c_{ij}=\sum _{k=1}^n{a}_{ik}{b}_{kj}$$

for $1\le i\le m$ and $1\le j\le p$

Require number of columns of matrix $A$ to be equal to number of rows of matrix $B$

Link to original

Application of Left Multiplication Map to $A,B$

$$L_A\text{ from }{\mathbb{R}}_{\mathrm{col}}^n\text{ to }{\mathbb{R}}_{\mathrm{col}}^m,L_B\text{ from }{\mathbb{R}}_{\mathrm{col}}^p\text{ to }{\mathbb{R}}_{\mathrm{col}}^n,L_{AB}\text{ from }{\mathbb{R}}_{\mathrm{col}}^n\text{ to }{\mathbb{R}}_{\mathrm{col}}^p$$

With

$$L_{AB}=L_A\circ L_B$$

As $(AB)\mathbf{v}=A(B\mathbf{v})$

The $\circ$ is for composition

Link to original

Identity matrix $I_n$ ($n\times n$)

$(i,j)$th entry of $I={\delta }_{ij}$
where ${\delta }_{ij}$ is the Kronecker Delta

Usually $I_n$ is just represented as $I$ and it’s just ones on the main diagonal

Link to original

Sifting Property of the Kronecker Delta

Let $x_1,x_2,\cdots ,x_n$ be $n$ real numbers
Then for $1\le k\le n$

$$\sum _{i=1}^n{x}_i{\delta }_{ik}=x_k$$

Allows you to select (sift) the $k$th element from a list of numbers

Link to original

Properties of Matrix Multiplication

1. Let $A$ be a $m\times n$ matrix and $l,p\in \mathbb{N}\setminus \{0\}$

$$A{0}_{np}=0_{mp};0_{lm}A=0_{\ln };A{I}_n=A;I_{m}A=A$$

2. Matrix Multiplication is NOT commutative
3. Matrix Multiplication is associative
4. Matrix Multiplication is distributive under matrix addition

$$A(B+C)=AB+AC,\text{and}(A+B)C=AC+BC$$

5. If $MN=0$ then it is not necessarily true that either $M$ or $N$ are 0

Proof (Short - Not detailed)

1. Use matrix multiplication definition and sifting property for the identity ones
2. Counterexample (just think of $2\times 2$)
3. Go through double summation from definition
4. Go through double summation from definition
5. Counterexample (just think of $2\times 2$)

Link to original

Pre-multiplication and Post-multiplication

Let $A,M$ be matrices

• Pre-multiply $M$ by $A$: $AM$
• Post-multiply $M$ by $A$: $MA$

Link to original

Pre-multiplication and Post-multiplication

Let $A,M$ be matrices

• Pre-multiply $M$ by $A$: $AM$
• Post-multiply $M$ by $A$: $MA$

Link to original

Inverses

$$B\text{ is an inverse of }A⟺BA=AB=I$$

Link to original

Invertible vs Singular ( $A$)

• Invertible: Exists matrix $B$ s.t. $B$ is the inverse of $A$
• Singular: There doesn’t exist an inverse of $A$

Link to original

Properties of Inverses

1. Uniqueness: If a square matrix $A$ has an inverse then it is unique
   → Notation: $A^{-1}$

2. Product Rule: If $A,B$ are invertible $n\times n$ matrices then $AB$ is invertible with $(AB{)}^{-1}=B^{-1}{A}^{-1}$

3. Involution Rule: If $A$ is invertible then $A^{-1}$ is invertible with $(A^{-1}{)}^{-1}=A$

Proof

1. Let $B,C$ be inverses of $A$ then

$$C=IC=(BA)C=B(AC)=BI=B$$

2. Let $B$ be the inverse of $A$ then

$$(AB{)}^{-1}(AB)=I⟹(AB{)}^{-1}(AB)(B^{-1}{A}^{-1})=I{B}^{-1}{A}^{-1}⟹(AB{)}^{-1}=B^{-1}{A}^{-1}$$

3. Consider

$$(A^{-1})A=A(A^{-1})=I$$

So by definition $(A^{-1}{)}^{-1}=A$ by 1)

Link to original

Left and Right Inverses

• Left Inverse $B$ of $A$: $BA=I$
• Right Inverse $C$ of $A$: $AC=I$

Link to original

If $A$ is non-square then $A$ cannot have both left and right inverses

Link to original

If $A$ is square then any left or right inverse is also the other inverse!

Link to original

Inverses of $2\times 2$ matrices

Let

$$A=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$$

Iff $ad-bc\ne 0$ then

$$A^{-1}=\frac{1}{ad-bc}\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$$

$ad-bc$ is commonly referred to as the determinant of $A$ ($detA$)

Link to original

General Commutative Matrix

Let $A$ be an $n\times n$ matrix such that $AM=MA$ for all $n\times n$ matrices M (i.e. commutes with all $n\times n$ matrices)

Then $A=\lambda I_n$ for some $\lambda \in \mathbb{R}$

Proof - TODO

TODO: write up

Link to original

---

1.3 Reduced Row Echelon Form

Elementary Matrices

$$\begin{array}{rl}\text{the }(i,j)\text{th entry of }{S}_{IJ}& =\{\begin{array}{ll}1& \text{ if }i=j\ne I,J\\ 1& \text{ if }i=J,j=I\\ 1& \text{ if }i=I,j=J\\ 0& \text{ otherwise }\end{array}\\ & \\ \text{the }(i,j)\text{th entry of }{M}_I(\lambda )& =\{\begin{array}{ll}1& \text{ if }i=j\ne I\\ \lambda & \text{ if }i=j=I\\ 0& \text{ otherwise }\end{array}\\ & \\ \text{the }(i,j)\text{th entry of }{A}_{IJ}(\lambda )& =\{\begin{array}{ll}1& \text{ if }i=j\\ \lambda & \text{ if }i=J,j=I\\ 0& \text{ otherwise }\end{array}\end{array}$$

These elementary matrices can also be obtained by applying the respective ERO onto the identity matrix!

Link to original

Inverses of the Elementary Matrices

$$(S_{ij}{)}^{-1}=S_{ji}=S_{ij};(A_{ij}(\lambda ){)}^{-1}=A_{ij}(-\lambda );(M_i(\lambda ){)}^{-1}=M_i({\lambda }^{-1})$$

Link to original

Invariance of Solution Space under EROs corollary

Let $(A\mid \mathbf{b})$ be a linear system of $m$ equations and $E$ an $m\times m$ elementary matrix
Then

$$\mathbf{x}\text{ is a solution of }(A\mid \mathbf{b})⟺\mathbf{x}\text{ is a solution of }(EA\mid E\mathbf{b})$$

Proof

As $E$ is invertible then (by pre-multiplication of $E$)

$$A\mathbf{x}=\mathbf{b}⟹EA\mathbf{x}=E\mathbf{b}$$

And (by pre-multiplication of $E^{-1}$)

$$EA\mathbf{x}=E\mathbf{b}⟹A\mathbf{x}=\mathbf{b}$$

Link to original

Reduced Row Echelon Form of $A$

1. First non-zero entry of any non-zero row is $1$
2. Any column that contains a leading $1$, all other entries in the column are $0$
3. Leading $1$ of a non-zero row appears to the right of leading $1$s above it
4. Any zero rows appear below the non-zero rows

Link to original

Solving Systems in RRE Form

Let $(A\mid \mathbf{b})$ be a matrix in RRE form which represents $A\mathbf{x}=\mathbf{b}$ of $m$ equations in $n$ variables

1. No solutions iff last non-zero row of $(A\mid \mathbf{b})$ is

$$\left(\begin{array}{cccc}0& 0& \cdots & 0\mid 1\end{array}\right)$$

2. Unique solution iff non-zero rows of $(A\mid \mathbf{b})$ form the identity matrix $I_n$ (requires $m\ge n$)

3. Infinitely many solutions

Proof - TODO

Link to original

Existence of RRE Form

Every $m\times n$ matrix $A$ can be reduced by EROs to a matrix in RRE form

Proof - Use Lecture Notes

Link to original