8 Matrix Inverse and Linear Independence

8.1 The Inverse of a Matrix

Identity Matrix: The n\times n identity matrix {\bf I}_n is the matrix whose diagonal elements are 1 and all off-diagonal elements are 0. Examples: {\bf I}_2=\begin{bmatrix} 1&0\\0&1 \end{bmatrix}, \qquad {\bf I}_3=\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&0&1 \end{bmatrix}

Inverse Matrix: An n\times n matrix {\bf A} is nonsingular or invertible if there exists an n\times n matrix {\bf A}^{-1} such that {\bf A} {\bf A}^{-1} = {\bf A}^{-1} {\bf A} = {\bf I}_n where {\bf A}^{-1} is the inverse of {\bf A}. If there is no such {\bf A}^{-1}, then {\bf A} is singular or not invertible.

Example: Let {\bf A} = \begin{bmatrix} 2&3\\2&2 \end{bmatrix}, \qquad {\bf B}=\begin{bmatrix} -1&\frac{3}{2}\\ 1&-1 \end{bmatrix} Since {\bf A} {\bf B} = {\bf B} {\bf A} = {\bf I}_n we conclude that {\bf B} is the inverse, {\bf A}^{-1}, of {\bf A} and that {\bf A} is nonsingular.

Properties of the Inverse:

If the inverse exists, it is unique.
If {\bf A} is nonsingular, then {\bf A}^{-1} is nonsingular.
({\bf A}^{-1})^{-1} = {\bf A}
If {\bf A} and {\bf B} are nonsingular, then {\bf A}{\bf B} is nonsingular
({\bf A}{\bf B})^{-1} = {\bf B}^{-1}{\bf A}^{-1}
If {\bf A} is nonsingular, then ({\bf A}^\top)^{-1}=({\bf A}^{-1})^\top

Procedure to Find {\bf A}^{-1}: We know that if {\bf B} is the inverse of {\bf A}, then {\bf A} {\bf B} = {\bf B} {\bf A} = {\bf I}_n Looking only at the first and last parts of this {\bf A} {\bf B} = {\bf I}_n Solving for {\bf B} is equivalent to solving for n linear systems, where each column of {\bf B} is solved for the corresponding column in {\bf I}_n. We can solve the systems simultaneously by augmenting {\bf A} with {\bf I}_n and performing Gauss-Jordan elimination on {\bf A}. If Gauss-Jordan elimination on [{\bf A} | {\bf I}_n] results in [{\bf I}_n | {\bf B} ], then {\bf B} is the inverse of {\bf A}. Otherwise, {\bf A} is singular.

To summarize: To calculate the inverse of {\bf A}

Form the augmented matrix [ {\bf A} | {\bf I}_n]
Using elementary row operations, transform the augmented matrix to reduced row echelon form.
The result of step 2 is an augmented matrix [ {\bf C} | {\bf B} ].
1. If {\bf C}={\bf I}_n, then {\bf B}={\bf A}^{-1}.
2. If {\bf C}\ne{\bf I}_n, then \bf C has a row of zeros. This means {\bf A} is singular and {\bf A}^{-1} does not exist.

Example 8.1 Find the inverse of the following matrix:

{\bf A}=\begin{bmatrix} 1&1&1\\0&2&3\\5&5&1 \end{bmatrix}

Exercise 8.1 Find the inverse of the following matrix:

{\bf A}=\begin{bmatrix} 1&0&4\\0&2&0\\0&0&1 \end{bmatrix}

8.2 Linear Systems and Inverse

Let’s return to the matrix representation of a linear system

\bf{Ax} = \bf{b}

If \bf{A} is an n\times n matrix,then \bf{Ax}=\bf{b} is a system of n equations in n unknowns. Suppose \bf{A} is nonsingular. Then \bf{A}^{-1} exists. To solve this system, we can multiply each side by \bf{A}^{-1} and reduce it as follows: \begin{align*} \bf{A}^{-1} (\bf{A} \bf{x}) & = \bf{A}^{-1} \bf{b} \\ (\bf{A}^{-1} \bf{A})\bf{x} & = \bf{A}^{-1} \bf{b}\\ \bf{I}_n \bf{x} & = \bf{A}^{-1} \bf{b}\\ \bf{x} & = \bf{A}^{-1} \bf{b} \end{align*}

Hence, given \bf{A} and \bf{b} and given that \bf{A} is nonsingular, then \bf{x} = \bf{A}^{-1} \bf{b} is a unique solution to this system.

Exercise 8.2 Use the inverse matrix to solve the following linear system:

\begin{align*} -3x + 4y &= 5 \\ 2x - y &= -10 \end{align*}

Hint: the linear system above can be written in the matrix form

\textbf{A}\textbf{z} = \textbf{b}

given

\textbf{A} = \begin{bmatrix} -3&4\\2&-1 \end{bmatrix},

\textbf{z} = \begin{bmatrix} x\\y \end{bmatrix},

and

\textbf{b} = \begin{bmatrix} 5\\-10 \end{bmatrix}

8.3 When is Matrix Invertible?

The following statements for an n\times n square matrix \mathbf{A} are equivalent:

\mathbf{A} is invertible: \mathbf{A}^{-1} \textrm{ exists and } \mathbf{A}^{-1}\mathbf{A}=\mathbf{I}_n
The system \mathbf{A}\mathbf{x} = \mathbf{b} has a unique solution for all \mathbf{b}\neq\mathbf{0} (zero vector)
If \mathbf{A}\mathbf{x} = \mathbf{0} (zero vector), it implies that \mathbf{x} = \mathbf{0} (zero vector)
The column vectors in \mathbf{A} are linearly independent and spans \mathbb{R}^n
The rank of \mathbf{A} is n: \mathrm{rank}(\mathbf{A})=n
The determinant of \mathbf{A} is not zero: \det(\mathbf{A}) \neq 0

Conceptually, we want columns of \mathbf{A} contains enough vectors to reach all coordinates (span) \mathbb{R}^n.
However, when we include too many vectors, we will have redundant vectors when the new vectors does not provide new information (you can already express the new vectors using the existing vectors) and so the vectors become linearly dependent

8.4 Linear Independence

Linear Dependence: A set of vectors \{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n\} is linearly dependent if some vector \mathbf{v}_i is a linear combination of the other vectors \mathbf{v}_j

If all vectors cannot be written as linear combinations of the other vectors, then the set of vectors are linearly independent

\mathbf{v}_i is not a linear combination of the other vectors \mathbf{v}_j, i.e.,

{\color{red}\mathbf{v}_i} \neq \sum_{j\neq i} c_j \mathbf{v}_j = \underbrace{c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots + c_n \mathbf{v}_n}_{\textrm{linear combination {\color{red}excluding} } {\color{red}\mathbf{v}_i}} \;\;\;\;\;\; \textrm{ for all } i

Subtracting \mathbf{v}_i, this is equivalent to

\underbrace{\mathbf{0}}_{\textrm{zero vector!}} \neq {\color{red} - \mathbf{v}_i} + \sum_{j\neq i} c_j \mathbf{v}_j = \underbrace{c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots + {\color{red} (-1) \mathbf{v}_i} + \cdots + c_n \mathbf{v}_n}_{\textrm{linear combination of } \mathbf{v}_1, \mathbf{v}_2, \ldots, {\color{red} \mathbf{v}_i}, \ldots, \mathbf{v}_n} \;\; \textrm{ for all } i.

This is equivalent to saying: The only solution to

\underbrace{\mathbf{0}}_{\textrm{zero vector!}} = \underbrace{c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots + \mathbf{v}_i + \cdots + c_n \mathbf{v}_n}_{\textrm{linear combination of } \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_i, \ldots, \mathbf{v}_n}

is c_1 = c_2 = \cdots = c_n = 0.

This is equivalent to the statement that \mathbf{A}\mathbf{x} = \mathbf{0} implies \mathbf{x} = \mathbf{0}.

Linear independence: A set of vectors {\bf v}_1, {\bf v}_2, \cdots , {\bf v}_k is linearly independent if the only solution to the equation

c_1{\bf v}_1 + c_2{\bf v}_2 + \cdots + c_k{\bf v}_k = 0

is c_1 = c_2 = \cdots = c_k = 0. If another solution exists, the set of vectors is linearly dependent.

A set S of vectors is linearly dependent if and only if at least one of the vectors in S can be written as a linear combination of the other vectors in S.

Linear independence is only defined for sets of vectors with the same number of elements; any linearly independent set of vectors in n-space contains at most n vectors.

Since \begin{bmatrix}9 \\ 13 \\ 17 \end{bmatrix} is a linear combination of \begin{bmatrix}1 \\ 2 \\ 3 \end{bmatrix}, \begin{bmatrix} 2 \\ 3\\ 4\end{bmatrix}, and \begin{bmatrix} 3 \\ 4 \\ 5 \end{bmatrix}, these 4 vectors constitute a linearly dependent set.

Example 8.2 Are the following sets of vectors linearly independent?

\begin{bmatrix}2 \\ 3 \\ 1 \end{bmatrix} and \begin{bmatrix}4 \\ 6 \\ 1 \end{bmatrix}
\begin{bmatrix}1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix}0 \\ 5 \\ 0 \end{bmatrix}, and \begin{bmatrix}10 \\ 10 \\ 0 \end{bmatrix}

Exercise 8.3 Are the following sets of vectors linearly independent?

{\bf v}_1 = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} , {\bf v}_2 = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} , {\bf v}_3 = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}
{\bf v}_1 = \begin{bmatrix} 2 \\ 2 \\ 1 \end{bmatrix} , {\bf v}_2 = \begin{bmatrix} -4 \\ 6 \\ 5 \end{bmatrix} , {\bf v}_3 = \begin{bmatrix} -2 \\ 8 \\ 6 \end{bmatrix}

8.5 Rank of a Matrix

Another way to think about linear independence is to consider the rank of a matrix.

Rank: The rank of a matrix is the number of linearly independent rows or columns in the matrix. The rank of a matrix is denoted by \textrm{rank}(\mathbf{A}).

For example \begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{bmatrix}

Rank = 3

\begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 0 \end{bmatrix}

Rank = 2

Exercise 8.4 Find the rank of each matrix below:

(Hint: transform the matrices into row echelon form. Remember that the number of nonzero rows of a matrix in row echelon form is the rank of that matrix)

\begin{bmatrix} 1 & 1 & 2 \\ 2 & 1 & 3 \\ 1 & 2 & 3 \end{bmatrix}
\begin{bmatrix} 1 & 3 & 3 & -3 & 3\\ 1 & 3 & 1 & 1 & 3 \\ 1 & 3 & 2 & -1 & -2 \\ 1 & 3 & 0 & 3 & -2 \end{bmatrix}

Answer to Exercise 8.4:

rank is 2
rank is 3

8.6 Determinants

Singularity: Determinants can be used to determine whether a square matrix is nonsingular.

A square matrix is nonsingular if and only if its determinant is not zero.

Determinant of a 1 \times 1 matrix, equals |\mathbf{A}|=|a_{11}|=a_{11}

Determinant of a 2 \times 2 matrix,

\mathbf{A}=\begin{vmatrix} a_{11}&a_{12}\\ a_{21}&a_{22} \end{vmatrix}

\begin{align*}\det({\bf A}) &= |{\bf A}|\\ &= a_{11}|a_{22}| - a_{12}|a_{21}|\\ &= a_{11}a_{22} - a_{12}a_{21} \end{align*}

We can extend the second to last equation above to get the definition of the determinant of a 3 \times 3 matrix: \begin{align*} \begin{vmatrix} a_{11}&a_{12}&a_{13}\\ a_{21} & a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33} \end{vmatrix} &= a_{11} \begin{vmatrix} a_{22}&a_{23}\\ a_{32}&a_{33} \end{vmatrix} - a_{12} \begin{vmatrix} a_{21}&a_{23}\\ a_{31}&a_{33} \end{vmatrix} + a_{13} \begin{vmatrix} a_{21}&a_{22}\\ a_{31}&a_{32} \end{vmatrix}\\ &= a_{11}(a_{22}a_{33} - a_{23}a_{32}) - a_{12}(a_{21}a_{33} - a_{23}a_{31}) + a_{13}(a_{21}a_{32} - a_{22}a_{31}) \end{align*}

Let’s extend this now to any n\times n matrix. Let’s define \mathbf{A}_{ij} as the (n-1)\times (n-1) submatrix of \mathbf{A} obtained by deleting row i and column j. Let the (i,j)th minor of \mathbf{A} be the determinant of \mathbf{A}_{ij}:

M_{ij} = \left|\mathbf{A}_{ij}\right|

Then for any n\times n matrix \mathbf{A}

|\mathbf{A}| = a_{11}M_{11} - a_{12}M_{12} + \cdots + (-1)^{n+1} a_{1n} M_{1n}

For example, in figuring out whether the following matrix has an inverse?

\mathbf{A}=\begin{bmatrix} 1&1&1\\0&2&3\\5&5&1 \end{bmatrix}

Calculate its determinant. \begin{align*} |\mathbf{A}| &= 1(2-15) - 1(0-15) + 1(0-10) \nonumber\\ &= -13+15-10 \nonumber\\ &= -8\nonumber \end{align*}
Since |{\bf A}|\ne 0, we conclude that {\bf A} has an inverse.

Exercise 8.5 Determine whether the following matrices are nonsingular:

\begin{bmatrix} 1 & 0 & 1\\ 2 & 1 & 2\\ 1 & 0 & -1 \end{bmatrix}
\begin{bmatrix} 2 & 1 & 2\\ 1 & 0 & 1\\ 4 & 1 & 4 \end{bmatrix}

8.7 Getting Inverse of a Matrix using its Determinant

Thus far, we have a number of algorithms to

Find the solution of a linear system,
Find the inverse of a matrix

but these remain just that — algorithms. At this point, we have no way of telling how the solutions x_j change as the parameters a_{ij} and b_i change, except by changing the values and “rerunning” the algorithms.

With determinants, we can provide an explicit formula for the inverse and therefore provide an explicit formula for the solution of an n\times n linear system.

Hence, we can examine how changes in the parameters and b_i affect the solutions x_j.

Determinant Formula for the Inverse of a 2 \times 2:

The determinant of a 2 \times 2 matrix \mathbf{A}=\begin{bmatrix} a & b\\ c & d\\ \end{bmatrix} is defined as:

\det(\mathbf{A}) = a d - b c

The inverse of \mathbf{A} is given by:

\frac{1}{\det({\bf A})} \begin{bmatrix} d & -b \\ -c & a\\ \end{bmatrix}

For example, Let’s calculate the inverse of matrix A from Exercise 8.2 using the determinant formula.

Recall,

\mathbf{A} = \begin{bmatrix} -3 & 4\\ 2 & -1\\ \end{bmatrix}

\det(\mathbf{A}) = (-3)(-1) - (4)(2) = 3 - 8 = -5

\frac{1}{\det(\mathbf{A})} \begin{bmatrix} -1 & -4\\ -2 & -3\\ \end{bmatrix}

\frac{1}{-5} \begin{bmatrix} -1 & -4\\ -2 & -3\\ \end{bmatrix}

\begin{bmatrix} \frac{1}{5} & \frac{4}{5}\\ \frac{2}{5} & \frac{3}{5}\\ \end{bmatrix}

Exercise 8.6

Caculate the inverse of \mathbf{A} \mathbf{A} = \begin{bmatrix} 3 & 5\\ -7 & 2\\ \end{bmatrix}

Answers to Examples and Exercises

Answer to Example 8.2:

Answer to Exercise 8.3:

yes
no (-v_1 -v_2 + v_3 = 0)

Answer to Exercise 8.4:

rank is 2
rank is 3

Answer to Example 8.1:

\left(\begin{array}{ccc|ccc} 1&1&1&1&0&0\\ 0&2&3&0&1&0\\ 5&5&1&0&0&1 \end{array} \right)

\left(\begin{array}{ccc|ccc} 1&1&1 &1 &0&0\\ 0&2&3 &0 &1&0\\ 0&0&-4&-5&0&1 \end{array} \right)

\left(\begin{array}{ccc|ccc} 1&1&1&1 &0&0\\ 0&2&3&0 &1&0\\ 0&0&1&5/4&0&-1/4 \end{array} \right)

\left(\begin{array}{ccc|ccc} 1&1&0&-1/4 &0&1/4\\ 0&2&0&-15/4&1&3/4\\ 0&0&1&5/4 &0&-1/4 \end{array} \right)

\left(\begin{array}{ccc|ccc} 1&1&0&-1/4 &0 &1/4\\ 0&1&0&-15/8&1/2&3/8\\ 0&0&1&5/4 &0 &-1/4 \end{array} \right)

\left(\begin{array}{ccc|ccc} 1&0&0&13/8 &-1/2&-1/8\\ 0&1&0&-15/8&1/2 &3/8\\ 0&0&1&5/4 &0 &-1/4 \end{array} \right)

{\bf A}^{-1} = \left(\begin{array}{ccc} 13/8 &-1/2&-1/8\\ -15/8&1/2 &3/8\\ 5/4 &0 &-1/4 \end{array} \right)

Answer to Exercise 8.1:

{\bf A}^{-1}=\begin{bmatrix} 1&0&-4\\0&\frac{1}{2}&0\\0&0&1 \end{bmatrix}

Answer to Exercise 8.2:

\textbf{z} = \bf{A}^{-1} \bf{b} = \begin{bmatrix} 1/5 &4/5\\ 2/5&3/5 \end{bmatrix} \begin{bmatrix} 5 \\ -10 \end{bmatrix}= \begin{bmatrix} -7 \\ -4 \end{bmatrix} = \begin{bmatrix} x \\ y \end{bmatrix}

Answer to Exercise 8.5:

nonsingular
singular

Answer to Exercise 8.6:

\begin{bmatrix} \frac{2}{41} & \frac{-5}{41}\\ \frac{7}{41} & \frac{3}{41}\\ \end{bmatrix}

# Matrix Inverse and Linear Independence ## The Inverse of a Matrix __Identity Matrix__: The $n\times n$ identity matrix ${\bf I}_n$ is the matrix whose diagonal elements are 1 and all off-diagonal elements are 0. Examples: $$ {\bf I}_2=\begin{bmatrix} 1&0\\0&1 \end{bmatrix}, \qquad {\bf I}_3=\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&0&1 \end{bmatrix}$$ __Inverse Matrix__: An $n\times n$ matrix ${\bf A}$ is __nonsingular__ or __invertible__ if there exists an $n\times n$ matrix ${\bf A}^{-1}$ such that $${\bf A} {\bf A}^{-1} = {\bf A}^{-1} {\bf A} = {\bf I}_n$$ where ${\bf A}^{-1}$ is the inverse of ${\bf A}$. If there is no such ${\bf A}^{-1}$, then ${\bf A}$ is singular or not invertible. Example: Let $${\bf A} = \begin{bmatrix} 2&3\\2&2 \end{bmatrix}, \qquad {\bf B}=\begin{bmatrix} -1&\frac{3}{2}\\ 1&-1 \end{bmatrix}$$ Since $${\bf A} {\bf B} = {\bf B} {\bf A} = {\bf I}_n$$ we conclude that ${\bf B}$ is the inverse, ${\bf A}^{-1}$, of ${\bf A}$ and that ${\bf A}$ is nonsingular. __Properties of the Inverse__: - If the inverse exists, it is unique. - If ${\bf A}$ is nonsingular, then ${\bf A}^{-1}$ is nonsingular. - $({\bf A}^{-1})^{-1} = {\bf A}$ - If ${\bf A}$ and ${\bf B}$ are nonsingular, then ${\bf A}{\bf B}$ is nonsingular - $({\bf A}{\bf B})^{-1} = {\bf B}^{-1}{\bf A}^{-1}$ - If ${\bf A}$ is nonsingular, then $({\bf A}^\top)^{-1}=({\bf A}^{-1})^\top$ __Procedure to Find__ ${\bf A}^{-1}$: We know that if ${\bf B}$ is the inverse of ${\bf A}$, then $${\bf A} {\bf B} = {\bf B} {\bf A} = {\bf I}_n$$ Looking only at the first and last parts of this $${\bf A} {\bf B} = {\bf I}_n$$ Solving for ${\bf B}$ is equivalent to solving for $n$ linear systems, where each column of ${\bf B}$ is solved for the corresponding column in ${\bf I}_n$. We can solve the systems simultaneously by augmenting ${\bf A}$ with ${\bf I}_n$ and performing Gauss-Jordan elimination on ${\bf A}$. If Gauss-Jordan elimination on $[{\bf A} | {\bf I}_n]$ results in $[{\bf I}_n | {\bf B} ]$, then ${\bf B}$ is the inverse of ${\bf A}$. Otherwise, ${\bf A}$ is singular. To summarize: To calculate the inverse of ${\bf A}$ 1. Form the augmented matrix $[ {\bf A} | {\bf I}_n]$ 2. Using elementary row operations, transform the augmented matrix to reduced row echelon form. 3. The result of step 2 is an augmented matrix $[ {\bf C} | {\bf B} ]$. a. If ${\bf C}={\bf I}_n$, then ${\bf B}={\bf A}^{-1}$. b. If ${\bf C}\ne{\bf I}_n$, then $\bf C$ has a row of zeros. This means ${\bf A}$ is singular and ${\bf A}^{-1}$ does not exist. :::{#exm-inverse} Find the inverse of the following matrix: $${\bf A}=\begin{bmatrix} 1&1&1\\0&2&3\\5&5&1 \end{bmatrix}$$ ::: :::{#exr-inverse1} Find the inverse of the following matrix: $${\bf A}=\begin{bmatrix} 1&0&4\\0&2&0\\0&0&1 \end{bmatrix}$$ ::: ## Linear Systems and Inverse Let's return to the matrix representation of a linear system $$\bf{Ax} = \bf{b}$$ If $\bf{A}$ is an $n\times n$ matrix,then $\bf{Ax}=\bf{b}$ is a system of $n$ equations in $n$ unknowns. Suppose $\bf{A}$ is nonsingular. Then $\bf{A}^{-1}$ exists. To solve this system, we can multiply each side by $\bf{A}^{-1}$ and reduce it as follows: \begin{align*} \bf{A}^{-1} (\bf{A} \bf{x}) & = \bf{A}^{-1} \bf{b} \\ (\bf{A}^{-1} \bf{A})\bf{x} & = \bf{A}^{-1} \bf{b}\\ \bf{I}_n \bf{x} & = \bf{A}^{-1} \bf{b}\\ \bf{x} & = \bf{A}^{-1} \bf{b} \end{align*} Hence, given $\bf{A}$ and $\bf{b}$ and given that $\bf{A}$ is nonsingular, then $\bf{x} = \bf{A}^{-1} \bf{b}$ is a unique solution to this system. :::{#exr-invlinsys} Use the inverse matrix to solve the following linear system: \begin{align*} -3x + 4y &= 5 \\ 2x - y &= -10 \end{align*} **Hint**: the linear system above can be written in the matrix form $\textbf{A}\textbf{z} = \textbf{b}$ given $$\textbf{A} = \begin{bmatrix} -3&4\\2&-1 \end{bmatrix},$$ $$\textbf{z} = \begin{bmatrix} x\\y \end{bmatrix},$$ and $$\textbf{b} = \begin{bmatrix} 5\\-10 \end{bmatrix}$$ ::: ## When is Matrix Invertible? The following statements for an $n\times n$ square matrix $\mathbf{A}$ are **equivalent**: - $\mathbf{A}$ is **invertible**: $$ \mathbf{A}^{-1} \textrm{ exists and } \mathbf{A}^{-1}\mathbf{A}=\mathbf{I}_n $$ - The system $\mathbf{A}\mathbf{x} = \mathbf{b}$ has a **unique solution** for all $\mathbf{b}\neq\mathbf{0}$ (zero vector) - If $\mathbf{A}\mathbf{x} = \mathbf{0}$ (zero vector), it implies that $\mathbf{x} = \mathbf{0}$ (zero vector) - The column vectors in $\mathbf{A}$ are **linearly independent** and **spans** $\mathbb{R}^n$ - The **rank** of $\mathbf{A}$ is $n$: $$ \mathrm{rank}(\mathbf{A})=n $$ - The **determinant** of $\mathbf{A}$ is not zero: $$ \det(\mathbf{A}) \neq 0 $$ Conceptually, we want columns of $\mathbf{A}$ contains enough vectors to reach all coordinates (**span**) $\mathbb{R}^n$. However, when we include too many vectors, we will have **redundant** vectors when the new vectors does not provide new information (you can already express the new vectors using the existing vectors) and so the vectors become **linearly dependent** ## Linear Independence {#linearindependence} __Linear Dependence__: A set of vectors $\{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n\}$ is **linearly dependent** if some vector $\mathbf{v}_i$ is a *linear combination* of the *other vectors* $\mathbf{v}_j$ If all vectors **cannot** be written as linear combinations of the other vectors, then the set of vectors are **linearly independent** $\mathbf{v}_i$ is **not** a *linear combination* of the *other vectors* $\mathbf{v}_j$, i.e., $$ {\color{red}\mathbf{v}_i} \neq \sum_{j\neq i} c_j \mathbf{v}_j = \underbrace{c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots + c_n \mathbf{v}_n}_{\textrm{linear combination {\color{red}excluding} } {\color{red}\mathbf{v}_i}} \;\;\;\;\;\; \textrm{ for all } i $$ Subtracting $\mathbf{v}_i$, this is equivalent to $$ \underbrace{\mathbf{0}}_{\textrm{zero vector!}} \neq {\color{red} - \mathbf{v}_i} + \sum_{j\neq i} c_j \mathbf{v}_j = \underbrace{c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots + {\color{red} (-1) \mathbf{v}_i} + \cdots + c_n \mathbf{v}_n}_{\textrm{linear combination of } \mathbf{v}_1, \mathbf{v}_2, \ldots, {\color{red} \mathbf{v}_i}, \ldots, \mathbf{v}_n} \;\; \textrm{ for all } i. $$ This is equivalent to saying: The only solution to $$ \underbrace{\mathbf{0}}_{\textrm{zero vector!}} = \underbrace{c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots + \mathbf{v}_i + \cdots + c_n \mathbf{v}_n}_{\textrm{linear combination of } \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_i, \ldots, \mathbf{v}_n} $$ is $c_1 = c_2 = \cdots = c_n = 0$. This is equivalent to the statement that $\mathbf{A}\mathbf{x} = \mathbf{0}$ implies $\mathbf{x} = \mathbf{0}$. __Linear independence__: A set of vectors ${\bf v}_1, {\bf v}_2, \cdots , {\bf v}_k$ is linearly independent if the only solution to the equation $$c_1{\bf v}_1 + c_2{\bf v}_2 + \cdots + c_k{\bf v}_k = 0$$ is $c_1 = c_2 = \cdots = c_k = 0$. If another solution exists, the set of vectors is linearly dependent. A set $S$ of vectors is linearly dependent if and only if at least one of the vectors in $S$ can be written as a linear combination of the other vectors in $S$. Linear independence is only defined for sets of vectors with the same number of elements; any linearly independent set of vectors in $n$-space contains at most $n$ vectors. Since $\begin{bmatrix}9 \\ 13 \\ 17 \end{bmatrix}$ is a linear combination of $\begin{bmatrix}1 \\ 2 \\ 3 \end{bmatrix}$, $\begin{bmatrix} 2 \\ 3\\ 4\end{bmatrix}$, and $\begin{bmatrix} 3 \\ 4 \\ 5 \end{bmatrix}$, these 4 vectors constitute a linearly dependent set. :::{#exm-linearindep} Are the following sets of vectors linearly independent? 1. $\begin{bmatrix}2 \\ 3 \\ 1 \end{bmatrix}$ and $\begin{bmatrix}4 \\ 6 \\ 1 \end{bmatrix}$ 2. $\begin{bmatrix}1 \\ 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix}0 \\ 5 \\ 0 \end{bmatrix}$, and $\begin{bmatrix}10 \\ 10 \\ 0 \end{bmatrix}$ ::: :::{#exr-linearindep1} Are the following sets of vectors linearly independent? 1. $${\bf v}_1 = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} , {\bf v}_2 = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} , {\bf v}_3 = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} $$ 2. $${\bf v}_1 = \begin{bmatrix} 2 \\ 2 \\ 1 \end{bmatrix} , {\bf v}_2 = \begin{bmatrix} -4 \\ 6 \\ 5 \end{bmatrix} , {\bf v}_3 = \begin{bmatrix} -2 \\ 8 \\ 6 \end{bmatrix} $$ ::: ## Rank of a Matrix Another way to think about linear independence is to consider the **rank** of a matrix. __Rank__: The **rank** of a matrix is the number of linearly independent rows or columns in the matrix. The rank of a matrix is denoted by $\textrm{rank}(\mathbf{A})$. For example $$\begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{bmatrix}$$ Rank = 3 $$\begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 0 \end{bmatrix}$$ Rank = 2 :::{#exr-rank} Find the rank of each matrix below: (Hint: transform the matrices into row echelon form. Remember that the number of nonzero rows of a matrix in row echelon form is the rank of that matrix) 1. $$\begin{bmatrix} 1 & 1 & 2 \\ 2 & 1 & 3 \\ 1 & 2 & 3 \end{bmatrix}$$ 2. $$\begin{bmatrix} 1 & 3 & 3 & -3 & 3\\ 1 & 3 & 1 & 1 & 3 \\ 1 & 3 & 2 & -1 & -2 \\ 1 & 3 & 0 & 3 & -2 \end{bmatrix}$$ ::: Answer to @exr-rank: 1. rank is 2 2. rank is 3 ## Determinants <iframe width="560" height="315" src="https://www.youtube.com/embed/Ip3X9LOh2dk" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen style="border:1;display:block;margin:10px auto;"></iframe> __Singularity__: Determinants can be used to determine whether a square matrix is nonsingular. A square matrix is nonsingular if and only if its determinant is not zero. Determinant of a $1 \times 1$ matrix, equals $|\mathbf{A}|=|a_{11}|=a_{11}$ Determinant of a $2 \times 2$ matrix, $$\mathbf{A}=\begin{vmatrix} a_{11}&a_{12}\\ a_{21}&a_{22} \end{vmatrix}$$ \begin{align*}\det({\bf A}) &= |{\bf A}|\\ &= a_{11}|a_{22}| - a_{12}|a_{21}|\\ &= a_{11}a_{22} - a_{12}a_{21} \end{align*} We can extend the second to last equation above to get the definition of the determinant of a $3 \times 3$ matrix: \begin{align*} \begin{vmatrix} a_{11}&a_{12}&a_{13}\\ a_{21} & a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33} \end{vmatrix} &= a_{11} \begin{vmatrix} a_{22}&a_{23}\\ a_{32}&a_{33} \end{vmatrix} - a_{12} \begin{vmatrix} a_{21}&a_{23}\\ a_{31}&a_{33} \end{vmatrix} + a_{13} \begin{vmatrix} a_{21}&a_{22}\\ a_{31}&a_{32} \end{vmatrix}\\ &= a_{11}(a_{22}a_{33} - a_{23}a_{32}) - a_{12}(a_{21}a_{33} - a_{23}a_{31}) + a_{13}(a_{21}a_{32} - a_{22}a_{31}) \end{align*} Let's extend this now to any $n\times n$ matrix. Let's define $\mathbf{A}_{ij}$ as the $(n-1)\times (n-1)$ submatrix of $\mathbf{A}$ obtained by deleting row $i$ and column $j$. Let the $(i,j)$th __minor__ of $\mathbf{A}$ be the determinant of $\mathbf{A}_{ij}$: $$M_{ij} = \left|\mathbf{A}_{ij}\right|$$ Then for any $n\times n$ matrix $\mathbf{A}$ $$|\mathbf{A}| = a_{11}M_{11} - a_{12}M_{12} + \cdots + (-1)^{n+1} a_{1n} M_{1n}$$ For example, in figuring out whether the following matrix has an inverse? $$\mathbf{A}=\begin{bmatrix} 1&1&1\\0&2&3\\5&5&1 \end{bmatrix}$$ 1. Calculate its determinant. \begin{align*} |\mathbf{A}| &= 1(2-15) - 1(0-15) + 1(0-10) \nonumber\\ &= -13+15-10 \nonumber\\ &= -8\nonumber \end{align*} 2. Since $|{\bf A}|\ne 0$, we conclude that ${\bf A}$ has an inverse. :::{#exr-determinants} Determine whether the following matrices are nonsingular: 1. $$\begin{bmatrix} 1 & 0 & 1\\ 2 & 1 & 2\\ 1 & 0 & -1 \end{bmatrix}$$ 2. $$\begin{bmatrix} 2 & 1 & 2\\ 1 & 0 & 1\\ 4 & 1 & 4 \end{bmatrix}$$ ::: ## Getting Inverse of a Matrix using its Determinant Thus far, we have a number of algorithms to 1. Find the solution of a linear system, 2. Find the inverse of a matrix but these remain just that --- algorithms. At this point, we have no way of telling how the solutions $x_j$ change as the parameters $a_{ij}$ and $b_i$ change, except by changing the values and "rerunning" the algorithms. With determinants, we can provide an explicit formula for the inverse and therefore provide an explicit formula for the solution of an $n\times n$ linear system. Hence, we can examine how changes in the parameters and $b_i$ affect the solutions $x_j$. __Determinant Formula for the Inverse of a $2 \times 2$__: The determinant of a $2 \times 2$ matrix $\mathbf{A}=\begin{bmatrix} a & b\\ c & d\\ \end{bmatrix}$ is defined as: $$\det(\mathbf{A}) = a d - b c$$ The inverse of $\mathbf{A}$ is given by: $$\frac{1}{\det({\bf A})} \begin{bmatrix} d & -b \\ -c & a\\ \end{bmatrix}$$ For example, Let's calculate the inverse of matrix A from @exr-invlinsys using the determinant formula. Recall, $$\mathbf{A} = \begin{bmatrix} -3 & 4\\ 2 & -1\\ \end{bmatrix}$$ $$\det(\mathbf{A}) = (-3)(-1) - (4)(2) = 3 - 8 = -5$$ $$\frac{1}{\det(\mathbf{A})} \begin{bmatrix} -1 & -4\\ -2 & -3\\ \end{bmatrix}$$ $$\frac{1}{-5} \begin{bmatrix} -1 & -4\\ -2 & -3\\ \end{bmatrix}$$ $$\begin{bmatrix} \frac{1}{5} & \frac{4}{5}\\ \frac{2}{5} & \frac{3}{5}\\ \end{bmatrix}$$ :::{#exr-calcinverse} Caculate the inverse of $\mathbf{A}$ $$\mathbf{A} = \begin{bmatrix} 3 & 5\\ -7 & 2\\ \end{bmatrix}$$ ::: ## Answers to Examples and Exercises {-} Answer to @exm-linearindep: 1. yes 2. no Answer to @exr-linearindep1: 1. yes 2. no ($-v_1 -v_2 + v_3 = 0$) Answer to @exr-rank: 1. rank is 2 2. rank is 3 Answer to @exm-inverse: $\left(\begin{array}{ccc|ccc} 1&1&1&1&0&0\\ 0&2&3&0&1&0\\ 5&5&1&0&0&1 \end{array} \right)$ $\left(\begin{array}{ccc|ccc} 1&1&1 &1 &0&0\\ 0&2&3 &0 &1&0\\ 0&0&-4&-5&0&1 \end{array} \right)$ $\left(\begin{array}{ccc|ccc} 1&1&1&1 &0&0\\ 0&2&3&0 &1&0\\ 0&0&1&5/4&0&-1/4 \end{array} \right)$ $\left(\begin{array}{ccc|ccc} 1&1&0&-1/4 &0&1/4\\ 0&2&0&-15/4&1&3/4\\ 0&0&1&5/4 &0&-1/4 \end{array} \right)$ $\left(\begin{array}{ccc|ccc} 1&1&0&-1/4 &0 &1/4\\ 0&1&0&-15/8&1/2&3/8\\ 0&0&1&5/4 &0 &-1/4 \end{array} \right)$ $\left(\begin{array}{ccc|ccc} 1&0&0&13/8 &-1/2&-1/8\\ 0&1&0&-15/8&1/2 &3/8\\ 0&0&1&5/4 &0 &-1/4 \end{array} \right)$ ${\bf A}^{-1} = \left(\begin{array}{ccc} 13/8 &-1/2&-1/8\\ -15/8&1/2 &3/8\\ 5/4 &0 &-1/4 \end{array} \right)$ Answer to @exr-inverse1: 1. ${\bf A}^{-1}=\begin{bmatrix} 1&0&-4\\0&\frac{1}{2}&0\\0&0&1 \end{bmatrix}$ Answer to @exr-invlinsys: $\textbf{z} = \bf{A}^{-1} \bf{b} = \begin{bmatrix} 1/5 &4/5\\ 2/5&3/5 \end{bmatrix} \begin{bmatrix} 5 \\ -10 \end{bmatrix}= \begin{bmatrix} -7 \\ -4 \end{bmatrix} = \begin{bmatrix} x \\ y \end{bmatrix}$ Answer to @exr-determinants: 1. nonsingular 2. singular Answer to @exr-calcinverse: $\begin{bmatrix} \frac{2}{41} & \frac{-5}{41}\\ \frac{7}{41} & \frac{3}{41}\\ \end{bmatrix}$