- Do the following problems in Section 4.3: Problems 33, 34 which relate to linear independence of polynomials and problems 37 and 38 which deal with linear independence of trigonometric functions.
- Do the following problems in Section 4.4: Problems 13 and 14 which relate to the coordinates with respect to a basis of polynomials and problems 27, 28, 29, 30, 31, 32 which ask you to use the coordinates of polynomials to answer linear independence and span questions. Theorem 8 on page 221 is essential for these problems. How this theorem is used is explained in Example 6 and in the narrative between Theorem 8 and Example 6.
- Do the following problems in Section 4.5: Problems 21, 22, 23, 24 which ask you to use the coordinates of a set of polynomials to prove that they form a basis of a space of polynomials. For these problems you use the same method as in Section 4.4.
-
Let us now look at few subspaces of $\mathbb{P}_2.$ First consider the set
\[
\mathcal{H}_0 = \bigl\{ \mathbf{p} \in \mathbb{P}_2 \, : \, \mathbf{p}(0) = 0 \bigr\}.
\]
That is, by $\mathcal{H}_0$ we denote the set of all polynomials in $\mathbb{P}_2$ which have one root equal to $0.$ For example the polynomial $\mathbf{q}_1(x) = x$ is in $\mathcal{H}_0.$ Similarly, $\mathbf{q}_2(x) = x^2$ is also in $\mathcal{H}_0.$
- One task in this context is to use the definition of a subspace to prove that $\mathcal{H}_0$ is a subspace of $\mathbb{P}_2.$
- In three items below we will prove a more informative statement \[ \mathcal{H}_0 = \operatorname{Span}\bigl\{ x, x^2 \bigr\}. \]
- Proofs involving equality of two sets are done in two steps. We first prove that each polynomial in $\mathcal{H}_0$ must also be in $\operatorname{Span}\bigl\{ x, x^2 \bigr\},$ that is we prove that \[ \mathcal{H}_0 \subseteq \operatorname{Span}\bigl\{ x, x^2 \bigr\}. \] Then we prove that each polynomial in $\operatorname{Span}\bigl\{ x, x^2 \bigr\}$ must also be in $\mathcal{H}_0,$ that is we prove that \[ \operatorname{Span}\bigl\{ x, x^2 \bigr\} \subseteq \mathcal{H}_0. \] Together these two facts prove the equality of two sets.
- Assume that $\mathbf{p} \in \mathcal{H}_0.$ Then $\mathbf{p} \in \mathbb{P}_2$ and $\mathbf{p}(0) = 0.$ Therefore, for some $a_0, a_1, a_2 \in \mathbb{R}$ we have \[ \mathbf{p}(x) = a_0 + a_1 x + a_2 x^2 \quad \text{and} \quad \mathbf{p}(0) = a_0 + a_1 \, 0 + a_2 \, 0^2 = a_0 = 0. \] Since we proved that $a_0=0,$ we have $\mathbf{p}(x) = a_1 x + a_2 x^2,$ that is $\mathbf{p} \in \operatorname{Span}\bigl\{ x, x^2 \bigr\}.$ This proves \[ \mathcal{H}_0 \subseteq \operatorname{Span}\bigl\{ x, x^2 \bigr\}. \]
- Assume that $\mathbf{p} \in \operatorname{Span}\bigl\{ x, x^2 \bigr\}.$ Then there exist $\alpha_1, \alpha_2 \in \mathbb{R}$ such that $\mathbf{p}(x) = \alpha_1 x + \alpha_2 x^2.$ Since $\mathbf{p}(0) = \alpha_1 \, 0 + \alpha_2 \, 0^2 = 0$ we conclude that $\mathbf{p} \in \mathcal{H}_0.$ This proves \[ \operatorname{Span}\bigl\{ x, x^2 \bigr\} \subseteq \mathcal{H}_0. \] This item and the preceding one prove \[ \mathcal{H}_0 = \operatorname{Span}\bigl\{ x, x^2 \bigr\}. \]
- Above we expressed $\mathcal{H}_0$ as a span of two polynomials. By Theorem 1 each span is a subspace. Therefore, this is an alternative proof that $\mathcal{H}_0$ is a subspace. Since the set $\bigl\{ x, x^2 \bigr\}$ is linearly independent and since $\bigl\{ x, x^2 \bigr\}$ spans $\mathcal{H}_0$ we have that $\bigl\{ x, x^2 \bigr\}$ is a basis for $\mathcal{H}_0.$ Consequently \[ \dim \mathcal{H}_0 = 2. \]
-
Consider the set
\[
\mathcal{H}_1 = \bigl\{ \mathbf{p} \in \mathbb{P}_2 \, : \, \mathbf{p}(1) = 0 \bigr\}.
\]
That is, by $\mathcal{H}_1$ we denote the set of all polynomials in $\mathbb{P}_2$ which have one root equal to $1.$ For example the polynomial $\mathbf{q}_1(x) = x-1$ is in $\mathcal{H}_1.$ Similarly, $\mathbf{q}_2(x) = x^2-x$ is also in $\mathcal{H}_1.$
- In two items below we will prove that \[ \mathcal{H}_1 = \operatorname{Span}\bigl\{ x -1 , x^2-x \bigr\}. \]
-
Assume that $\mathbf{p} \in \mathcal{H}_1.$ Then $\mathbf{p} \in \mathbb{P}_2$ and $\mathbf{p}(1) = 0.$ Therefore, for some $a_0, a_1, a_2 \in \mathbb{R}$ we have
\[
\mathbf{p}(x) = a_0 + a_1 x + a_2 x^2 \quad \text{and} \quad \mathbf{p}(0) = a_0 + a_1 \,1 + a_2 \, 1^2 = a_0 + a_1 + a_2 = 0.
\]
Hence $a_1 = -a_0 - a_2$ and $\mathbf{p}$ can be expressed as
\begin{align*}
\mathbf{p}(x) & = a_0 + a_1 x + a_2 x^2 \\
&= a_0 + (-a_0 - a_2) x + a_2 x^2 \\
& = a_0 - a_0 x - a_2 x +a_2 x^2 \\
& = (-a_0) (x-1) + a_2 (x^2-x).
\end{align*}
Thus we proved the implication:
If $\mathbf{p} \in \mathcal{H}_1$, then $\mathbf{p} \in \operatorname{Span}\bigl\{ x-1, x^2-1 \bigr\}.$ The preceding implication proves the inclusion \[ \mathcal{H}_1 \subseteq \operatorname{Span}\bigl\{ x - 1, x^2 - x \bigr\}. \] -
Assume that $\mathbf{p} \in \operatorname{Span}\bigl\{ x - 1, x^2 - x \bigr\}.$ Then there exist $\alpha_1, \alpha_2 \in \mathbb{R}$ such that
\[
\mathbf{p}(x) = \alpha_1 (x-1) + \alpha_2 (x^2 - x).
\]
Since $\mathbf{p}(1) = \alpha_1 \, 0 + \alpha_2 \, 0 = 0,$ we conclude that $\mathbf{p} \in \mathcal{H}_1.$
If $\mathbf{p} \in \operatorname{Span}\bigl\{ x-1, x^2 - x \bigr\}$, then $\mathbf{p} \in \mathcal{H}_1.$ The preceding implication proves the inclusion \[ \operatorname{Span}\bigl\{ x -1, x^2 - x \bigr\} \subseteq \mathcal{H}_1. \] This item and the preceding one prove the set equality \[ \mathcal{H}_1 = \operatorname{Span}\bigl\{ x - 1 , x^2 - x \bigr\}. \] - Above we expressed $\mathcal{H}_1$ as a span of two polynomials. By Theorem 1 on page 196 each span is a subspace. Therefore, this is an alternative proof that $\mathcal{H}_1$ is a subspace.
- Next we need to prove that $\bigl\{ x - 1, x^2 - x \bigr\}$ is a linearly independent set. We use the definition of linear independence. Assume that $\alpha_1, \alpha_2 \in \mathbb{R}$ are such that \[ \alpha_1 (x-1) + \alpha_2 (x^2-x) = 0 \quad \text{for all} \quad x \in \mathbb{R}. \] Setting $x=0$ yields $-\alpha_1 = 0.$ Thus, $\alpha_1 = 0.$ Substituting this in the assumption yields \[ \alpha_2 (x^2-x) = 0 \quad \text{for all} \quad x \in \mathbb{R}. \] Setting $x=-1$ yields $2\alpha_2 = 0.$ Thus, $\alpha_2 = 0.$ Hence we proved $\alpha_1 = 0$ and $\alpha_2 = 0.$ This proves the linear independence of $\bigl\{ x - 1, x^2 - x \bigr\}.$ Consequently $\bigl\{ x - 1, x^2 - x \bigr\}$ is a basis for $\mathcal{H}_1$ and \[ \dim \mathcal{H}_1 = 2. \]
- On Monday we introduced a concept of an abstract vector space. An abstract vector space I will usually denote by $\mathcal{V},$ or same other nearby capital calygraphy letter, like $\mathcal{U},$ or $\mathcal{W}.$ Individual vectors in these spaces will be denoted by lower case letters, $u,$ $v,$ $w,$ which will often be indexed, like $v_1,$ $v_2,$ and so on.
-
We talked about the following concepts this week:
- The definition of an abstract vector space on page 192 and posted on November 29.
- The definition of a subspace on page 195
- The definition of the span of a set of vectors in the first paragraph of the subsection "A Subspace Spanned by a Set" starting on page 196. This definition in the set-builder notation reads: Let $m$ be a positive integer and let ${v}_1,\ldots,{v}_m$ be vectors in a vector space $\mathcal{V}.$ The span of vectors ${v}_1,\ldots,{v}_m$ is defined as \[ \operatorname{Span}\bigl\{{v}_1,\ldots,{v}_m\bigr\} = \bigl\{ \alpha_1 {v}_1 + \cdots + \alpha_m {v}_m : \alpha_1,\ldots,\alpha_m \in \mathbb{R} \bigr\}. \] This is a very important theorem on page 196: Theorem 1. $\operatorname{Span}\{{v}_1,\ldots,{v}_m\}$ is a subspace of $\mathcal{V}.$
- The definition of a linearly independent set on page 210. Next, I will restate this definition as an implication: An indexed set of vectors $\{{v}_1,\ldots,{v}_m\}$ in a vector space $\mathcal{V}$ is said to be linearly independent if the following implication holds \[ \alpha_1 {v}_1 + \cdots + \alpha_m {v}_m = {0} \quad \text{implies} \quad \alpha_k = 0 \quad \text{for all} \quad k \in \{1,\ldots,m\}. \] There are many other equivalent ways of stating this definition. However, the above statement is the only formal definition which is easiest to use when we need to prove that certain vectors are linearly independent.
- The definition of a basis on page 211.
- The relevant section in the book is Section 4.3: Linear independent sets; bases. Suggested problems for Section 4.3: 3, 4, 5, 9, 10, 11, 13, 14, 15, 21, 22, 23, 25, 26, 33, 34. This is a good opportunity to review linear independence of vectors in $\mathbb{R}^n.$ Most of these problems deal with vectors in $\mathbb{R}^n.$ Pay special attention to problems 33, 34 which deal with polynomials and 37 and 38 which deal with trigonomatric functions.
- Important examples of finite dimensional vector spaces are spaces of polynomials. For $n\in\mathbb{N}$ by $\mathbb{P}_n$ we denote the vector space of all polynomials of degree less or equal to $n.$ The most important step in understanding the vector space $\mathbb{P}_n$ is establishing that the monomials form a basis of this space. I wrote this webpage with a proof which uses only linear algebra. The proof which I give below for $\mathbb{P}_2$ uses calculus. The proof which is given in our textbook uses the Fundamental Theorem of Algebra (which is more difficult to prove.)
-
The friendliest among spaces $\mathbb{P}_n$ is the spaces $\mathbb{P}_2$. Below I explore some of the properties of $\mathbb{P}_2$.
- $\mathbb{P}_2$ denotes the vector space of all polynomials of degree less or equal $2.$ That is, in set-builder notation, \[ \mathbb{P}_2 = \bigl\{a_0 + a_1 x +a_2 x^2 \, : \, a_0, a_1, a_2 \in \mathbb{R} \bigr\}. \] Recall that the constant polynomial $1$ is a polynomial in $\mathbb{P}_2$. To get this polynomial in the above set-builder notation we take $a_0 = 1,$ $a_1 = 0,$ and $a_2 = 0.$ To get the polynomial $x$ in the above set-builder notation we take $a_0 = 0,$ $a_1 = 1,$ and $a_2 = 0.$ Similarly, to get the square polynomial $x^2$ in the above set-builder notation we take $a_0 = 0,$ $a_1 = 0,$ and $a_2 = 1.$ Using the concept of the span the above expression for $\mathbb{P}_2$ in set-builder notation can be written using the concept of the span as \[ \mathbb{P}_2 = \operatorname{Span}\bigl\{ 1, x, x^2 \bigr\}. \]
-
Here is a proof that the polynomials $1, x, x^2$ are linearly independent in the vector space ${\mathbb P}_2$.
Assume that $\alpha_1,$ $\alpha_2,$ and $\alpha_3$ are scalars in $\mathbb{R}$ such that \[ \require{bbox} \bbox[5px, #88FF88, border: 1pt solid green]{\alpha_1\cdot 1 + \alpha_2 x + \alpha_3 x^2 =0 \quad \text{for all} \quad x \in \mathbb{R}}. \] The objective here is to prove \[ \bbox[5px, #FF4444, border: 1pt solid red]{\alpha_1 = 0, \quad \alpha_2 =0, \quad \alpha_3 = 0}. \] Consider the left-hand side of the above green identity as a function of $x$ and take the derivative with respect to $x$. We obtain \[ \bbox[5px, #88FF88, border: 1pt solid green]{\alpha_2 + 2 \alpha_3 x =0 \quad \text{for all} \quad x \in \mathbb{R}}. \] Again, consider the left-hand side of the above green identity as a function of $x$ and take the derivative with respect to $x$. We obtain \[ \bbox[5px, #88FF88, border: 1pt solid green]{2 \alpha_3 =0 \quad \text{for all} \quad x \in \mathbb{R}}. \] Substituting $x=0$ in the first two green identities and dividing the third green equality by $2$ we obtain \[ \bbox[5px, #88FF88, border: 1pt solid green]{\alpha_1 = 0, \quad \alpha_2 =0, \quad \alpha_3 = 0}. \] In this way we have greenifyed the red statement. That is, we proved it.
-
Here is an alternative proof that the polynomials $1, x, x^2$ are linearly independent in the vector space ${\mathbb P}_2$.
Assume that $\alpha_1,$ $\alpha_2,$ and $\alpha_3$ are scalars in $\mathbb{R}$ such that \[ \require{bbox} \bbox[5px, #88FF88, border: 1pt solid green]{\alpha_1\cdot 1 + \alpha_2 x + \alpha_3 x^2 =0 \quad \text{for all} \quad x \in \mathbb{R}}. \] The objective here is to prove \[ \bbox[5px, #FF4444, border: 1pt solid red]{\alpha_1 = 0, \quad \alpha_2 =0, \quad \alpha_3 = 0}. \] The above green identity holds for all $x\in\mathbb{R}.$ In particular it holds for specific $x=-1,$ $x=0,$ and $x=1.$ That is, we have \[ \bbox[5px, #88FF88, border: 1pt solid green]{ \begin{array}{lr} \alpha_1 - \alpha_2 +\alpha_3 &=0 \\ \alpha_1 &=0 \\ \alpha_1 + \alpha_2 +\alpha_3 &=0 \\ \end{array} } \] The last green box contains a homogeneous system of linear equations which can be written in a matrix form as \[ \bbox[5px, #88FF88, border: 1pt solid green]{ \left[\!\begin{array}{rrr} 1 & -1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{array}\!\right] \left[\!\begin{array}{c} \alpha_1 \\ \alpha_2 \\ \alpha_3 \end{array}\!\right] = \left[\!\begin{array}{c} 0 \\ 0 \\ 0 \end{array}\!\right] } \] Since the determinant of the above $3\!\times\!3$ matrix is $2$, the above homogeneous equation has only the trivial solution. That is, \[ \bbox[5px, #88FF88, border: 1pt solid green]{\alpha_1 = 0, \quad \alpha_2 =0, \quad \alpha_3 = 0}. \] In this way we have greenifyed the red statement. That is, we proved it.
- Hence, \[ \mathbb{P}_2 = \operatorname{Span}\bigl\{ 1, x, x^2 \bigr\} \] and $\mathcal{M} = \bigl\{ 1, x, x^2 \bigr\}$ is a basis for $\mathbb{P}_2.$ I denoted this basis by $\mathcal{M}$ since the polynomials $1,$ $x,$ $x^2$ are called monomials.
- We did Section 4.1 today. Recommended exercises: 1, 3, 5, 6, 7, 8, 9, 11 13, 15, 16, 17, 18, 21, 22, 23, 24.
-
Here I recall the definition of a vector space as I stated it in class.
Definition. A nonempty set $\mathcal{V}$ is said to be a vector space over $\mathbb R$ if it satisfies the following ten axioms.
Axiom 1. (AE) There exists a function $+: \mathcal{V}\!\times\!\mathcal{V} \to \mathcal{V}.$That is, for each pair $(u,v) \in \mathcal{V}\!\times\!\mathcal{V}$ there exists a unique $u+v \in \mathcal{V}$ which is called the sum of $u$ and $v.$Axiom 2. (AA) For every $u, v, w \in \mathcal{V}$ we have $u+(v+w) = (u+v)+w$Axiom 3. (AC) For every $u, v \in \mathcal{V}$ we have $u+v = v+u$Axiom 4. (AZ) There exists $0 \in \mathcal{V}$ such that for every $v \in \mathcal{V}$ we have $v+0 = v$Axiom 5. (AO) For every $v \in \mathcal{V}$ there exists $-v \in \mathcal{V}$ such that $v+(-v) = 0$Axiom 6. (SE) There exists a function $\cdot: \mathbb{R}\!\times\!\mathcal{V} \to \mathcal{V}.$That is, for each real number $\alpha \in \mathbb R$ and each $v \in \mathcal{V}$ there exists a unique $\alpha v \in \mathcal{V}$ which is called the scalar product of $\alpha$ and $v.$Axiom 7. (SA) For every $\alpha, \beta \in \mathbb R$ and every $v \in \mathcal{V}$ we have $\alpha (\beta v) = (\alpha\beta) v$Axiom 8. (SD) For every $\alpha, \beta \in \mathbb R$ and every $v \in \mathcal{V}$ we have $(\alpha +\beta) v = \alpha v + \beta v$Axiom 9. (SD) For every $\alpha \in \mathbb R$ and every $u, v \in \mathcal{V}$ we have $\alpha (u + v) = \alpha u + \alpha v$Axiom 10. (S0) For every $v \in \mathcal{V}$ we have $1 v = v$Explanation of the abbreviations: AE--addition exists, AA--addition is associative, AC--addition is commutative, AZ--addition has zero, AO--addition has opposites, SE-- scaling exists, SA--scaling is associative, SD--scaling distributes over addition of real numbers, SD--scaling distributes over addition of vectors, SO--scaling with one.
- To illustrate the definition of a vector space we studied an exotic vector space: \[ \require{bbox} \mathcal{V} = \left\{ \bbox[yellow]{\left[\! \begin{array}{c} x_1 \\ x_2 \end{array} \!\right]} \, : \, x_1, x_2 \in \mathbb{R} \ \ \text{and} \ \ x_1, x_2 \gt 0 \right\} \] with the addition defined as \[ \bbox[yellow]{\left[\! \begin{array}{c} x_1 \\ x_2 \end{array} \!\right]} \bbox[yellow]{+} \bbox[yellow]{\left[\! \begin{array}{c} y_1 \\ y_2 \end{array} \!\right]} = \bbox[yellow]{\left[\! \begin{array}{c} x_1 y_1 \\ x_2 y_2 \end{array} \!\right]} \quad \text{for all} \quad \bbox[yellow]{\left[\! \begin{array}{c} x_1 \\ x_2 \end{array} \!\right]}, \bbox[yellow]{\left[\! \begin{array}{c} y_1 \\ y_2 \end{array} \!\right]} \in \mathcal{V} \] and scaling defined as \[ \alpha \bbox[yellow]{\phantom{*}} \bbox[yellow]{\left[\! \begin{array}{c} x_1 \\ x_2 \end{array} \!\right]} = \bbox[yellow]{\left[\! \begin{array}{c} (x_1)^\alpha \\ (x_2)^\alpha \end{array} \!\right]} \quad \text{for all} \quad \bbox[yellow]{\left[\! \begin{array}{c} x_1 \\ x_2 \end{array} \!\right]}\in \mathcal{V} \quad \text{and for all} \quad \alpha \in \mathbb{R}. \] It is a nice exercise to verify that all the axioms of a vector space are satisfied. Interestingly, the zero vector in the vector space $\mathcal{V}$ is the vector $\bbox[yellow]{\left[\! \begin{array}{c} 1 \\ 1 \end{array} \!\right]}.$
- I colored the vectors in $\mathcal{V}$ yellow to distinguish them from the vectors in $\mathbb{R}^2.$
- Now consider the function $L:\mathcal{V} \to \mathbb{R}^2$ defined as follows \[ L \bbox[yellow]{\left[\! \begin{array}{c} x_1 \\ x_2 \end{array} \!\right]} = \left[\! \begin{array}{c} \ln x_1 \\ \ln x_2 \end{array} \!\right] \quad \text{for all} \quad \bbox[yellow]{\left[\! \begin{array}{c} x_1 \\ x_2 \end{array} \!\right]}\in \mathcal{V}. \] This function has the following two properties: \[ L \left(\bbox[yellow]{\left[\! \begin{array}{c} x_1 \\ x_2 \end{array} \!\right]} \bbox[yellow]{+} \bbox[yellow]{\left[\! \begin{array}{c} y_1 \\ y_2 \end{array} \!\right]} \right) = L \bbox[yellow]{\left[\! \begin{array}{c} x_1 \\ x_2 \end{array} \!\right]} + L \bbox[yellow]{\left[\! \begin{array}{c} y_1 \\ y_2 \end{array} \!\right]} \quad \text{for all} \quad \bbox[yellow]{\left[\! \begin{array}{c} x_1 \\ x_2 \end{array} \!\right]}, \bbox[yellow]{\left[\! \begin{array}{c} y_1 \\ y_2 \end{array} \!\right]} \in \mathcal{V} \] and \[ L \left(\alpha\bbox[yellow]{\phantom{*}} \bbox[yellow]{\left[\! \begin{array}{c} x_1 \\ x_2 \end{array} \!\right]} \right) = \alpha L \bbox[yellow]{\left[\! \begin{array}{c} x_1 \\ x_2 \end{array} \!\right]} \quad \text{for all} \quad \bbox[yellow]{\left[\! \begin{array}{c} x_1 \\ x_2 \end{array} \!\right]} \in \mathcal{V} \quad \text{and for all} \quad \alpha \in \mathbb{R}. \]
- These two properties make $L:\mathcal{V} \to \mathbb{R}^2$ a linear transformation defined on $\mathcal{V}$ to $\mathbb{R}^2.$
- It is interesting to study subspaces of the vector space $\mathcal{V}.$ For example, what is \[ \operatorname{Span} \left\{ \bbox[yellow]{\left[\! \begin{array}{c} 1 \\ 2 \end{array} \!\right]} \right\}, \] or, what is \[ \operatorname{Span} \left\{ \bbox[yellow]{\left[\! \begin{array}{c} 2 \\ 1 \end{array} \!\right]} \right\}, \] or, \[ \operatorname{Span} \left\{ \bbox[yellow]{\left[\! \begin{array}{c} 2 \\ 2 \end{array} \!\right]} \right\}, \] or \[ \operatorname{Span} \left\{ \bbox[yellow]{\left[\! \begin{array}{c} 4 \\ 2 \end{array} \!\right]} \right\}, \] or, \[ \operatorname{Span} \left\{ \bbox[yellow]{\left[\! \begin{array}{c} 2 \\ 4 \end{array} \!\right]} \right\}. \]
- I am posting two challenging problems related to this section.
- Experiencing mathematics
Understanding a theorem, mathematical concept, or a problem is an individual act of creative sensemaking that engages all our senses and creativity.
-
I will summarize what I posted on Tuesday. The main reason for this is to answer the question asked by Christopher O'Dell
in class:
Question. Let $f_n$, with $n \in \{0\}\cup\mathbb{N},$ be the Fibonacci numbers. Does there exist a continuous function $g:[0,+\infty)\to \mathbb{R}$ such that for every $n \in \{0\}\cup\mathbb{N}$ we have $g(n) = f_n.$ Here it is expected that we give a reasonably simple formula for $g.$
-
Let me summarize some findings about Fibonacci numbers from yesterday.
- Standard recursive definition. \[ f_0 = 0, \quad f_1 = 1 \quad \text{and} \quad \text{for every} \quad n \in \mathbb{N} \quad f_{n+1} = f_{n} + f_{n-1} \] This definition is uses only the addition of positive integers. Applying the recursive definition to the consecutive positive integers we obtain the sequence of Fibonacci numbers \[ f_2 = 1, f_3 = 2, f_4 = 3, f_5 = 5, f_6 = 8, f_7 = 13, f_8 = 21, f_9 = 34, f_{10} = 55, f_{11} = 89, f_{12} = 144, \cdots \]
- A formula for Fibonacci numbers using matrices. In class we deduced a formula for Fibonacci numbers using powers of a $2\!\times\!2$ matrix \[ \text{for all} \quad n \in \mathbb{N} \quad f_{n} = \bigl[ 1 \ \ 0 \bigr] \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^n \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right]. \] This formula involves powers of a matrix, which is not a simple calculation. It appears not to be recursive, although, in full honesty, the definition of powers is a recursive definition.
- A closed form expression for the Fibonacci numbers. We used a diagonalization of the matrix $\left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]$ to deduce the following closed form expression for the Fibonacci numbers: \[ \text{for all} \quad n \in \mathbb{N} \qquad f_{n} = \frac{1}{\sqrt{5}}\Biggl( \biggl(\frac{1+\sqrt{5}}{2}\biggr)^n - \biggl(\frac{1-\sqrt{5}}{2}\biggr)^n \Biggr). \] The difficulty with this formula is that calculating accurate high powers of irrational numbers is difficult. It is important to mention that the irrational number \[ \varphi = \frac{1+\sqrt{5}}{2} \] is the famous number called Golden Ratio. We have that \[ \frac{1}{\varphi} = \frac{2}{1+\sqrt{5}} = \frac{2}{1+\sqrt{5}} \frac{1-\sqrt{5}}{1-\sqrt{5}} = \frac{2 (1-\sqrt{5})}{1-5} = - \frac{1-\sqrt{5}}{2}. \] Therefore, the closed form expression for the Fibonacci numbers can be written as \[ \text{for all} \quad n \in \mathbb{N} \qquad f_{n} = \frac{1}{\sqrt{5}}\Bigl( \varphi^n - (-1)^n \varphi^{-n} \Bigr). \]
- In the previous item we deduced the following closed form expression for the Fibonacci numbers \[ \text{for all} \quad n \in \mathbb{N} \qquad f_{n} = \frac{1}{\sqrt{5}}\Bigl( \varphi^n - (-1)^n \varphi^{-n} \Bigr). \] Here $\varphi$ is the Golden Ratio. The preceding displayed formula indicates a possible answer to Christopher's question. In the displayed formula for the Fibonacci numbers replace $n$ with a positive real number $x$ as follows: \[ \text{for all} \quad x \geq 0 \quad \text{set} \qquad g(x) = \frac{1}{\sqrt{5}}\Bigl( \varphi^x - (-1)^x \varphi^{-x} \Bigr). \] The problem with the given formula for $g(x)$ is that the expression $(-1)^x$ is not defined for noninteger values of $x.$ So, we have to work out some other formula.
-
In the last (wrong) displayed formula for $g(x)$ I notice three correctly defined functions of $x$:
\begin{equation*}
\color{orange}{a(x)} = \frac{\varphi^x - \varphi^{-x}}{\sqrt{5}}, \quad
\color{#008000}{b(x)} = \frac{ \varphi^x}{\sqrt{5}}, \quad
\color{#000080}{c(x)} = \frac{\varphi^x + \varphi^{-x}}{\sqrt{5}}, \quad x \geq 0.
\end{equation*}
Clearly,
\begin{equation*}
\color{orange}{a(x)} \lt
\color{#008000}{b(x)} \lt
\color{#000080}{c(x)} \quad \text{for all} \quad x \geq 0.
\end{equation*}
On the plot below you can see the orange function $ \color{orange}{a(x)},$ the dark green function $\color{#008000}{b(x)}$ and the navy blue function $\color{#000080}{c(x)}$ and the first five Fibonacci numbers represented by red dots.
- Today we did a remarkable application of eigenvalues and eigenvectors to a famous sequence of positive integers: Fibonacci numbers.
- Recall that $\mathbb{N}$ denotes the set of positive integers. The Fibonacci numbers are the elements of the sequence \[ f_0, f_1, f_2, \ldots, f_n, \ldots \] recursively defined by \[ f_0 = 0, \quad f_1 = 1, \quad \text{and} \quad f_{n+1} = f_n + f_{n-1} \quad \text{for} \quad n \in \mathbb{N}. \] Since we are given $f_0 = 0$ and $f_1 = 1$ using the recursion $f_{n+1} = f_n + f_{n-1}$ with $n=1$ we get $f_2 = 0+1 = 1.$ A repeated use of the recursion $f_{n+1} = f_n + f_{n-1}$ with $n=2$, then $n=3$, and so on, we get \[ f_0 = 0, \ f_1 = 1, \ f_2 = 1, \ f_3 = 2, \ f_4 = 3, \ f_5 = 5, \ f_6 = 8, \ f_7 = 13, \ f_8 = 21, \ f_9 = 34, \ f_{10} = 55, \ f_{11} = 89, \ \ldots \ \] It is clear that with enough patience we can calculate $f_{100}$ by calculating all Fibonacci numbers preceding it. Computers are really good with doing recursively defined operations. I wrote a webpage on how to do this in Mathematica. If you want to try using Mathematica on WWU computers please let me know. I can help you with that. By the way, \[ f_{100} = 354,224,848,179,261,915,075 \]
- Since in Mathematics we like to be able to approach mathematical concepts in diverse ways, we are interested in finding a formula for the $n$-th Fibonacci number without calculating all the preceding Fibonacci numbers; a formula that will use only $n$ and algebraic operations. Amazingly, Linear Algebra offers a way to do that. The next items will illustrate how that comes about.
- The first step is to write the recutsion \[ f_{n+1} = f_n + f_{n-1} \] using a matrix: \[ \left[\!\begin{array}{l} f_{n} \\ f_{n+1} \end{array}\!\right] = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right] \left[\!\begin{array}{l} f_{n-1} \\ f_{n} \end{array}\!\right]. \] Thus, we can obtain the Fibonacci sequence by repeated application of the matrix $\displaystyle\left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]$ as follows \begin{align*} \left[\!\begin{array}{l} f_{1} \\ f_{2} \end{array}\!\right] & = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right] \left[\!\begin{array}{l} f_0 \\ f_{1} \end{array}\!\right] = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right] \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right] \\ \left[\!\begin{array}{l} f_{2} \\ f_{3} \end{array}\!\right] & = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right] \left[\!\begin{array}{l} f_{1} \\ f_{2} \end{array}\!\right] = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right] \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right] \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right] = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^2 \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right] \\ \left[\!\begin{array}{l} f_{3} \\ f_{4} \end{array}\!\right] &= \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right] \left[\!\begin{array}{l} f_{2} \\ f_{3} \end{array}\!\right] = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]\left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^2 \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right] = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^3 \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right] \\ \left[\!\begin{array}{l} f_{4} \\ f_{5} \end{array}\!\right] &= \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right] \left[\!\begin{array}{l} f_{3} \\ f_{4} \end{array}\!\right] = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right] \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^3 \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right] = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^4 \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right] \\ & \ \vdots \\ \left[\!\begin{array}{l} f_{n} \\ f_{n-1} \end{array}\!\right] &= \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right] \left[\!\begin{array}{l} f_{n-1} \\ f_{n-2} \end{array}\!\right] = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right] \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^{n-1} \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right] = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^n \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right] \\ \left[\!\begin{array}{l} f_{n+1} \\ f_{n} \end{array}\!\right] &= \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right] \left[\!\begin{array}{l} f_{n} \\ f_{n-1} \end{array}\!\right] = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right] \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^{n} \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right] = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^{n+1} \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right] \end{align*}
- In the preceding item we saw that \[ \left[\!\begin{array}{l} f_{n} \\ f_{n-1} \end{array}\!\right] = \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^n \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right]. \] Therefore \[ f_n = \bigl[ 1 \ \ 0 \bigr] \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^n \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right]. \] We could stop here and pronounce that this is sufficiently good formula for $f_n$ which uses only $n$ and matrix algebra. However, we want a formula for $f_n$ which uses only algebra with specific numbers; without matrices. To obtain such a formula we will calculate the eigenvalues and eigenvectors of the matrix $\displaystyle\left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]$.
- First we calculate the characteristic polynomial of $\displaystyle\left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]$: \[ \det\left( \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right] - \left[\!\begin{array}{cc} \lambda & 0 \\ 0 & \lambda \end{array}\!\right] \right) = \left|\!\begin{array}{cc} -\lambda & 1 \\ 1 & 1-\lambda \end{array}\!\right| = -\lambda(1-\lambda) - 1 = \lambda^2 - \lambda - 1 \] The roots of the characteristic polynomial are \[ \lambda_1 = \frac{1+\sqrt{5}}{2} = \varphi \quad \text{and} \quad \lambda_2 = \frac{1-\sqrt{5}}{2} = \psi. \] The number $\phi$ is the famous number Golden ratio. The Greek letter $\varphi$ is the standard notation for the Golden ratio. We introduce $\psi$ since we will use it several times below.
- An eigenvector of $\displaystyle\left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]$ corresponding to $\varphi$ is $\displaystyle\left[\!\begin{array}{l} 1 \\ \varphi \end{array}\!\right]$ and an eigenvector corresponding to $\psi$ is $\displaystyle\left[\!\begin{array}{l} 1 \\ \psi \end{array}\!\right]$. Please verify that \[ \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]\left[\!\begin{array}{l} 1 \\ \varphi \end{array}\!\right] = \varphi \left[\!\begin{array}{l} 1 \\ \varphi \end{array}\!\right] \quad \text{and} \quad \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]\left[\!\begin{array}{l} 1 \\ \psi \end{array}\!\right] = \psi \left[\!\begin{array}{l} 1 \\ \psi \end{array}\!\right]. \] To verify the preceding vector equalities you will use that $\varphi$ and $\psi$ are the roots of the characteristic polynomial, that is \[ \varphi^2 - \varphi - 1 = 0 \quad \text{and} \quad \psi^2 - \psi - 1 = 0. \] One of the important properties of eigenvectors is that it is easy to calculate the action of the powers of the matrix on eigenvectors: \[ \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^n \left[\!\begin{array}{c} 1 \\ \varphi \end{array}\!\right] = \varphi^n \left[\!\begin{array}{c} 1 \\ \varphi \end{array}\!\right] \quad \text{and} \quad \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^n \left[\!\begin{array}{c} 1 \\ \psi \end{array}\!\right] = \psi^n \left[\!\begin{array}{c} 1 \\ \psi \end{array}\!\right]. \]
- To improve the formula \[ f_n = \bigl[ 1 \ \ 0 \bigr] \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^n \left[\!\begin{array}{c} 0 \\ 1 \end{array}\!\right] \] we will represent the vector $\displaystyle\left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right]$ as a linear combination of the eigenvectors: \[ \left[\!\begin{array}{c} 0 \\ 1 \end{array}\!\right] = x_1 \left[\!\begin{array}{c} 1 \\ \varphi \end{array}\!\right] + x_2 \left[\!\begin{array}{c} 1 \\ \psi \end{array}\!\right]. \] We do not need to do row reduction to solve this system. Since $x_1+x_2 = 0$ we deduce that $x_2 = -x_1$. Then we have \[ x_1 (\varphi - \psi) = 1. \] Since $\varphi - \psi = \sqrt{5}$ we have \[ \left[\!\begin{array}{c} 0 \\ 1 \end{array}\!\right] = \frac{1}{\sqrt{5}} \left[\!\begin{array}{c} 1 \\ \varphi \end{array}\!\right] - \frac{1}{\sqrt{5}} \left[\!\begin{array}{c} 1 \\ \psi \end{array}\!\right]. \] Therefore, \begin{align*} f_n & = \bigl[ 1 \ \ 0 \bigr] \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^n \left[\!\begin{array}{l} 0 \\ 1 \end{array}\!\right] \\ & = \bigl[ 1 \ \ 0 \bigr] \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^n \left( \frac{1}{\sqrt{5}} \left[\!\begin{array}{c} 1 \\ \varphi \end{array}\!\right] - \frac{1}{\sqrt{5}} \left[\!\begin{array}{c} 1 \\ \psi \end{array}\!\right] \right) \\ & = \bigl[ 1 \ \ 0 \bigr] \left( \frac{1}{\sqrt{5}} \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^n \left[\!\begin{array}{c} 1 \\ \varphi \end{array}\!\right] - \frac{1}{\sqrt{5}} \left[\!\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\!\right]^n \left[\!\begin{array}{c} 1 \\ \psi \end{array}\!\right] \right) \\ & = \bigl[ 1 \ \ 0 \bigr] \left( \frac{1}{\sqrt{5}} \varphi^n \left[\!\begin{array}{l} 1 \\ \varphi \end{array}\!\right] - \frac{1}{\sqrt{5}} \psi^n \left[\!\begin{array}{c} 1 \\ \psi \end{array}\!\right] \right) \\ & = \frac{1}{\sqrt{5}} \bigl[ 1 \ \ 0 \bigr] \left( \left[\!\begin{array}{c} \varphi^n \\ \varphi^{n+1} \end{array}\!\right] - \left[\!\begin{array}{c} \psi^{n} \\ \psi^{n+1} \end{array}\!\right] \right) \\ & = \frac{1}{\sqrt{5}} \bigl[ 1 \ \ 0 \bigr] \left[\!\begin{array}{c} \varphi^n - \psi^{n} \\ \varphi^{n+1} -\psi^{n+1} \end{array}\!\right]\\ & = \frac{1}{\sqrt{5}} \bigl( \varphi^n - \psi^{n} \bigr). \end{align*} Thus, finally and amazingly, \[ f_n = \frac{1}{\sqrt{5}} \bigl( \varphi^n - \psi^{n} \bigr) = \frac{1}{\sqrt{5}} \left( \frac{(1+\sqrt{5})^n}{2^n} - \frac{(1-\sqrt{5})^n}{2^n} \right) = \frac{ (1+\sqrt{5})^n - (1-\sqrt{5})^n }{2^n \sqrt{5}} \] for all nonnegative integers $n$. A formula like this in which $f_n$ is given in terms of $n$ and standard functions is called a closed form expression. A lot of effort in mathematics has been put in finding closed form expressions for different mathematical objects.
- This and the following item are related to the Fibonacci numbers but not to Linear ALgebra. I post it since it is interesting mathematics that you can understand and might be interested in. Without knowing what we derived above, if somebody showed you the expression \[ \frac{ (1+\sqrt{5})^n - (1-\sqrt{5})^n }{2^n \sqrt{5}} \] with $n$ a positive integer, how would one know that this is an integer. For small $n$ we could calculate, and we would get the Fibonacci numbers, but proving that it is always the case is an interesting exercise.
- One can use the Binomial theorem to expend the numerator \[ (1+\sqrt5)^n-(1-\sqrt5)^n=\sum_{k=0}^{n} \binom{n}{k}(\sqrt{5})^k-\sum_{k=0}^{n} \binom{n}{k}(-1)^k (\sqrt{5})^k. \] In the above sums we can write the even and odd terms separately and get \[ \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n}{2j}(\sqrt{5})^{2j} + \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n}{2j+1}(\sqrt{5})^{2j+1} - \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n}{2j}(\sqrt{5})^{2j} + \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n}{2j+1}(\sqrt{5})^{2j+1}. \] Hence \[ (1+\sqrt5)^n-(1-\sqrt5)^n=2 \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n}{2j+1}(\sqrt{5})^{2j+1} = 2 \sqrt{5} \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n}{2j+1} 5^{j}. \] Dividing by $2^n\sqrt{5}$ so we get: \[ \frac{ (1+\sqrt{5})^n - (1-\sqrt{5})^n }{2^n \sqrt{5}} = \frac{2\sqrt{5}}{2^n \sqrt{5}}\sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n}{2j+1} 5^{j} = \frac{1}{2^{n-1}} \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n}{2j+1} 5^{j}. \] This gives us another interesting formula for the Fibonacci numbers \[ f_n = \frac{1}{2^{n-1}} \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n}{2j+1} 5^{j} \quad \text{where} \quad n \in\mathbb{N}. \] But it would be interesting to prove that the number \[ \frac{1}{2^{n-1}} \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n}{2j+1} 5^{j} \quad \text{where} \quad n \in\mathbb{N} \] is always an integer. I do not know how to do that directly, without all the work done in this post.
- Recommended exercises for Section 5.3 are 2, 3, 5, 8, 9, 12, 13, 16, 18, 20, 23, 24.
-
Today we proved the following theorem
Theorem. Let $n \in \mathbb{N}$ and let $A$ be an $n\!\times\!n$ matrix. The matrix $A$ is diagonalizable if and only if there exists a basis of $\mathbb{R}^n$ which consists of eigenvectors of $A.$
Theorem. Let $n \in \mathbb{N}$ and let $A$ be an $n\!\times\!n$ matrix. The following two statements are equivalent:
(a) There exist an invertible $n\!\times\!n$ matrix $P$ and a diagonal $n\!\times\!n$ matrix $D$ such that $A= PDP^{-1}.$
(b) There exist linearly independent vectors $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n$ in $\mathbb{R}^n$ and real numbers $\lambda_1, \lambda_2,\ldots,\lambda_n$ such that $A \mathbf{v}_k = \lambda_k \mathbf{v}_k$ for all $k\in \{1,\ldots,n\}.$
- Proof of (b)⇒(a). Assume (b). That is, assume that there exist linearly independent vectors $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n$ in $\mathbb{R}^n$ and real numbers $\lambda_1, \lambda_2,\ldots,\lambda_n$ such that \[ A \mathbf{v}_k = \lambda_k \mathbf{v}_k \quad \text{for all} \quad k\in \{1,\ldots,n\}. \] The preceding displayed expression contains $n$ vector equations. These $n$ vector equations can be expressed as one matrix equation \[ \Bigl[ A \mathbf{v}_1 \ A \mathbf{v}_2 \ \cdots \ A \mathbf{v}_n \Bigr] = \Bigl[ \lambda_1 \mathbf{v}_1 \ \lambda_2 \mathbf{v}_2 \ \cdots \ \lambda_n \mathbf{v}_n \Bigr]. \] By the definition of the matrix multiplication the preceding matrix equality can be expressed as \[ A \Bigl[ \mathbf{v}_1 \ \mathbf{v}_2 \ \cdots \ \mathbf{v}_n \Bigr] = \Bigl[ \mathbf{v}_1 \ \mathbf{v}_2 \ \cdots \ \mathbf{v}_n \Bigr] \left[\!\begin{array}{cccc} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n \end{array}\!\right]. \] The preceding matrix equality can be written as \[ A P = P D, \] where we set \[ P = \Bigl[ \mathbf{v}_1 \ \mathbf{v}_2 \ \cdots \ \mathbf{v}_n \Bigr] \quad \text{and} \quad D = \left[\!\begin{array}{cccc} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n \end{array}\!\right]. \] Since we assume that $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n$ are linearly independent vectors in $\mathbb{R}^n$ the matrix $P$ is invertible by the Invertible Matrix Theorem. Therefore, the matrix $P^{-1}$ exists. Multiplying the equality \[ AP=PD \] from the right by $P^{-1}$ we get \[ A = PDP^{-1}. \] This proves (a).
- Now we recall Example 1 from Tuesday, November 16, 2021. We calculated that \begin{align*} \left[\! \begin{array}{rrr} 3 & 1 & -1 \\ 1 & 3 & -1 \\ 3 & 3 & -1 \end{array} \!\right] \left[\! \begin{array}{c} 1 \\ 1 \\ 3 \end{array} \!\right] & = 1 \left[\! \begin{array}{c} 1 \\ 1 \\ 3 \end{array} \!\right], \\ \left[\! \begin{array}{rrr} 3 & 1 & -1 \\ 1 & 3 & -1 \\ 3 & 3 & -1 \end{array} \!\right] \left[\! \begin{array}{r} -1 \\ 1 \\ 0 \end{array} \!\right] & = 2 \left[\! \begin{array}{r} -1 \\ 1 \\ 0 \end{array} \!\right], \\ \left[\! \begin{array}{rrr} 3 & 1 & -1 \\ 1 & 3 & -1 \\ 3 & 3 & -1 \end{array} \!\right]\left[\! \begin{array}{c} 1 \\ 0 \\ 1 \end{array} \!\right] & = 2 \left[\! \begin{array}{c} 1 \\ 0 \\ 1 \end{array} \!\right]. \end{align*} and \[ \left[\! \begin{array}{crc|ccc} 1 & -1 & 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0 & 1 & 0 \\ 3 & 0 & 1 & 0 & 0 & 1 \end{array} \!\right] \sim \cdots \sim \left[\! \begin{array}{ccc|rrc} 1 & 0 & 0 & -1 & -1 & 1\\ 0 & 1 & 0 & 1 & 2 & -1 \\ 0 & 0 & 1 & 3 & 3 & -2 \end{array} \!\right]. \]
- In the preceding item we have that \[ A = \left[\! \begin{array}{rrr} 3 & 1 & -1 \\ 1 & 3 & -1 \\ 3 & 3 & -1 \end{array} \!\right] \] is a $3\!\times\!3$ matrix. The vectors \[ \mathbf{v}_1 = \left[\! \begin{array}{c} 1 \\ 1 \\ 3 \end{array} \!\right], \quad \mathbf{v}_2 = \left[\! \begin{array}{r} -1 \\ 1 \\ 0 \end{array} \!\right], \quad \mathbf{v}_3 = \left[\! \begin{array}{r} 1 \\ 0 \\ 1 \end{array} \!\right] \] are linearly independent vectors in $\mathbb{R}^3$ which are eigenvectors of $A$ such that \[ A \mathbf{v}_1 = 1 \mathbf{v}_1, \quad A \mathbf{v}_2 = 2 \mathbf{v}_2, \quad A \mathbf{v}_3 = 2 \mathbf{v}_3. \] Based on the proof presented above the preceding three vector equations can be written as one matrix equation as follows (this is the equation $AP=PD$ in the proof) \[ \left[\! \begin{array}{rrr} 3 & 1 & -1 \\ 1 & 3 & -1 \\ 3 & 3 & -1 \end{array} \!\right] \left[\! \begin{array}{crc} 1 & -1 & 1\\ 1 & 1 & 0 \\ 3 & 0 & 1 \end{array} \!\right] = \left[\! \begin{array}{crc} 1 & -1 & 1\\ 1 & 1 & 0 \\ 3 & 0 & 1 \end{array} \!\right] \left[\! \begin{array}{crc} 1 & 0 & 0\\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{array} \!\right] \] Multiplying the preceding matrix equation with the inverse calculated in the previous item \[ \left[\! \begin{array}{crc} 1 & -1 & 1\\ 1 & 1 & 0 \\ 3 & 0 & 1 \end{array} \!\right]^{-1} = \left[\! \begin{array}{rrr} -1 & -1 & 1 \\ 1 & 2 & -1 \\ 3 & 3 & -2 \end{array} \!\right], \] we get the diagonalization of the matrix $A$: \[ \left[\! \begin{array}{rrr} 3 & 1 & -1 \\ 1 & 3 & -1 \\ 3 & 3 & -1 \end{array} \!\right] = \left[\! \begin{array}{rrr} 1 & -1 & 1 \\ 1 & 1 & 0 \\ 3 & 0 & 1 \end{array} \!\right] \left[\! \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{array} \!\right] \left[\! \begin{array}{rrr} -1 & -1 & 1 \\ 1 & 2 & -1 \\ 3 & 3 & -2 \end{array} \!\right] . \] Notice that this is a specific numerical matrix equality and it takes just a little bit of patience to verify whether it is true or not.
- Consider the matrix \[ A = \frac{1}{5} \left[\! \begin{array}{rr} 4 & 3/2 \\[5pt] 1 & 7/2 \end{array} \!\right] \qquad A = \left[\! \begin{array}{rr} 0.8 & 0.3 \\[5pt] 0.2 & 0.7 \end{array} \!\right] \] These two matrices are identical, but performing computations with them on a computer might give different results. For example, using computer algebra system Wolfram Mathematica (To get started with Mathematica see my Mathematica page.) gives
-
Proofs are important aspect of mathematics. One proof that you need to understand is Theorem 2 in Section 5.1. Since I like stating important theorems in English without using any symbols, I restate this theorem in English without any symbols.
- I did not post the Assignment on Canvas yet. I will do that later today. One problem that will be on the assignment is the problem which I posted on October 2.
- For Section 5.2 do 1-8, 11, 12, 14, 15, (in all these problems you can find eigenvectors as well) 9, 13, 18, 19, 20, 21, 24, 25, 27.
-
Example 1. In this item I will illustrate how to calculate eigenvalues and the corresponding eigenspaces of a specific $3\!\times\!3$ matrix. Consider the matrix
\[
A = \left[\!
\begin{array}{rrr}
3 & 1 & -1 \\
1 & 3 & -1 \\
3 & 3 & -1
\end{array}
\!\right] .
\]
- First we find the characteristic polynomial of this matrix. The characteristic polynomial is the determinant of the following matrix: \[ A - \lambda I_3 = \left[\! \begin{array}{rrr} 3 & 1 & -1 \\ 1 & 3 & -1 \\ 3 & 3 & -1 \end{array} \!\right] - \left[\! \begin{array}{rrr} \lambda & 0 & 0 \\ 0 & \lambda & 0 \\ 0 & 0 & \lambda \end{array} \!\right] = \left[\! \begin{array}{ccc} 3-\lambda & 1 & -1 \\ 1 & 3-\lambda & -1 \\ 3 & 3 & -1-\lambda \end{array} \!\right] \] Next we calculate this determinant: \begin{align*} \left|\! \begin{array}{ccc} 3-\lambda & 1 & -1 \\ 1 & 3-\lambda & -1 \\ 3 & 3 & -1-\lambda \end{array} \!\right| &= \left|\! \begin{array}{ccc} 2-\lambda & -2+\lambda & 0 \\ 1 & 3-\lambda & -1 \\ 3 & 3 & -1-\lambda \end{array} \!\right| \\ &= \left|\! \begin{array}{ccc} 2-\lambda & 0 & 0 \\ 1 & 4-\lambda & -1 \\ 3 & 6 & -1-\lambda \end{array} \!\right| \\ &= (2-\lambda) \bigl( (4-\lambda)(-1-\lambda) + 6 \bigr) \\ & = (2-\lambda)\bigl(\lambda^2 - 3 \lambda + 2\bigr) \\ & = -(\lambda - 2)^2 ( \lambda - 1) \end{align*} (At the first equality sign, we subtracted the second row from the first. At the second equality sign, we added the first column to the second. These operations do not change the value of a determinant.)
- Thus the eigenvalues of the matrix $A$ are $1$ and $2.$
- Next we will find the eigenspace corresponding to the eigenvalue $1.$ For that we need to find the nullspace of the matrix \[ A - 1 I_3 = \left[\! \begin{array}{rrr} 3 & 1 & -1 \\ 1 & 3 & -1 \\ 3 & 3 & -1 \end{array} \!\right] - \left[\! \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \!\right] = \left[\! \begin{array}{ccc} 2 & 1 & -1 \\ 1 & 2 & -1 \\ 3 & 3 & -2 \end{array} \!\right]. \] So, we row reduce this matrix: \[ \left[\! \begin{array}{ccc} 2 & 1 & -1 \\ 1 & 2 & -1 \\ 3 & 3 & -2 \end{array} \!\right] \sim \left[\! \begin{array}{ccc} 1 & 2 & -1 \\ 0 & 3 & -1 \\ 0 & 3 & -1 \end{array} \!\right] \sim \left[\! \begin{array}{ccc} 1 & 2 & -1 \\ 0 & 1 & -1/3 \\ 0 & 0 & 0 \end{array} \!\right] \sim \left[\! \begin{array}{ccc} 1 & 0 & -1/3 \\ 0 & 1 & -1/3 \\ 0 & 0 & 0 \end{array} \!\right]. \] Thus, the eigenspace is the subspace \[ \left\{ \left[\! \begin{array}{c} s/3 \\ s/3 \\ s \end{array} \!\right] \ : \ s \in \mathbb{R} \right\} = \operatorname{Span} \left\{ \left[\! \begin{array}{c} 1 \\ 1 \\ 3 \end{array} \!\right] \right\}. \] Hence one eigenvector is $\left[\! \begin{array}{c} 1 \\ 1 \\ 3 \end{array} \!\right].$
- Next we will find the eigenspace corresponding to the eigenvalue $2.$ For that we need to find the nullspace of the matrix \[ A - 2 I_3 = \left[\! \begin{array}{rrr} 3 & 1 & -1 \\ 1 & 3 & -1 \\ 3 & 3 & -1 \end{array} \!\right] - \left[\! \begin{array}{rrr} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{array} \!\right] = \left[\! \begin{array}{rrr} 1 & 1 & -1 \\ 1 & 1 & -1 \\ 3 & 3 & -3 \end{array} \!\right]. \] So, we row reduce this matrix: \[ \left[\! \begin{array}{rrr} 1 & 1 & -1 \\ 1 & 1 & -1 \\ 3 & 3 & -3 \end{array} \!\right] \sim \left[\! \begin{array}{rrr} 1 & 1 & -1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array} \!\right]. \] Thus, the eigenspace is the subspace \[ \left\{ \left[\! \begin{array}{c} -s + t \\ s \\ t \end{array} \!\right] \ : \ s, t \in \mathbb{R} \right\} = \operatorname{Span} \left\{ \left[\! \begin{array}{c} -1 \\ 1 \\ 0 \end{array} \!\right], \left[\! \begin{array}{c} 1 \\ 0 \\ 1 \end{array} \!\right] \right\}. \] Hence two linearly independent eigenvectors corresponding to the eigenvalue $2$ are $\left[\! \begin{array}{c} -1 \\ 1 \\ 0 \end{array} \!\right]$ and $\left[\! \begin{array}{c} 1 \\ 0 \\ 1 \end{array} \!\right].$
- The magic of what we found by now is that we found a basis of $\mathbb{R}^3$ which consists of eigenvectors of $A:$ \[ \left[\! \begin{array}{c} 1 \\ 1 \\ 3 \end{array} \!\right], \quad \left[\! \begin{array}{r} -1 \\ 1 \\ 0 \end{array} \!\right], \quad \left[\! \begin{array}{c} 1 \\ 0 \\ 1 \end{array} \!\right]. \]
- It is easy to verify whether these are really eigenvectors: \begin{align*} \left[\! \begin{array}{rrr} 3 & 1 & -1 \\ 1 & 3 & -1 \\ 3 & 3 & -1 \end{array} \!\right] \left[\! \begin{array}{c} 1 \\ 1 \\ 3 \end{array} \!\right] & = 1 \left[\! \begin{array}{c} 1 \\ 1 \\ 3 \end{array} \!\right], \\ \left[\! \begin{array}{rrr} 3 & 1 & -1 \\ 1 & 3 & -1 \\ 3 & 3 & -1 \end{array} \!\right] \left[\! \begin{array}{r} -1 \\ 1 \\ 0 \end{array} \!\right] & = 2 \left[\! \begin{array}{r} -1 \\ 1 \\ 0 \end{array} \!\right], \\ \left[\! \begin{array}{rrr} 3 & 1 & -1 \\ 1 & 3 & -1 \\ 3 & 3 & -1 \end{array} \!\right]\left[\! \begin{array}{c} 1 \\ 0 \\ 1 \end{array} \!\right] & = 2 \left[\! \begin{array}{c} 1 \\ 0 \\ 1 \end{array} \!\right]. \end{align*} Yes, they are.
- I also made the claim that the three eigenvectors are linearly independent. Let us verify that as well. \[ \left[\! \begin{array}{crc|ccc} 1 & -1 & 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0 & 1 & 0 \\ 3 & 0 & 1 & 0 & 0 & 1 \end{array} \!\right] \sim \cdots \sim \left[\! \begin{array}{ccc|rrc} 1 & 0 & 0 & -1 & -1 & 1\\ 0 & 1 & 0 & 1 & 2 & -1 \\ 0 & 0 & 1 & 3 & 3 & -2 \end{array} \!\right]. \] We know that the right-hand side matrix in the Reduced Row Echelon Form is the inverse of the matrix whose columns are the eigenvectors. To verify the row reduction above, we calculate: \[ \left[\! \begin{array}{rrr} 1 & -1 & 1 \\ 1 & 1 & 0 \\ 3 & 0 & 1 \end{array} \!\right] \left[\! \begin{array}{rrr} -1 & -1 & 1 \\ 1 & 2 & -1 \\ 3 & 3 & -2 \end{array} \!\right] = \left[\! \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \!\right]. \]
-
Example 2. In this item I will illustrate how to calculate eigenvalues and the corresponding eigenspaces of a specific $4\!\times\!4$ matrix. The purpose is to demonstrate a matrix that is not diagonalizable. Consider the matrix
\[
A = \left[\!
\begin{array}{rrrr}
0 & 0 & -1 & -1 \\
-1 & 0 & 0 & 0 \\
2 & 1 & 2 & 1 \\
-2 & -1 & -1 & 0
\end{array}
\!\right] .
\]
- First we find the characteristic polynomial of this matrix. The characteristic polynomial is the determinant of the following matrix: \[ A - \lambda I_4 = \left[\! \begin{array}{rrrr} 0 & 0 & -1 & -1 \\ -1 & 0 & 0 & 0 \\ 2 & 1 & 2 & 1 \\ -2 & -1 & -1 & 0 \end{array} \!\right] - \left[\! \begin{array}{rrrr} \lambda & 0 &0 & 0 \\ 0 & \lambda & 0 & 0 \\ 0 & 0 & \lambda & 0 \\ 0 & 0 & 0 & \lambda \end{array} \!\right] = \left[\! \begin{array}{cccc} -\lambda & 0 & -1 & -1 \\ -1 & -\lambda & 0 & 0 \\ 2 & 1 & 2-\lambda & 1 \\ -2 & -1 & -1 & -\lambda \end{array} \!\right] \] Next we calculate the determinant of the preceding matrix: \begin{align*} \left|\! \begin{array}{cccc} -\lambda & 0 & -1 & -1 \\ -1 & -\lambda & 0 & 0 \\ 2 & 1 & 2-\lambda & 1 \\ -2 & -1 & -1 & -\lambda \end{array} \!\right| & = -\lambda \left|\begin{array}{ccc} -\lambda & 0 & 0 \\ 1 & 2-\lambda & 1 \\ -1 & -1 & -\lambda \end{array} \right| - \left| \begin{array}{ccc} -1 & -\lambda & 0 \\ 2 & 1 & 1 \\ -2 & -1 & -\lambda \end{array} \right| + \left| \begin{array}{ccc} -1 & -\lambda & 0 \\ 2 & 1 & 2-\lambda \\ -2 & -1 & -1 \end{array} \right| \\ & = \lambda^2 ( \lambda^2 -2 \lambda + 1 ) - \bigl( \lambda -1 +2 \lambda - 2 \lambda^2 \bigr) + \bigl( \lambda - 1 + 2 \lambda - 2 \lambda^2 \bigr) \\ & = \lambda^2 ( \lambda^2 -2 \lambda + 1 ) \\ & = \lambda^2 ( \lambda - 1 )^2 \end{align*}
- Thus the eigenvalues of the matrix $A$ are $0$ and $1.$
- Next we will find the eigenspace corresponding to the eigenvalue $0.$ For that we need to find the nullspace of the matrix \[ A - 0 I_4 = \left[\! \begin{array}{rrrr} 0 & 0 & -1 & -1 \\ -1 & 0 & 0 & 0 \\ 2 & 1 & 2 & 1 \\ -2 & -1 & -1 & 0 \end{array} \!\right] \]
- So, we row reduce the matrix $A:$ \[ \left[\! \begin{array}{rrrr} 0 & 0 & -1 & -1 \\ -1 & 0 & 0 & 0 \\ 2 & 1 & 2 & 1 \\ -2 & -1 & -1 & 0 \end{array} \!\right] \sim \cdots \sim \left[\! \begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{array} \!\right] \] Thus, the eigenspace is the subspace \[ \left\{ \left[\! \begin{array}{c} 0 \\ s \\ -s \\ s \end{array} \!\right] \ : \ s \in \mathbb{R} \right\} = \operatorname{Span} \left\{ \left[\! \begin{array}{r} 0 \\ 1 \\ -1 \\ 1 \end{array} \!\right] \right\}. \]
- Thus, eigenspace corresponding to the eigenvalue $0$ is one-dimensional.
- Next we will find the eigenspace corresponding to the eigenvalue $1.$ For that we need to find the nullspace of the matrix \[ A - 1 I_4 = \left[\! \begin{array}{rrrr} 0 & 0 & -1 & -1 \\ -1 & 0 & 0 & 0 \\ 2 & 1 & 2 & 1 \\ -2 & -1 & -1 & 0 \end{array} \!\right] - \left[\! \begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \!\right] = \left[\! \begin{array}{rrrr} -1 & 0 & -1 & -1 \\ -1 & -1 & 0 & 0 \\ 2 & 1 & 1 & 1 \\ -2 & -1 & -1 & -1 \end{array} \!\right] \]
- So, we row reduce the precedig matrix: \[ \left[\! \begin{array}{rrrr} -1 & 0 & -1 & -1 \\ -1 & -1 & 0 & 0 \\ 2 & 1 & 1 & 1 \\ -2 & -1 & -1 & -1 \end{array} \!\right] \sim \cdots \sim \left[\! \begin{array}{rrrr} 1 & 0 & 1 & 1 \\ 0 & 1 & -1 & -1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array} \!\right] \] Thus, the eigenspace corresponding to the eigenvalue $1$ is the subspace \[ \left\{ \left[\! \begin{array}{c} -s-t \\ s+t \\ s \\ t \end{array} \!\right] \ : \ s, t \in \mathbb{R} \right\} = \operatorname{Span} \left\{ \left[\! \begin{array}{r} -1 \\ 1 \\ 1 \\ 0 \end{array} \!\right], \left[\! \begin{array}{r} -1 \\ 1 \\ 0 \\ 1 \end{array} \!\right] \right\}. \]
- Thus, the eigenspace corresponding to the eigenvalue $1$ is two-dimensional.
- Since we found all eigenspaces of the $4\!\times\!4$ matrix $A$ and these eigenspaces have dimensions $1$ and $2$, we conclude that we can have at most three linearly independent eigenvectors. Consequently, we can not have a basis for $\mathbb R^4$ which consists of eigenvectors of $A.$ This shows directly that the matrix $A$ is not diagonalizable.
- We did Section 5.1. Suggested problems for Section 5.1: 1, 3, 4, 5, 6, 8, 11, 15, 16, 17, 19, 20, 24-27, 29, 30, 31. We also did parts of Section 5.2.
- A related Wikipedia link: Eigenvalue, eigenvector and eigenspace.
- Below are animations of different matrices in action. In each scene the navy blue vector is the image of the sea green vector under the multiplication by a matrix $A$. For easier visualization of the action the heads of vectors leave traces.
- Just looking at the movies you can guess what are the eigenvalues and eigenvectors of the featured matrix. In particular it is easy to see whether an eigenvalue is positive, negative, zero, or complex, ... You can also approximately calculate which matrix is featured in each movie.
Place the cursor over the image to start the animation.
|
|
|
|
|
|
|
|
|
|
- Thank you for your question about calculating the inverse of a $3\!\times\!3$ matrix which would be similar to how we calculate the inverse of a $2\!\times\!2$ matrix. Below I explain that analogy. The key to recognize below is the use of cofactors in the inverse matrix.
- But, before we continue, I want to point out that a more efficient way to find the inverse of a $3\!\times\!3$ matrix is the method presented on October 21.
- Let \[ A = \left[\! \begin{array}{cc} a & b \\ c & d \end{array} \!\right]. \] Then without any conditions on the matrix $A$ we have \[ \left[\! \begin{array}{cc} a & b \\ c & d \end{array} \!\right] \left[\! \begin{array}{rr} d & -b \\ -c & a \end{array} \!\right] = (ad-bc) \left[\! \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \!\right]. \] Therefore $A$ is invertable if and only if $\det(A) = ad-bc \neq 0.$ If $\det(A) = ad-bc \neq 0,$ then \[ A^{-1} = \frac{1}{ad-bc} \left[\! \begin{array}{rr} d & -b \\ - c & a \end{array} \!\right] = \frac{1}{ad-bc} \left[\! \begin{array}{rr} d & -c \\ -b & a \end{array} \!\right]^{\top} \]
- It is truly amazing that the same pattern holds for a $3\!\times\!3$ matrix. We just have to take into account that the definition of the determinant for a $3\!\times\!3$ matrix is more complicated and the determinant can be expressed as three different looking cofactor expensions.
- Let \[ A = \left[\! \begin{array}{rrr} a & b & c \\ d & e & f \\ g & h & i \end{array} \!\right]. \] Recall that \begin{align*} \require{bbox} \det(A) & = a \left(\bbox[yellow]{\left|\! \begin{array}{cc} e & f \\ h & i \end{array} \!\right|}\right) + b \left(\bbox[yellow]{-\left|\! \begin{array}{cc} d & f \\ g & i \end{array} \!\right|}\right) + c \left(\bbox[yellow]{\left|\! \begin{array}{cc} d & e \\ g & h \end{array} \!\right|}\right) \\ & = d \left(\bbox[cyan]{-\left|\! \begin{array}{cc} b & c \\ h & i \end{array} \!\right|} \right) + e \left(\bbox[cyan]{\left|\! \begin{array}{cc} a & c \\ g & i \end{array} \!\right|}\right) + f \left(\bbox[cyan]{-\left|\! \begin{array}{cc} a & b \\ g & h \end{array} \!\right|}\right) \\ & = g \left(\bbox[#FF88FF]{\left|\! \begin{array}{cc} b & c \\ e & f \end{array} \!\right|}\right) + h \left(\bbox[#FF88FF]{-\left|\! \begin{array}{cc} a & c \\ d & f \end{array} \!\right|}\right) + i \left(\bbox[#FF88FF]{\left|\! \begin{array}{cc} a & b \\ d & e \end{array} \!\right|}\right) \\ & = aei + bfg +cdh - afh - bdi - ceg. \end{align*}
- Then without any assumptions on the $3\!\times\!3$ matrix $A$ we have \[ \require{bbox} \left[\! \begin{array}{rrr} a & b & c \\ d & e & f \\ g & h & i \end{array} \!\right] \left[\! \begin{array}{rrr} \bbox[yellow]{\left|\! \begin{array}{cc} e & f \\ h & i \end{array} \!\right|} & \bbox[cyan]{ -\left|\! \begin{array}{cc} b & c \\ h & i \end{array} \!\right|} & \bbox[#FF88FF]{ \left|\! \begin{array}{cc} b & c \\ e & f \end{array} \!\right|} \\[6pt] \bbox[yellow]{ -\left|\! \begin{array}{cc} d & f \\ g & i \end{array} \!\right|} & \bbox[cyan]{ \left|\! \begin{array}{cc} a & c \\ g & i \end{array} \!\right|} & \bbox[#FF88FF]{ -\left|\! \begin{array}{cc} a & c \\ d & f \end{array} \!\right|} \\[6pt] \bbox[yellow]{ \left|\! \begin{array}{cc} d & e \\ g & h \end{array} \!\right|} & \bbox[cyan]{ -\left|\! \begin{array}{cc} a & b \\ g & h \end{array} \!\right|} & \bbox[#FF88FF]{ \left|\! \begin{array}{cc} a & b \\ d & e \end{array} \!\right|} \end{array} \!\right] = \] (here we use the definition of matrix multiplication to calculate the product) \[ = \require{bbox} \left[\! \begin{array}{ccc} \bbox[yellow]{ a \left|\! \begin{array}{cc} e & f \\ h & i \end{array} \!\right| - b \left|\! \begin{array}{cc} d & f \\ g & i \end{array} \!\right| + c \left|\! \begin{array}{cc} d & e \\ g & h \end{array} \!\right|} \ & \bbox[cyan]{ - a \left|\! \begin{array}{cc} b & c \\ h & i \end{array} \!\right| + b \left|\! \begin{array}{cc} a & c \\ g & i \end{array} \!\right| - c \left|\! \begin{array}{cc} a & b \\ g & h \end{array} \!\right|} \ & \bbox[#FF88FF]{ a \left|\! \begin{array}{cc} b & c \\ e & f \end{array} \!\right| - b \left|\! \begin{array}{cc} a & c \\ d & f \end{array} \!\right| + c \left|\! \begin{array}{cc} a & b \\ d & e \end{array} \!\right|} \\[14pt] \bbox[yellow]{ d \left|\! \begin{array}{cc} e & f \\ h & i \end{array} \!\right| - e \left|\! \begin{array}{cc} d & f \\ g & i \end{array} \!\right| + f \left|\! \begin{array}{cc} d & e \\ g & h \end{array} \!\right|} \ & \bbox[cyan]{ - d \left|\! \begin{array}{cc} b & c \\ h & i \end{array} \!\right| + e \left|\! \begin{array}{cc} a & c \\ g & i \end{array} \!\right| - f \left|\! \begin{array}{cc} a & b \\ g & h \end{array} \!\right|} \ & \bbox[#FF88FF]{ d \left|\! \begin{array}{cc} b & c \\ e & f \end{array} \!\right| - e \left|\! \begin{array}{cc} a & c \\ d & f \end{array} \!\right| + f \left|\! \begin{array}{cc} a & b \\ d & e \end{array} \!\right|} \\[14pt] \bbox[yellow]{ g \left|\! \begin{array}{cc} e & f \\ h & i \end{array} \!\right| - h \left|\! \begin{array}{cc} d & f \\ g & i \end{array} \!\right| + i \left|\! \begin{array}{cc} d & e \\ g & h \end{array} \!\right|} \ & \bbox[cyan]{ - g \left|\! \begin{array}{cc} b & c \\ h & i \end{array} \!\right| + h \left|\! \begin{array}{cc} a & c \\ g & i \end{array} \!\right| - i \left|\! \begin{array}{cc} a & b \\ g & h \end{array} \!\right|} \ & \bbox[#FF88FF]{ g \left|\! \begin{array}{cc} b & c \\ e & f \end{array} \!\right| - h \left|\! \begin{array}{cc} a & c \\ d & f \end{array} \!\right| + i \left|\! \begin{array}{cc} a & b \\ d & e \end{array} \!\right|} \end{array} \!\right] = \] (now we notice that each colored entry in the preceding matrix is a cofactor expension of a $3\!\times\!3$ determinant; so each colored entry we write as a determinant; so the entry of the preceding matrix are $3\!\times\!3$ determinants) \[ = \left[\! \begin{array}{ccc} \bbox[yellow]{\left|\! \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \end{array} \!\right|} & \bbox[cyan]{\left|\! \begin{array}{ccc} a & b & c \\ a & b & c \\ g & h & i \end{array} \!\right|} & \bbox[#FF88FF]{ \left|\! \begin{array}{ccc} a & b & c \\ d & e & f \\ a & b & c \end{array} \!\right|} \\[6pt] \bbox[yellow]{ \left|\! \begin{array}{ccc} d & e & f \\ d & e & f \\ g & h & i \end{array} \!\right| } & \bbox[cyan]{\left|\! \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \end{array} \!\right|} & \bbox[#FF88FF]{ \left|\! \begin{array}{ccc} a & b & c \\ d & e & f \\ d & e & f \end{array} \!\right|} \\[6pt] \bbox[yellow]{\left|\! \begin{array}{ccc} g & h & i \\ d & e & f \\ g & h & i \end{array} \!\right|} & \bbox[cyan]{ \left|\! \begin{array}{ccc} a & b & c \\ g & h & i \\ g & h & i \end{array} \!\right|} & \bbox[#FF88FF]{ \left|\! \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \end{array} \!\right| } \end{array} \!\right] = \] (now looking carefully at each of nine determinants, we see that on the diagonal we have $\det(A)$ and off-diagonal we have determinants with two identical rows, so these are equal to $0$) \[ =\left[\! \begin{array}{ccc} \bbox[yellow]{ \det(A)} & \bbox[cyan]{0} & \bbox[#FF88FF]{0} \\[6pt] \bbox[yellow]{ 0} & \bbox[cyan]{\det(A)} & \bbox[#FF88FF]{0} \\[6pt] \bbox[yellow]{0} & \bbox[cyan]{0} & \bbox[#FF88FF]{\det(A)} \end{array} \!\right] = \det(A) \left[\! \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \!\right]. \]
- In conclusion, without any conditions on the $3\!\times\!3$ matrix $A$ we have \[ \require{bbox} \left[\! \begin{array}{rrr} a & b & c \\ d & e & f \\ g & h & i \end{array} \!\right] \left[\! \begin{array}{rrr} \bbox[yellow]{\left|\! \begin{array}{cc} e & f \\ h & i \end{array} \!\right|} & \bbox[cyan]{ -\left|\! \begin{array}{cc} b & c \\ h & i \end{array} \!\right|} & \bbox[#FF88FF]{ \left|\! \begin{array}{cc} b & c \\ e & f \end{array} \!\right|} \\[6pt] \bbox[yellow]{ -\left|\! \begin{array}{cc} d & f \\ g & i \end{array} \!\right|} & \bbox[cyan]{ \left|\! \begin{array}{cc} a & c \\ g & i \end{array} \!\right|} & \bbox[#FF88FF]{ -\left|\! \begin{array}{cc} a & c \\ d & f \end{array} \!\right|} \\[6pt] \bbox[yellow]{ \left|\! \begin{array}{cc} d & e \\ g & h \end{array} \!\right|} & \bbox[cyan]{ -\left|\! \begin{array}{cc} a & b \\ g & h \end{array} \!\right|} & \bbox[#FF88FF]{ \left|\! \begin{array}{cc} a & b \\ d & e \end{array} \!\right|} \end{array} \!\right] = \det(A) \left[\! \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \!\right]. \]
- The preceding formula shows that $A$ is invertible if and only if $\det(A) \neq 0.$ If $\det(A) \neq 0,$ then \[ A^{-1} = \frac{1}{\det(A)} \left[\! \begin{array}{rrr} \bbox[yellow]{\left|\! \begin{array}{cc} e & f \\ h & i \end{array} \!\right|} & \bbox[cyan]{ -\left|\! \begin{array}{cc} b & c \\ h & i \end{array} \!\right|} & \bbox[#FF88FF]{ \left|\! \begin{array}{cc} b & c \\ e & f \end{array} \!\right|} \\[6pt] \bbox[yellow]{ -\left|\! \begin{array}{cc} d & f \\ g & i \end{array} \!\right|} & \bbox[cyan]{ \left|\! \begin{array}{cc} a & c \\ g & i \end{array} \!\right|} & \bbox[#FF88FF]{ -\left|\! \begin{array}{cc} a & c \\ d & f \end{array} \!\right|} \\[6pt] \bbox[yellow]{ \left|\! \begin{array}{cc} d & e \\ g & h \end{array} \!\right|} & \bbox[cyan]{ -\left|\! \begin{array}{cc} a & b \\ g & h \end{array} \!\right|} & \bbox[#FF88FF]{ \left|\! \begin{array}{cc} a & b \\ d & e \end{array} \!\right|} \end{array} \!\right]. \] Notice that in the matrix on the right we have cofactors of the matrix $A.$
- The preceding formula for the inverse is commonly written with the transpose of the matrix involving the cofactors. \[ A^{-1} = \frac{1}{\det(A)} \left[\! \begin{array}{rrr} \bbox[yellow]{\left|\! \begin{array}{cc} e & f \\ h & i \end{array} \!\right|} & \bbox[yellow]{-\left|\! \begin{array}{cc} d & f \\ g & i \end{array} \!\right|} & \bbox[yellow]{\left|\! \begin{array}{cc} d & e \\ g & h \end{array} \!\right|} \\ \bbox[cyan]{-\left|\! \begin{array}{cc} b & c \\ h & i \end{array} \!\right|} & \bbox[cyan]{\left|\! \begin{array}{cc} a & c \\ g & i \end{array} \!\right|} & \bbox[cyan]{-\left|\! \begin{array}{cc} a & b \\ g & h \end{array} \!\right|} \\ \bbox[#FF88FF]{\left|\! \begin{array}{cc} b & c \\ e & f \end{array} \!\right|} & \bbox[#FF88FF]{-\left|\! \begin{array}{cc} a & c \\ d & f \end{array} \!\right|} & \bbox[#FF88FF]{\left|\! \begin{array}{cc} a & b \\ d & e \end{array} \!\right|} \end{array} \!\right]^{\mathbf{\top}}. \] Please recall the definition of the cofactors of $A$. With the definition of the cofactors the above formula for the inverse is simply \[ A^{-1} = \frac{1}{\det(A)} \left[\! \begin{array}{rrr} \bbox[yellow]{C_{11}} & \bbox[yellow]{C_{12}} & \bbox[yellow]{C_{13}} \\ \bbox[cyan]{C_{21}} & \bbox[cyan]{C_{22}} & \bbox[cyan]{C_{23}} \\ \bbox[#FF88FF]{C_{31}} & \bbox[#FF88FF]{C_{32}} & \bbox[#FF88FF]{C_{33}} \end{array} \!\right]^{\mathbf{\top}}. \]
- The pattern presented above for a $3\!\times\!3$ matrix holds for any $n\!\times\!n$ matrix: \[ \left[\! \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{array} \!\right] \left[\! \begin{array}{cccc} C_{11} & C_{21} & \cdots & C_{n1} \\ C_{12} & C_{22} & \cdots & C_{n2} \\ \vdots & \vdots & \ddots & \vdots \\ C_{1n} & C_{2n} & \cdots & C_{nn} \end{array} \!\right] = \det(A) I_n. \] A justification for this identity is the definition of determinant using the cofactor expansions along the rows of $A$ and the fact that a determinant with two identical rows is equal to $0.$
- Let us calculate the inverse of a specific $3\!\times\!3$ matrix. Consider \[ A = \left[\! \begin{array}{ccc} 1 & 2 & 6 \\ 3 & 5 & 7 \\ 4 & 8 & 9 \end{array} \!\right]. \] Let us first evaluate the determinant of this matrix in three different ways, by performing the cofactor expansion along each column: \begin{align*} \det A & = 1*(\bbox[yellow]{+(-11)})+2*(\bbox[yellow]{-(-1)})+6*(\bbox[yellow]{+(4)}) \\ & = 3*(\bbox[cyan]{-(-30)})+5*(\bbox[cyan]{+(-15)})+7*(\bbox[cyan]{-(0)}) \\ & = 4*(\bbox[#FF88FF]{+(-16)})+8*(\bbox[#FF88FF]{-(-11)})+9*(\bbox[#FF88FF]{+(-1)}) \\ & = 15. \end{align*} Since we are doing this three different ways, there is a lot of checking going on in the above calculations.
- Based on the three cofactor expansions above we can write the inverse of the given matrix $A:$ \[ A^{-1} = \frac{1}{15} \left[\! \begin{array}{rrr} \bbox[yellow]{-11} & \bbox[cyan]{30} & \bbox[#FF88FF]{-16} \\ \bbox[yellow]{1} & \bbox[cyan]{-15} & \bbox[#FF88FF]{11} \\ \bbox[yellow]{4} & \bbox[cyan]{0} & \bbox[#FF88FF]{-1} \end{array} \!\right]. \] To verify, calculate \[ \left[\! \begin{array}{ccc} 1 & 2 & 6 \\ 3 & 5 & 7 \\ 4 & 8 & 9 \end{array} \!\right] \left[\! \begin{array}{rrr} \bbox[yellow]{-11} & \bbox[cyan]{30} & \bbox[#FF88FF]{-16} \\ \bbox[yellow]{1} & \bbox[cyan]{-15} & \bbox[#FF88FF]{11} \\ \bbox[yellow]{4} & \bbox[cyan]{0} & \bbox[#FF88FF]{-1} \end{array} \!\right] = \left[\! \begin{array}{rrr} \bbox[yellow]{15} & \bbox[cyan]{0} & \bbox[#FF88FF]{0} \\ \bbox[yellow]{0} & \bbox[cyan]{15} & \bbox[#FF88FF]{0} \\ \bbox[yellow]{0} & \bbox[cyan]{0} & \bbox[#FF88FF]{15} \end{array} \!\right] \]
- Suggested problems for Section 3.2: 5, 7, 9, 11, 16-20 (even), 21, 25, 31, 33, 34, 35, 40c
-
I talked to a student yesterday. We discussed some questions from the sample exam. One question that came up was question 5 which has three parts (a), (b), (c). Part (a) asks to state the definition of invertible matrix. This definition is given in Section 2.2 The Inverse of a Matrix the first sentence of the third paragraph. In the 5th edition it is on page 105. I will restate the definition below.
-
This Theorem is Theorem 7 in Section 2.2 of the textbook. I do not know how to simplify the proof (see page 109 in 5th edition) which is given in the textbook of the implication:
- In mathematics we always want to present as simple proofs as possible. Here, neither the authors of the textbook nor I know of any simpler way to prove the implication in the preceding item. I think that the student that I talked to yesterday, presented a proof of the converse of the implication in the preceding item that is slightly simpler than the proof given in the book.
-
To complete the proof of the theorem we need to prove the implication:
- In this file you can find some problems in the form that they could appear on the exam. Some of the problems in this sample have too many items to be on an exam. On the exam I will assign at most three items per problem.
- I updated the calendar that was originally a part of the Information sheet.
- Suggested problems for Section 3.1: 1, 3, 5, 9, 11, 13, 17, 20, 21, 22, 25-32, 37, 41, 42
-
Below is a "click-by-click" proof. There are nine steps in this proof. I describe each step below.
- This is the determinant that we want to calculate.
- I emphasize that the $i$-th and $j$-th row in the identity matrix are interchanged.
- We will calculate the $n\!\times\!n$ determinant by cofactor expansion along the $i$-th row.
- Since the only nonzero entry in the $i$-th row is at the $j$-th place, the cofactor expansion equals $(-1)^{i+j}$ multiplied by an $(n-1)\times(n-1)$ determinant.
- We will calculate the $(n-1)\!\times\!(n-1)$ determinant using cofactor expansion along the $(j-1)$-st row. Notice that the only nonzero entry in the $(j-1)$-st row is $1$ which is at $i$-th position.
- The previous $(n-1)\!\times\!(n-1)$ determinant calculates to $(-1)^{i+j-1}$ multiplied by the $(n-2)\!\times\!(n-2)$ determinant of the identity matrix.
- The $(n-2)\!\times\!(n-2)$ determinant of the identity matrix calculates to $1$.
- $(-1)^{i+j}(-1)^{i+j-1} = (-1)^{2i+2j-1}$.
- $(-1)^{2i+2j-1} = -1$.
All entries left blank in the determinant below are zeros.
Click on the image for a step by step proof.
- Look at Wikipedia's Matrix page. It contains some stuff that we did and much that we didn't do.
-
Today in class we explored a problem inspired by the picture below. No numbers are given just the picture. In the picture below we are given two bases of $\mathbb{R}^2$, one blue and one purple:
\[
\color{blue}{\mathcal B} = \bigl\{ \color{blue}{\mathbf{b}_1}, \color{blue}{\mathbf{b}_2} \bigr\}, \quad \color{purple}{\mathcal C} = \bigl\{ \color{purple}{\mathbf{c}_1}, \color{purple}{\mathbf{c}_2} \bigr\}
\]
- Suggested exercises for Section 4.7: Change of Basis are 2, 3, 4, 6, 8, 9, 11, 12, 13, 14, 15, 16, 17, 19, 20.
-
A brief review of the Change of Coordinates Matrix (this is my preferred name) follows. Let $m, n \in \mathbb{N}$ and $m\leq n$. Let $\mathcal{H}$ be a subspace of $\mathbb{R}^n$ and let
\[
\mathcal{A} = \bigl\{\mathbf{a}_1,\ldots,\mathbf{a}_m\bigr\}
\]
and
\[
\mathcal{B} = \bigl\{\mathbf{b}_1,\ldots,\mathbf{b}_m\bigr\}
\]
be two bases of $\mathcal{H}.$ By definition of a basis this implies that
\[
\mathcal{H} = \operatorname{Span}\bigl\{\mathbf{a}_1,\ldots,\mathbf{a}_m\bigr\} = \operatorname{Span}\bigl\{\mathbf{b}_1,\ldots,\mathbf{b}_m\bigr\}
\]
and both
\[
\mathcal{A} = \bigl\{\mathbf{a}_1,\ldots,\mathbf{a}_m\bigr\} \quad \text{and} \quad \mathcal{B} = \bigl\{\mathbf{b}_1,\ldots,\mathbf{b}_m\bigr\}
\]
are linearly independent. We proved in class that the change of coordinates matrix $\displaystyle\underset{\mathcal{B}\leftarrow\mathcal{A}}{P}$ is given by
\[
\underset{\mathcal{B}\leftarrow\mathcal{A}}{P} = \Bigl[ \bigl[\mathbf{a}_1\bigr]_{\mathcal{B}} \ \cdots \ \bigl[ \mathbf{a}_m\bigr]_{\mathcal{B}} \Bigr]
\]
and analogously
\[
\underset{\mathcal{A}\leftarrow\mathcal{B}}{P} = \Bigl[ \bigl[\mathbf{b}_1\bigr]_{\mathcal{A}} \ \cdots \ \bigl[ \mathbf{b}_m\bigr]_{\mathcal{A}} \Bigr].
\]
But, how to calculate
\[
\bigl[\mathbf{a}_1\bigr]_{\mathcal{B}}, \ldots,\bigl[ \mathbf{a}_m\bigr]_{\mathcal{B}}?
\]
Let us look at
\[
\bigl[\mathbf{a}_1\bigr]_{\mathcal{B}} = \left[\!\begin{array}{c}
x_1 \\ \vdots \\ x_m
\end{array}\!\right].
\]
To find the real numbers $x_1, \ldots, x_m$ we have to solve the nonhomogeneous vector equation
\[
x_1 \mathbf{b}_1 + x_2 \mathbf{b}_2 + \cdots + x_m \mathbf{b}_m = \mathbf{a}_1.
\]
To solve the preceding equation we row reduce
\[
\Bigl[\!\begin{array}{cccc|c}
\mathbf{b}_1 & \mathbf{b}_2 & \cdots & \mathbf{b}_m & \mathbf{a}_1\end{array}\!\Bigr].
\]
Since the vectors $\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_m$ are linearly independent, the Reduced Row Echelon Form of the preceding augmented matrix has the following form
\[
\left[\!\begin{array}{cccc|c}
1 & 0 & \cdots & 0 & \text{the solution for} \ x_1 \\
0 & 1 & \cdots & 0 & \text{the solution for} \ x_2 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & 1 & \text{the solution for} \ x_m \\
0 & 0 & \cdots & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & 0 & 0
\end{array}\!\right].
\]
Notice that in the preceding matrix the bottom zero rows are present only in the case when $n \gt m.$ If $n \gt m$, then there are exactly $n-m$ rows of zeros. Also notice that the above system must be consistent since the vector $\mathbf{a}_1$ is in the span of the vectors $\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_m.$
To solve the nonhomogeneous vector equations \[ x_1 \mathbf{b}_1 + x_2 \mathbf{b}_2 + \cdots + x_m \mathbf{b}_m = \mathbf{a}_2, \quad \ldots, \quad x_1 \mathbf{b}_1 + x_2 \mathbf{b}_2 + \cdots + x_m \mathbf{b}_m = \mathbf{a}_m, \] we just build the bigger augmented matrix: \[ \Bigl[\!\begin{array}{cccc|cccc} \mathbf{b}_1 & \mathbf{b}_2 & \cdots & \mathbf{b}_m & \mathbf{a}_1 & \mathbf{a}_2 & \cdots & \mathbf{a}_m \end{array}\!\Bigr]. \] Since the vectors $\mathbf{b}_1, \ldots, \mathbf{b}_m$ are linearly independent, the RREF off the matrix whose columns are the vectors of $\mathcal{B}$ consists of the identity matrix $I_m$ and $n-m$ zero rows at the bottom if $n\gt m.$ Therefore \[ \Bigl[\!\begin{array}{ccc|ccc} \mathbf{b}_1 & \cdots & \mathbf{b}_m & \mathbf{a}_1 & \cdots & \mathbf{a}_m \end{array}\!\Bigr] \sim \cdots \sim \left[\! \begin{array}{c|c} I_m & \underset{\mathcal{B}\leftarrow\mathcal{A}}{P} \\ 0 & 0 \end{array} \!\right]. \] In the preceding RREF, the zero matrices at the bottom are present only if $n-m \gt 0.$ Then, if $n-m \gt 0,$ these matrices are of the size $(n-m)\!\times\!m;$ they both have $m$ columns and $n-m$ rows consisting of zeros. -
In the next example we are given two bases of a two-dimensional subspace of $\mathbb{R}^4$ and we are asked to find a change of coordinate matrices between these two bases:
\[
\mathcal{H} = \operatorname{Span}\left\{\left[\!\begin{array}{c}
1 \\ 2 \\ 1 \\ 3
\end{array}\!\right], \left[\!\begin{array}{c}
2 \\ 3 \\ 1 \\ 5
\end{array}\!\right]\right\} = \operatorname{Span}\left\{\left[\!\begin{array}{c}
2 \\ 5 \\ 3 \\ 7
\end{array}\!\right], \left[\!\begin{array}{r}
1 \\ 0 \\ -1 \\ 1
\end{array}\!\right]\right\}.
\]
Set
\[
\mathcal{A} = \left\{\left[\!\begin{array}{c}
1 \\ 2 \\ 1 \\ 3
\end{array}\!\right], \left[\!\begin{array}{c}
2 \\ 3 \\ 1 \\ 5
\end{array}\!\right]\right\}, \qquad \mathcal{B} = \left\{\left[\!\begin{array}{c}
2 \\ 5 \\ 3 \\ 7
\end{array}\!\right], \left[\!\begin{array}{r}
1 \\ 0 \\ -1 \\ 1
\end{array}\!\right]\right\}.
\]
To calculate $\displaystyle\underset{\mathcal{B}\leftarrow\mathcal{A}}{P}$ we need to row reduce the matrix
\[
\left[\!\begin{array}{cr|cc}
2 & 1 & 1 & 2 \\
5 & 0 & 2 & 3 \\
3 & -1 & 1 & 1 \\
7 & 1 & 3 & 5
\end{array}\!\right]
\]
The RREF of the preceding matrix will certainly include fractions. Therefore we rather find $\displaystyle\underset{\mathcal{A}\leftarrow\mathcal{B}}{P}$ for which we need to row reduce (without fractions)
\[
\left[\!\begin{array}{cc|cr}
1 & 2 & 2 & 1 \\
2 & 3 & 5 & 0 \\
1 & 1 & 3 & -1 \\
3 & 5 & 7 & 1
\end{array}\!\right] \sim \cdots \sim
\left[\!\begin{array}{cc|rr}
1 & 0 & 4 & -3 \\
0 & 1 & -1 & 2 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0
\end{array}\!\right].
\]
Hence
\[
\underset{\mathcal{A}\leftarrow\mathcal{B}}{P} = \left[\!\begin{array}{rr}
4 & -3 \\
-1 & 2
\end{array}\!\right].
\]
Let us verify this calculation. Is it true that:
\[
\left[\!\begin{array}{c}
2 \\ 5 \\ 3 \\ 7
\end{array}\!\right] = (4) \left[\!\begin{array}{c}
1 \\ 2 \\ 1 \\ 3
\end{array}\!\right] + (-1)\left[\!\begin{array}{c}
2 \\ 3 \\ 1 \\ 5
\end{array}\!\right], \qquad \left[\!\begin{array}{r}
1 \\ 0 \\ -1 \\ 1
\end{array}\!\right] = (-3) \left[\!\begin{array}{c}
1 \\ 2 \\ 1 \\ 3
\end{array}\!\right] + (2) \left[\!\begin{array}{c}
2 \\ 3 \\ 1 \\ 5
\end{array}\!\right]?
\]
Yes. Therefore the following equalites are correct:
\[
\bigl[ \mathbf{b}_1\bigr]_{\mathcal{A}} = \left[\!\begin{array}{r}
4 \\ -1
\end{array}\!\right], \qquad \bigl[ \mathbf{b}_2\bigr]_{\mathcal{A}} = \left[\!\begin{array}{r}
-3 \\ 2
\end{array}\!\right].
\]
Hence, $\displaystyle\underset{\mathcal{A}\leftarrow\mathcal{B}}{P}$ is correct.
We have \[ \underset{\mathcal{B}\leftarrow\mathcal{A}}{P} = \left(\underset{\mathcal{A}\leftarrow\mathcal{B}}{P}\right)^{-1} = \frac{1}{5} \left[\!\begin{array}{rr} 2 & 3 \\ 1 & 4 \end{array}\!\right]. \] Verify this: \[ \left[\!\begin{array}{c} 1 \\ 2 \\ 1 \\ 3 \end{array}\!\right] = \frac{2}{5}\left[\!\begin{array}{c} 2 \\ 5 \\ 3 \\ 7 \end{array}\!\right] + \frac{1}{5} \left[\!\begin{array}{r} 1 \\ 0 \\ -1 \\ 1 \end{array}\!\right], \qquad \left[\!\begin{array}{c} 2 \\ 3 \\ 1 \\ 5 \end{array}\!\right] = \frac{3}{5} \left[\!\begin{array}{c} 2 \\ 5 \\ 3 \\ 7 \end{array}\!\right] + \frac{4}{5} \left[\!\begin{array}{r} 1 \\ 0 \\ -1 \\ 1 \end{array}\!\right]. \] True. Therefore the following equalites are correct: \[ \bigl[ \mathbf{a}_1\bigr]_{\mathcal{B}} = \frac{1}{5}\left[\!\begin{array}{r} 2 \\ 1 \end{array}\!\right], \qquad \bigl[ \mathbf{a}_2\bigr]_{\mathcal{B}} = \frac{1}{5} \left[\!\begin{array}{r} 3 \\ 4 \end{array}\!\right]. \] Hence, $\displaystyle\underset{\mathcal{B}\leftarrow\mathcal{A}}{P}$ is correct.
- Yesterday in class I made an important claim: For an arbitrary matrix $A$ the only vector that belongs to both $\operatorname{Row}(A)$ and $\operatorname{Nul}(A)$ is the zero vector. Thinking back about my explanation for this claim that I gave in class was very convincing. Therefore I will provide a proper proof below. Before presenting this proof, I will review the facts about the four fundamental subspaces associated with a matrix $A.$
- Let $m, n \in \mathbb{N}.$ Let $A$ be an $m\!\times\!n$ matrix. The matrix $A$ has $m$ rows and $n$ columns. The columns of $A$ are vectors in $\mathbb{R}^m.$ The transpose of $A$, denoted by $A^\top,$ is an $n\!\times\!m$ matrix. The matrix $A^\top$ has $n$ rows and $m$ columns. The columns of $A^\top$ are vectors in $\mathbb{R}^n.$ The columns of $A^\top$ have the identical entries as the rows of $A,$ just instead of being in rows they are written as columns. The four fundamental subspaces associated with the matrix $A$ are \begin{alignat*}{2} \operatorname{Col}(A) & = \operatorname{Row}(A^\top) \quad & & \left\{ \begin{array}{l} \text{this space is the span of the columns of} \ \ A \\ \text{this space is a subspace of} \ \ \mathbb{R}^m, \ \text{since each column of $A$ is a vector in} \ \mathbb{R}^m \end{array} \right. \\ \operatorname{Row}(A) &= \operatorname{Col}(A^\top) \quad & & \left\{ \begin{array}{l} \text{this space is the span of the columns of} \ A^\top \\ \text{this space is a subspace of} \ \ \mathbb{R}^n, \ \text{since each column of $A^\top$ is a vector in} \ \mathbb{R}^n \end{array} \right. \\ \operatorname{Nul}(A) & = \bigl\{ \mathbf{x} \in \mathbb{R}^n \, : \, & & A\mathbf{x} = \mathbf{0}_m \bigr\} \quad \text{this space is a subspace of} \ \ \mathbb{R}^n, \\ \operatorname{Nul}(A^\top) & = \bigl\{ \mathbf{y} \in \mathbb{R}^m \, : \, & & A^\top\mathbf{y} = \mathbf{0}_n \bigr\} \quad \text{this space is a subspace of} \ \ \mathbb{R}^m \end{alignat*} Thus \begin{equation*} \bbox[lightgreen, 6px, border:3px solid green]{ \begin{array}{cll} \operatorname{Col}(A) = \operatorname{Row}(A^\top) \quad & \text{and} \quad \operatorname{Nul}(A^\top) \quad & \text{are subspaces of} \quad \mathbb{R}^m \\ \operatorname{Row}(A) = \operatorname{Col}(A^\top) \quad & \text{and} \quad \operatorname{Nul}(A) \quad & \text{are subspaces of} \quad \mathbb{R}^n \end{array} } \end{equation*}
-
The green boxed statement in the preceding item is even more interesting combined with the following theorem:
-
Step 1.
By the definition of intersection
\[
\operatorname{Row}(A) \cap \operatorname{Nul}(A)
\]
consists of all vectors which belong to both $\operatorname{Row}(A)$ and $\operatorname{Nul}(A).$ Let $\mathbf{x} \in \mathbb{R}^n$ be such that
\[
\mathbf{x} \in \operatorname{Row}(A) \quad \text{and} \quad \mathbf{x} \in \operatorname{Nul}(A).
\]
Since we know that $\operatorname{Row}(A) = \operatorname{Col}(A^\top)$ we deduce that $\mathbf{x} \in \operatorname{Col}(A^\top).$ Therefore, there exists $\mathbf{y} \in \mathbb{R}^m$ such that
\[
\mathbf{x} = A^\top \mathbf{y}.
\]
Since $\mathbf{x} \in \operatorname{Nul}(A)$ we know that $A\mathbf{x} = \mathbf{0}_m.$ The preceding two equalities yield
\[
A\bigl(A^\top \mathbf{y}\bigr) = \mathbf{0}_m.
\]
-
Step 2.
Think of the vector $\mathbf{y} \in \mathbb{R}^m$ as being an $m\!\times\!1$ matrix. Since $A\bigl(A^\top \mathbf{y}\bigr)$ is also an $m\!\times\!1$ matrix, we can multiply $\mathbf{y}^\top$, it is an $1\!\times\!m$ matrix, and the $m\!\times\!1$ matrix $A\bigl(A^\top \mathbf{y}\bigr).$ The result will be $1\!\times\!1$ matrix which we identify with a number:
\[
\mathbf{y}^\top\bigl(A\bigl(A^\top \mathbf{y}\bigr)\bigr) = \mathbf{y}^\top \mathbf{0}_m = 0.
\]
Since matrix multiplication is associative we can write
\[
\bigl( \mathbf{y}^\top A\bigr) \bigl(A^\top \mathbf{y}\bigr) = 0.
\]
-
Step 3.
Recall the rules about matrix transpose:
\[
\bigl( A^\top \mathbf{y}\bigr)^\top = \mathbf{y}^\top A.
\]
Substituting this in the equality preceding the last one, we get
\[
\bigl( A^\top \mathbf{y}\bigr)^\top \bigl(A^\top \mathbf{y}\bigr) = 0.
\]
Now recall that $\mathbf{x} = A^\top \mathbf{y}.$ Thus we proved that
\[
\mathbf{x}^\top \mathbf{x} = 0.
\]
-
Step 4.
Now calculate $\mathbf{x}^\top \mathbf{x}$:
\[
\mathbf{x}^\top \mathbf{x} = \bigl[ x_1 \ x_2 \ \cdots \ x_n \bigr] \left[\begin{array}{c}
x_1 \\ x_2 \\ \vdots \\ x_n \end{array}\right] = (x_1)^2 + (x_2)^2 + \cdots + (x_n)^2.
\]
Since we proved that $\mathbf{x}^\top \mathbf{x} = 0$, we deduce
\[
(x_1)^2 + (x_2)^2 + \cdots + (x_n)^2 = 0.
\]
Since $ (x_k)^2 \geq 0$ for all $k \in \{1,\ldots,n\}$ we deduce that
\[
x_1 = 0, \ \ x_2 = 0, \ \ \ldots, \ \ x_n = 0.
\]
Hence $\mathbf{x} = \mathbf{0}_n.$
-
Step 5.
Thus we proved
\[
\mathbf{x} \in \operatorname{Row}(A) \ \ \text{and} \ \ \mathbf{x} \in \operatorname{Nul}(A) \quad \Rightarrow \quad \mathbf{x} = \mathbf{0}_n.
\]
Since clearly $\mathbf{0}_n \in \operatorname{Row}(A)$ and $\mathbf{0}_n \in \operatorname{Nul}(A)$, we have proved that $\mathbf{0}_n$ is the only vector which is in both subspaces $\operatorname{Row}(A)$ and $\operatorname{Nul}(A).$
- QED. The end of the proof.
-
Step 1.
By the definition of intersection
\[
\operatorname{Row}(A) \cap \operatorname{Nul}(A)
\]
consists of all vectors which belong to both $\operatorname{Row}(A)$ and $\operatorname{Nul}(A).$ Let $\mathbf{x} \in \mathbb{R}^n$ be such that
\[
\mathbf{x} \in \operatorname{Row}(A) \quad \text{and} \quad \mathbf{x} \in \operatorname{Nul}(A).
\]
Since we know that $\operatorname{Row}(A) = \operatorname{Col}(A^\top)$ we deduce that $\mathbf{x} \in \operatorname{Col}(A^\top).$ Therefore, there exists $\mathbf{y} \in \mathbb{R}^m$ such that
\[
\mathbf{x} = A^\top \mathbf{y}.
\]
Since $\mathbf{x} \in \operatorname{Nul}(A)$ we know that $A\mathbf{x} = \mathbf{0}_m.$ The preceding two equalities yield
\[
A\bigl(A^\top \mathbf{y}\bigr) = \mathbf{0}_m.
\]
-
The theorem proved in the preceding item is essential to proving the following theorem:
-
I am very proud of the theorem that I stated at the end of the post yesterday. The theorem is completely in English, no symbols at all.
-
The above theorem restated using mathematical notation and colors to distinguish between the assumptions and the claim.
Theorem Let $n, p, q \in \mathbb{N}.$ Let $P$ be an $n\!\times\!p$ matrix and let $Q$ be an $n\!\times\!q$ matrix. If \begin{equation*} \bbox[lightgreen, 6px, border:3px solid green]{\operatorname{Col}(P) = \operatorname{Col}(Q)} \quad \text{and} \quad \bbox[lightgreen, 4px, border:3px solid green]{\text{the columns of} \ \ P \ \ \text{are linearly independent},} \end{equation*} then \begin{equation*} \bbox[#FFC0C0, 6px, border:3px solid red]{p\leq q}. \end{equation*}
- Suggested problems related to $\operatorname{Col}(A)$ and $\operatorname{Nul}(A)$ of a given matrix $A$ from Section 4.5 are: 3, 6, 12, 13, 15, 18.
- More problems about $\operatorname{Col}(A)$, $\operatorname{Row}(A)$ and $\operatorname{Nul}(A)$ of a given matrix $A$ are in Section 4.6: 3, 4, 5, 6, 7, 8, 9, 11, 13, 15, 17, 18, 27, 28, 29.
- Today we did Section 2.9 Dimension and Rank; suggested problems for Section 2.9: 1, 2, 3, 5, 6, 7, 9, 11, 12, 14, 15, 19, 20, 21, 23, 24, and in particular 27 and 28.
-
Before giving the definition of the dimansion the textbook has the following paragraph:
It can be shown that if a subspace H has a basis of p vectors, then every basis of H must consist of exactly p vectors. (See Exercises 27 and 28.) Thus the following definition makes sense.Since this theorem is essential for everything that is done in linear algebra we will prove it below. The proof is slightly different from what is suggested in Exercises 27 and 28 in the textbook. The proof is long, but I tried to make it clear. I tried to justify every step. If there is still something that needs an explanation please let me know.
-
Theorem If the following three assumptions are satisfied:
- A1. $n, m, k \in \mathbb{N},$ $\mathcal{H}$ is a subspace of $\mathbb{R}^n$,
- A2. Vectors $\mathbf{a}_1, \ldots, \mathbf{a}_k$ form a basis for $\mathcal{H}$, (notice that there are $k$ vectors in this basis)
- A3. Vectors $\mathbf{b}_1, \ldots, \mathbf{b}_m$ form a basis for $\mathcal{H}$, (notice that there are $m$ vectors in this basis)
- C. $m=k$.
The proof starts here.-
Step 1. We introduce the $n\!\times\!k$ matrix $A$ whose columns are the vectors $\mathbf{a}_1, \ldots, \mathbf{a}_k$ and the $n\!\times\!m$ matrix $B$ whose columns are the vectors $\mathbf{b}_1, \ldots, \mathbf{b}_m$:
\[
A = \bigl[ \mathbf{a}_1 \ \cdots \ \mathbf{a}_k \bigr], \qquad B = \bigl[ \mathbf{b}_1 \ \cdots \ \mathbf{b}_m \bigr].
\]
-
Step 2. We translate assumption A2. in terms of the matrix $A$. Since we assume that
\[
\mathcal{H} = \operatorname{Span} \bigl\{ \mathbf{a}_1, \ldots, \mathbf{a}_k \bigr\}
\]
and since the vectors $\mathbf{a}_1, \ldots, \mathbf{a}_k$ are the columns of $A$, we deduce that
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{\mathcal{H} = \operatorname{Col}(A)}
\end{equation*}
Since we assume that the vectors $\mathbf{a}_1, \ldots, \mathbf{a}_k$ are linearly independent, we deduce that the equation $A\mathbf{x} = \mathbf{0}$ has only the trivial solution. Therefore the following implication holds
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{A\mathbf{x} = \mathbf{0}_n \quad \Rightarrow \quad \mathbf{x} = \mathbf{0}_k.}
\end{equation*}
-
Step 3. We translate assumption A3 in terms of the matrix $B$. Since we assume that
\[
\mathcal{H} = \operatorname{Span} \bigl\{ \mathbf{b}_1, \ldots, \mathbf{b}_m \bigr\}
\]
and since the vectors $\mathbf{b}_1, \ldots, \mathbf{b}_m$ are the columns of $B$, we deduce that
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{\mathcal{H} = \operatorname{Col}(B).}
\end{equation*}
Since we assume that the vectors $\mathbf{b}_1, \ldots, \mathbf{b}_m$ are linearly independent, we deduce that the equation $B\mathbf{y} = \mathbf{0}_n$ has only the trivial solution. Therefore the following implication holds
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{B\mathbf{y} = \mathbf{0}_n \quad \Rightarrow \quad \mathbf{y} = \mathbf{0}_m.}
\end{equation*}
-
Step 4. From Step 2 and Step 3 we know that
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{\operatorname{Col}(A) = \operatorname{Col}(B)}.
\end{equation*}
The preceding green box implies that $\bbox[lightgreen, 6px, border:3px solid green]{\mathbf{b}_1 \in \operatorname{Col}(A)}$. Therefore there exists $\mathbf{c}_1 \in \mathbb{R}^k$ such that $\mathbf{b}_1 = A\mathbf{c}_1$. Similarly, there exists $\mathbf{c}_2 \in \mathbb{R}^k$ such that $\mathbf{b}_2 = A\mathbf{c}_2$, and so on, there exists $\mathbf{c}_m \in \mathbb{R}^k$ such that $\mathbf{b}_m = A\mathbf{c}_m$. We introduce the $k\!\times\!m$ matrix $C$ whose columns are $\mathbf{c}_1, \ldots, \mathbf{c}_m$:
\[
C = \bigl[ \mathbf{c}_1 \ \cdots \ \mathbf{c}_m \bigr].
\]
Then we have
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{B = \bigl[ \mathbf{b}_1 \ \cdots \ \mathbf{b}_m \bigr] = \bigl[ A\mathbf{c}_1 \ \cdots \ A \mathbf{c}_m \bigr] = A \bigl[ \mathbf{c}_1 \ \cdots \ \mathbf{c}_m \bigr] = AC.}
\end{equation*}
That is $\bbox[lightgreen, 6px, border:3px solid green]{B = AC.}$
-
Step 5. From Step 4 we know that there exists $k\!\times\!m$ matrix $C$ such that $\bbox[lightgreen, 6px, border:3px solid green]{B = AC.}$ From Step 3 we know that
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{B\mathbf{y} = \mathbf{0}_n \quad \Rightarrow \quad \mathbf{y} = \mathbf{0}_m.}
\end{equation*}
Now we will prove the implication
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{B = AC} \ \ \text{and} \ \
\bbox[lightgreen, 6px, border:3px solid green]{B\mathbf{y} = \mathbf{0}_n \ \Rightarrow \ \mathbf{y} = \mathbf{0}_m} \quad \Rightarrow \quad \bbox[#FFC0C0, 6px, border:3px solid red]{C\mathbf{y} = \mathbf{0}_k \quad \Rightarrow \quad \mathbf{y} = \mathbf{0}_m.}
\end{equation*}
In plain English the previous implication says: If $B = AC$ and the columns of $B$ are linearly independent, then the columns of $C$ are linearly independent.
Assume that $\bbox[lightgreen, 6px, border:3px solid green]{C\mathbf{y} = \mathbf{0}_k}$ for some $\mathbf{y} \in \mathbb{R}^m$. Then, $\bbox[lightgreen, 6px, border:3px solid green]{AC\mathbf{y} = A\mathbf{0}_k = \mathbf{0}_n}$. Since $\bbox[lightgreen, 6px, border:3px solid green]{B = AC}$, we conclude that $\bbox[lightgreen, 6px, border:3px solid green]{B\mathbf{y} = \mathbf{0}_n}$. Since
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{B\mathbf{y} = \mathbf{0}_n \quad \Rightarrow \quad \mathbf{y} = \mathbf{0}_m}
\end{equation*}
we deduce that $\bbox[lightgreen, 6px, border:3px solid green]{\mathbf{y} = \mathbf{0}_m}.$ Thus, we proved
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{C\mathbf{y} = \mathbf{0}_k \quad \Rightarrow \quad \mathbf{y} = \mathbf{0}_m.}
\end{equation*}
The preceding implication means that the columns of the $k\!\times\!m$ matrix $C$ are linearly independent. Therefore all columns of $C$ are pivot columns. Since each pivot occupies one row in the RREF of $C$, we deduce that $C$ cannot have more columns than rows. Thus, we proved $\bbox[lightgreen, 6px, border:3px solid green]{m\leq k}.$
-
Step 6. In Step 4 and Step 5 we proved: If $A$ is an $n\!\times\!k$ matrix, $B$ is an $n\!\times\!m$ matrix and
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{\operatorname{Col}(A) = \operatorname{Col}(B)} \quad \text{and} \quad \bbox[lightgreen, 6px, border:3px solid green]{B\mathbf{y} = \mathbf{0}_n \quad \Rightarrow \quad \mathbf{y} = \mathbf{0}_m,}
\end{equation*}
then
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{m\leq k}.
\end{equation*}
-
Step 7. From Step 2 and Step 3 we know that
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{\operatorname{Col}(A) = \operatorname{Col}(B)}
\end{equation*}
and from the Step 2 we know that
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{A\mathbf{x} = \mathbf{0}_n \quad \Rightarrow \quad \mathbf{x} = \mathbf{0}_k.}
\end{equation*}
Looking at the preciding two green boxes and the assumptions in Step 6 we notice that the only difference is that the matrices $A$ and $B$ exchanged roles. Therefore, based on Step 6 we deduce that
\begin{equation*}
\bbox[lightgreen, 6px, border:3px solid green]{k\leq m}.
\end{equation*}
-
Step 8. In Step 5 we proved
$
\bbox[lightgreen, 6px, border:3px solid green]{k\leq m}.
$
In Step 7 we proved
$
\bbox[lightgreen, 6px, border:3px solid green]{m\leq k}.
$
Therefore
$
\bbox[lightgreen, 6px, border:3px solid green]{k = m}.
$
- QED. The end of the proof.
-
Now that I have written the above proof, I think that I should have started with a theorem about matrices that we summarized in Step 6 above. That theorem goes as follows:
Theorem Let $n, p, q \in \mathbb{N}.$ Let $P$ be an $n\!\times\!p$ matrix and let $Q$ be an $n\!\times\!q$ matrix. If \begin{equation*} \bbox[lightgreen, 6px, border:3px solid green]{\operatorname{Col}(P) = \operatorname{Col}(Q)} \quad \text{and} \quad \bbox[lightgreen, 6px, border:3px solid green]{\text{the columns of} \ \ P \ \ \text{are linearly independent},} \end{equation*} then \begin{equation*} \bbox[#FFC0C0, 6px, border:3px solid red]{p\leq q}. \end{equation*} End of ThoremOr stated completely in English:
Theorem If two matrices have the same column space and one of them has linearly independent columns, then the matrix with linearly independent columns has no more columns than the other matrix. In particular, if two matrices have the same column space and both matrices have linearly independent columns, then the matrices are of the same size.
- For tomorrow, Section 2.9 Dimension and Rank. Suggested problems for Section 2.9: 1, 2, 3, 5, 6, 7, 9, 11, 12, 14, 15, 19, 20, 21, 23, 24.
- Below I show two examples of coordinate systems. The first one is in $\mathbb{R}^2$ and the second one is a coordinate system in a plane in $\mathbb{R}^3.$
-
Please enjoy my
- Is it appropriate to use the word magic in math lectures, or in math context in general?
-
This item is just a comment on how to make a matrix in Reduced Row Echelon Form. For example, $5\!\times\!7$ matrix in Reduced Row Echelon Form:
- First chose how many pivot columns we want. Recall that the pivot columns are the columns of the identity matrix \[ I_5 = \left[\!\begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array}\!\right] \] The number of pivot columns must be smaller or equal than both $5$ and $7.$ Let us choose $3$ pivot columns. These must be the first three columns of the identity matrix $I_5:$ \[ \require{bbox} \left[\! \begin{array}{rrrrr} \bbox[yellow]{\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}} & \bbox[yellow]{\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{array}} & \bbox[yellow]{\begin{array}{r} 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{array}} & \bbox[white]{\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \\ 0 \end{array}} & \bbox[white]{\begin{array}{c} 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{array}} \end{array} \!\right] \]
- Now choose the positions in $5\!\times\!7$ matrix where we want these pivot columns placed. We just need to chose three numbers from $\{1,2,3,4,5,6,7\}.$ There are \[ \binom{7}{3} = \frac{7!}{3!\, 4!} = \frac{5\cdot 6 \cdot 7}{1\cdot 2\cdot 3} = 35 \] ways to choose, from $\{1,2,3\},$ $\{1,2,4\},$ $\{1,2,5\},$ $\{1,2,6\},$ $\{1,2,7\},$ $\{1,3,4\},$ all the way to $\{5,6,7\}.$ Let us choose $\{2,4,5\}$ and place the chosen columns at those positions: \[ \require{bbox} \left[\! \begin{array}{rrrrrrr} \bbox[#FF8888]{\begin{array}{c} ? \\ ? \\ ? \\ ? \\ ? \end{array}} & \bbox[yellow]{\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}} & \bbox[#FF8888]{\begin{array}{c} ? \\ ? \\ ? \\ ? \\ ? \end{array}} & \bbox[yellow]{\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{array}} & \bbox[yellow]{\begin{array}{r} 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{array}} & \bbox[#FF8888]{\begin{array}{c} ? \\ ? \\ ? \\ ? \\ ? \end{array}} & \bbox[#FF8888]{\begin{array}{c} ? \\ ? \\ ? \\ ? \\ ? \end{array}} \end{array}\!\right] \]
- Next we recall that the ones ($1$s) in the pivot columns are leading entries in their rows. Thus we place all zeros before those ones. Also we place all zeros at the bottom of the matrix. \[ \require{bbox} \left[\! \begin{array}{rrrrrrr} \begin{array}{c} \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \end{array} & \bbox[yellow]{\begin{array}{c} 1 \\ \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \end{array}} & \begin{array}{c} \bbox[lightblue]{?} \\ \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \end{array} & \bbox[yellow]{\begin{array}{c} 0 \\ 1 \\ \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \end{array}} & \bbox[yellow]{\begin{array}{r} 0 \\ 0 \\ 1 \\ \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \end{array}} & \begin{array}{c} \bbox[lightblue]{?} \\ \bbox[lightblue]{?} \\ \bbox[lightblue]{?} \\ \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \end{array} & \begin{array}{c} \bbox[lightblue]{?} \\ \bbox[lightblue]{?} \\ \bbox[lightblue]{?} \\ \bbox[#88FF88]{0} \\ \bbox[#88FF88]{0} \end{array} \end{array}\!\right] \]
- That is it! The above matrix is in Reduced Row Echelon Form where $\require{bbox}\bbox[lightblue]{?}$ stands for any real number.
- You can use the above method to test whether a matrix is in RREF: I. Recognize the pivot columns. II. Test whether the pivot columns are the consecutive columns of an identity matrix. III. Test whether $1$s from the pivot columns are the leading entries in their rows. IV. All rows that do not have $1$s from the pivot columns must consist of zeros only.
-
You might be asking yourself why I write so much. The answer is that I find writing a beautiful conduit to learn. So, I would like to encourage you to incorporate writing into your learning. Inspired by a Latin phrase, I wrote the following words to celebrate writing:
I came, I thought, I wrote, I taught, I thought more, I rewrote.
The Latin phrase "veni, vidi, vici" inspired the above words. Incidentally, in the list of Latin phrases "veni, vidi, vici" is very close to another Latin phrase celebrating writing:
Verba volant, scripta manent.
(Spoken words fly away, written words stay.)
- To understand the concepts of the column space, the row space, and the null space of a matrix and their bases please study posts on October 9 and the follow-up on October 21.
- Today we did Section 2.8 Subspaces of $\mathbb{R}^n.$ Suggested problems for Section 2.8: 5, 6, 8, 9, 10, 11-20, 24, 25, 26, 30, 31-36.
- Today we further celebrated Section 2.3 Characterizations of invertible matrices. It is a good idea to review Problems 23, 24, 25 from Section 2.1 before reading this section. Suggested problems for Section 2.3: 1, 3, 5, 8, 11, 12, 13, 15, 16, 17, 18, 19, 20, 21, 26, 27, 33.
-
Almost all mathematical statements can be stated as implications. A symbolic way to represent an implication is $p \Rightarrow q$, where $p$ and $q$ are mathematical statements. There are many ways to say $p \Rightarrow q$ in English.
- If $p$, then $q$.
- $q$ if $p$.
- $p$ is sufficient for $q$.
- $q$ is necessary for $p$.
- A sufficient condition for $q$ is $p$.
- A necessary condition for $p$ is $q$.
- $p$ implies $q$.
- $p$ only if $q$.
- $q$ whenever $p$.
- $q$ follows from $p$.
-
Recall that the contrapositive of the implication $p \Rightarrow q$ is the implication $\neg q \Rightarrow \neg p$; where $\neg p$ stands for the negation of $p$ and $\neg q$ stands for the negation of $q$. This is exceptionally important to understand: The contrapositive is equivalent to the original implication. The easiest way to prove this claim is to look at the negations of $p \Rightarrow q$ and its contrapositive $\neg q \Rightarrow \neg p$.
The negation of $p \Rightarrow q$ is $p \land \neg q$.
The negation of $\neg q \Rightarrow \neg p$ is $\neg q \land p$.
For completenes, I emphasise that in the reasoning that $\neg q \land p$ is the negation of the contrapositive I used the fact that the statement $\neg(\neg p)$ is equivalent to $p.$ - Recall that the converse of the implication $p \Rightarrow q$ is the implication $q \Rightarrow p$. Also recall that the converse can be false when the original implication is true, like in my favorite example "If it rains, then the Red Square is wet." Like with all things in life, this validity of this statement is debatable (but I would argue that it is expensive to make this statement false). However, the converse is definitely not true. It is easy to make the converse false. However, I do not recommend that we do that without the approval of the Red Square authorities.
-
All this logic introduction is for the better understanding of the Invertible Matrix Theorem. For easier comprehention of the
twelve parts of the Invertible Matrix Theorem I created this picture
For a bigger picture of the whiteboard today click here.
-
Now proof of the implication (g)$\Rightarrow$(c). That is we need to prove:
If for all $\mathbf{b} \in \mathbb{R}^n$ the matrix equation $A\mathbf{x} = \mathbf{b}$ is consistent, then $A$ has $n$ pivot columns.
I will prove the contrapositive:If $A$ has $m$ pivot columns and $m \lt n$, then there exists $\mathbf{b} \in \mathbb{R}^n$ such that $A\mathbf{x} = \mathbf{b}$ is not consistent.
Proof.- Step 1. Assume that $A$ has $m$ pivot columns and $m \lt n.$ Then there are $m$ pivot positions in the RREF of $A.$ Since each pivot position occupies its own row, there are $m$ rows in the RREF of $A$ which contain pivot positions. The rows which contain the pivot positions are at the top of the RREF of $A.$ The remaining rows at the bottom of the RREF of $A$ are zero rows. Since $m \lt n$, the bottom row of the RREF of $A$ is a zero row.
- Step 2. Let $q \in\mathbb{N}.$ Assume that the RREF of $A$ has been obtained by performing $q$ row operations. Denote by $E_1,\ldots,E_q$ the corresponding elementary matrices. Then The matrix $E_q \cdots E_1 A$ is the RREF of $A$.
- Step 3. From Step 2 and Step 1 we conclude that The bottom row of the matrix $E_q \cdots E_1 A$ is the zero row. Therefore, The matrix equation $(E_q \cdots E_1 A) \mathbf{x} = \mathbf{e}_{n,n}$ is not consistent.
- Step 4. We know that changing a system of linear equations by performing row operations does not change the solution set of linear system. Therefore, the matrix equation $(E_q \cdots E_1 A) \mathbf{x} = \mathbf{e}_{n,n}$ and the matrix equation $ A \mathbf{x} = (E_1)^{-1} \cdots (E_q)^{-1}\mathbf{e}_{n,n}$ have the same solution set.
- Step 5. From Step 3 and Step 4 we deduce that the matrix equation $A \mathbf{x} = (E_1)^{-1} \cdots (E_q)^{-1}\mathbf{e}_{n,n}$ is not consistent.
- Step 6. From Step 5 we deduce that there exists $\mathbf{b} = (E_1)^{-1} \cdots (E_q)^{-1}\mathbf{e}_{n,n} \in \mathbb{R}^n$ such that the matrix equation $A \mathbf{x} = \mathbf{b}$ is not consistent.
- QED.
- I did not check how the textbook proves (g)$\Rightarrow$(c). The above proof that I gave is definitely not a blue proof. It should also be orange.
- I think that the best way to prove the implication (d)$\Rightarrow$(c) is to prove its contrapositive. You can try this proof on your own. I think that it is a blue proof.
- Today we did preliminaries for Section 2.3 Characterizations of invertible matrices. It is a good idea to review Exercises 23, 24, 25 from Section 2.1 before reading this section. Suggested problems for Section 2.3: 1, 3, 5, 8, 11, 12, 13, 15, 16, 17, 18, 19, 20, 21, 26, 27, 33.
- Recall the row reduction that we posted yesterday to find the inverse of $\displaystyle \left[\!\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 2 & 1 \\ -1 & 1 & 1 \end{array}\right]$: \begin{align*} \left[\!\begin{array}{rrr|rrr} 1 & 0 & -1 & 1 & 0 & 0 \\ 0 & 2 & 1 & 0 & 1 & 0 \\ -1 & 1 & 1 & 0 & 0 & 1 \end{array}\right] & \sim \left[\!\begin{array}{rrr|rrr} 1 & 0 & -1 & 1 & 0 & 0 \\ 0 & 2 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \end{array}\right] \\ & \sim \left[\!\begin{array}{rrr|rrr} 1 & 0 & -1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 2 & 1 & 0 & 1 & 0 \end{array}\right] \\ & \sim \left[\!\begin{array}{rrr|rrr} 1 & 0 & -1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & -2 & 1 & -2 \end{array}\right] \\ & \sim \left[\!\begin{array}{rrr|rrr} 1 & 0 & 0 & -1 & 1 & -2 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & -2 & 1 & -2 \end{array}\right] \\ \end{align*}
-
Now recall that each step in a row reduction can be achieved by multiplication by an elementary matrix.
Step the row operation the elementary matrix the inverse of elementary matrix 1st The third row is replaced by the the sum of the first row and the third row $E_1 = \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{array}\right]$ $E_1^{-1} = \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{array}\right]$ 2nd The third row and the second row are interchanged $E_2 = \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array}\right]$ $E_2^{-1} = \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array}\right]$ 3rd The third row is replaced by the the sum of the third row and the second row multiplied by $(-2)$ $E_3 = \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{array}\right]$ $E_3^{-1} = \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 2 & 1 \end{array}\right]$ 4th The first row is replaced by the the sum of the first row and the third row $E_4 = \left[\!\begin{array}{rrr} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right]$ $E_4^{-1} = \left[\!\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right]$ - Next we use the elementary matrices $E_1$, $E_2$, $E_3$ and $E_4$ to reconstruct the row reduction above: \begin{align*} E_1 A & = \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{array}\right] \left[\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 2 & 1 \\ -1 & 1 & 1 \end{array}\right] = \left[\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 2 & 1 \\ 0 & 1 & 0 \end{array}\right], \\ E_2 (E_1 A) & = \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array}\right] \left[\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 2 & 1 \\ 0 & 1 & 0 \end{array}\right] = \left[\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 1 & 0\\ 0 & 2 & 1 \end{array}\right], \\ E_3 (E_2 E_1 A) & =\left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{array}\right] \left[\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 1 & 0\\ 0 & 2 & 1 \end{array}\right] = \left[\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 1 & 0\\ 0 & 0 & 1 \end{array}\right], \\ E_4 (E_3 E_2 E_1 A) & = \left[\!\begin{array}{rrr} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right] \left[\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 1 & 0\\ 0 & 0 & 1 \end{array}\right] = \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right]. \end{align*}
- Since matrix multiplication is associative, we have \[ (E_4 E_3 E_2 E_1) A = I_3. \]
- The reason that I wrote all the above detailed steps is to show that we can write $A$ as a product of elementary matrices. Recall the preceding equality: \[ (E_4 E_3 E_2 E_1) A = I_3. \] Multiplying the last equality consecutively by $E_4^{-1}$, $E_3^{-1}$, $E_2^{-1}$, $E_1^{-1}$ we get \[ A = E_1^{-1} E_2^{-1} E_3^{-1} E_4^{-1}. \] Let us verify this claim: \begin{align*} E_4^{-1}& = \left[\!\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right], \\ E_3^{-1} E_4^{-1} & = \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 2 & 1 \end{array}\right] \left[\!\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right] = \left[\!\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 1 & 0 \\ 0 & 2 & 1 \end{array}\right], \\ E_2^{-1} \bigl(E_3^{-1} E_4^{-1}\bigr) & =\left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array}\right] \left[\!\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 1 & 0 \\ 0 & 2 & 1 \end{array}\right] = \left[\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 2 & 1 \\ 0 & 1 & 0 \end{array}\right], \\ E_1^{-1} \bigl(E_2^{-1} E_3^{-1} E_4^{-1}\bigr) & = \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{array}\right] \left[\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 2 & 1 \\ 0 & 1 & 0 \end{array}\right] = \left[\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 2 & 1 \\ -1 & 1 & 1 \end{array}\right]. \end{align*} Thus, we confirmed that \[ A = \left[\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 2 & 1 \\ -1 & 1 & 1 \end{array}\right] = \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{array}\right] \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array}\right] \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 2 & 1 \end{array}\right] \left[\!\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right] \]
-
The importance of the preceding item is that we found an expression for the matrix $A$ as a product of elementary matrices. In fact, the reasoning presented above for a specific $3\!\times\!3$ matrix $A$ holds for an arbitrary $n\!\times\!n$ matrix $A$ which can be row reduced to the identity matrix $I_n.$ The above reasoning is used as a model for a proof of the following important implication:
If Reduced Row Echelon Form of $A$ is $I_n$, then $A$ is invertible.
This implication is proved in Theorem 7 in Section 2.2. -
After reading this post you should be able to solve a problem stated as follows:
Consider the matrix $M = \left[\begin{array}{rrr} 3 & 3 & 2 \\ 3 & 2 & 1 \\ 2 & 1 & 0 \end{array}\right]$.
- Determine whether it is possible to write the matrix $M$ as a product of elementary matrices.
- If you claim that it is possible to write $M$ as a product of elementary matrices, then find elementary matrices whose product is $M$. If you claim that it is not possible to write $M$ as a product of elementary matrices, justify your answer.
- Today we started Section 2.2: The inverse of a matrix; suggested problems are: 1, 4, 5, 7, 12, 13, 21, 22, 23, 24, 28, 32, 33, 34, 38. In all bold face problems the textbook asks you to "explain why" something is true. In the text of the book and in class we offer proofs. Please try to organize your solutions as proofs, not explanations. State clearly what is known from theorems in the book and use logical reasoning to deduce what the problem claims.
-
My approach to the inverse of a $2\!\times\!2$ matrix is a little different from the approach in the textbook. I look at the process of seeking: Given a $2\!\times\!2$ matrix $\displaystyle \left[\!\begin{array}{cc}
a & b \\ c & d \end{array}\!\right]$ we seek another $2\!\times\!2$ matrix $\displaystyle \left[\!\begin{array}{cc}
x & y \\ z & w \end{array}\!\right]$ such that
\[
\left[\!\begin{array}{cc}
a & b \\ c & d \end{array}\!\right]\left[\!\begin{array}{cc}
x & y \\ z & w \end{array}\!\right] = \left[\!\begin{array}{cc}
ax+bz & ay+bw \\ cx+dz & cy+dw \end{array}\!\right] = \left[\!\begin{array}{cc}
1 & 0 \\ 0 & 1 \end{array}\!\right].
\]
At the first step we focus on the zeros and seek $y$ and $w$ such that $ay+bw = 0$, and $x$ and $z$ such that $cx+dz = 0.$
One of the simplest solution of $ay+bw = 0$ is $a(-b)+b\,a = 0$ and one of the simplest solution of $cx+dz = 0$ is $c\,d+d(-b) = 0.$ (This might take some guessing since you have another choice of $c(-d)+d\,b = 0.$) Now try $\displaystyle \left[\!\begin{array}{cc}
d & -b \\ -c & a \end{array}\!\right]$:
\[
\left[\!\begin{array}{cc}
a & b \\ c & d \end{array}\!\right]\left[\!\begin{array}{cc}
d & -b \\ -c & a \end{array}\!\right] = \left[\!\begin{array}{cc}
ad-bc & 0 \\ 0 & c(-b)+da \end{array}\!\right] = (ad-bc) \left[\!\begin{array}{cc}
1 & 0 \\ 0 & 1 \end{array}\!\right].
\]
From the last equality we see that if $ad-bc \neq 0$, then the matrix $\displaystyle \left[\!\begin{array}{cc}
a & b \\ c & d \end{array}\!\right]$ is invertible and its inverse is
\[
\displaystyle \left[\!\begin{array}{cc}
a & b \\ c & d \end{array}\!\right]^{-1} = \frac{1}{ad-bc}\left[\!\begin{array}{cc}
d & -b \\ -c & a \end{array}\!\right].
\]
My point here is that you do not have to memorize the inverse, you can construct it on your own just playing with the equations $ay+bw = 0$ and $cx+dz = 0$ and their simple solution.
The number $ad-bc$ is called the determinant of the matrix $\displaystyle \left[\!\begin{array}{cc} a & b \\ c & d \end{array}\!\right]$. We write \[ \det \left[\!\begin{array}{cc} a & b \\ c & d \end{array}\!\right] = \left|\!\begin{array}{cc} a & b \\ c & d \end{array}\!\right| = ad-bc. \] - It is important for you to perfect calculation of the inverse of an invertible matrix. For a $2\!\times\!2$ matrix one should use Theorem 4, that is the method explained in the preceding item. For a $3\!\times\!3$ matrix one uses the method presented in Example 7.
-
Consider the following problem:
- Determine whether the matrix $A = \left[\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 2 & 1 \\ -1 & 1 & 1 \end{array}\right]$ is invertible.
- If $A$ is invertible find its inverse $A^{-1}$.
-
To answer the first question in the problem we use the implication
If RREF of $A$ is $I_3$, then $A$ is invertible.
This implication is proved in Theorem 7 in Section 2.2 . This proof is important! - So, we just row reduce $A$ to RREF and that will answer the first question in the exercise: \begin{align*} \left[\!\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 2 & 1 \\ -1 & 1 & 1 \end{array}\right] & \sim \left[\!\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 2 & 1 \\ 0 & 1 & 0 \end{array}\right] \\ & \sim \left[\!\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 1 & 0 \\ 0 & 2 & 1 \end{array}\right] \\ & \sim \left[\!\begin{array}{rrr} 1 & 0 & -1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right] \\ & \sim \left[\!\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right] \\ \end{align*}
- The row reduction above shows that $A$ is row equivalent to $I_3$. Therefore, by Theorem 7 in Section 2.2 , $A$ is invertible.
- To calculate the inverse $A^{-1}$ we row reduce the $3\times 6$ matrix $[A | I_3]$: \begin{align*} \left[\!\begin{array}{rrr|rrr} 1 & 0 & -1 & 1 & 0 & 0 \\ 0 & 2 & 1 & 0 & 1 & 0 \\ -1 & 1 & 1 & 0 & 0 & 1 \end{array}\right] & \sim \left[\!\begin{array}{rrr|rrr} 1 & 0 & -1 & 1 & 0 & 0 \\ 0 & 2 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \end{array}\right] \\ & \sim \left[\!\begin{array}{rrr|rrr} 1 & 0 & -1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 2 & 1 & 0 & 1 & 0 \end{array}\right] \\ & \sim \left[\!\begin{array}{rrr|rrr} 1 & 0 & -1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & -2 & 1 & -2 \end{array}\right] \\ & \sim \left[\!\begin{array}{rrr|rrr} 1 & 0 & 0 & -1 & 1 & -2 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & -2 & 1 & -2 \end{array}\right] \\ \end{align*}
- The matrix whose inverse we found above is a very special matrix. It is a matrix whose entries are integers and all the entries of its inverse are integers. In exercises it is often convenient to have such matrices: matrices with integer entries whose inverse is also a matrix with integer entries. Such matrices are called unimodular matrices. I was surprised that there are a lot of such matrices. Here is a pdf file with all unimodular matrices with entries $-1,0,1,2,3$ whose inverses have entries among the ten digits and their opposites. I have omitted the matrices with 3 or more zeros. This pdf file is huge, 3119 pages with over 80000 matrices. If you ever need a unimodular matrix I hope you find it here. You can use these matrices to practice row reduction since for every matrix listed in this file I list its inverse.
- Today and on Friday we discussed Section 2.1: Matrix operations. For now, the objective is to learn matrix multiplication and apply it to verify row reduction. Suggested problems are: 1, 4, 5, 7, 9, 10, 11, 12, 17, 20, 22, 23, 24, 25, 27, 28, 34. The jewel of this section is Matrix Multiplication. It is such a beautiful and rich concept with three distinct ways of looking at it. I talked about it in class today.
-
Below is my attempt to use colors to explain how multiplication of matrices works:
- The most poetic application of matrix multiplication comes from row reduction. On Saturday, October 9, 2021 I posted a $4\!\times\!6$ matrix and later that day I posted its Reduced Row Echelon Form: \[ A = \Bigl[ \begin{array}{cccccc} \mathbf{a}_1 & \mathbf{a}_2 & \mathbf{a}_3 & \mathbf{a}_4 & \mathbf{a}_5 & \mathbf{a}_6 \end{array} \Bigr] = \left[ \begin{array}{cccccc} 1 & 1 & 4 & 1 & 0 & 6 \\ 2 & 1 & 3 & 0 & 1 & 4 \\ 3 & 1 & 2 & 1 & 0 & 8 \\ 4 & 1 & 1 & 0 & 1 & 6 \\ \end{array} \right] \sim \cdots \sim \left[ \begin{array}{ccrcrc} 1 & 0 & -1 & 0 & 0 & 1 \\ 0 & 1 & 5 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 & -1 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \right]. \]
- From the RREF of $A$ we read that the matrix $A$ has three pivot columns; its first, its second and its fourth column are the pivot columns. We also read that the RREF of $A$ has three nonzero rows. Let us separate the pivot columns of $A$ in a separate $4\!\times\!3$ matrix and let us separate the three nonzero rows of the RREF of $A$ in a separate $3\!\times\!6$ matrix as follows: \[ \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 2 & 1 & 0 \\ 3 & 1 & 1 \\ 4 & 1 & 0 \\ \end{array} \right] \qquad \text{and} \qquad \left[ \begin{array}{ccrcrc} 1 & 0 & -1 & 0 & 0 & 1 \\ 0 & 1 & 5 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 & -1 & 3 \end{array} \right]. \]
- What do we have now? We have the $4\!\times\!3$ matrix of the pivot columns of $A$, we have the $3\!\times\!6$ matrix of the nonzero rows of the RREF of $A$ and we started with the $4\!\times\!6$ matrix $A$. Do you sense poetry here? Something rhymes! Multiply matrices! Multiply matrices which are multiplyable and enjoy the magic! \[ \bbox[#7FBFBF, 8px, border: 3px solid teal]{ \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 2 & 1 & 0 \\ 3 & 1 & 1 \\ 4 & 1 & 0 \\ \end{array} \right] \left[ \begin{array}{ccrcrc} 1 & 0 & -1 & 0 & 0 & 1 \\ 0 & 1 & 5 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 & -1 & 3 \end{array} \right] = \left[ \begin{array}{cccccc} 1 & 1 & 4 & 1 & 0 & 6 \\ 2 & 1 & 3 & 0 & 1 & 4 \\ 3 & 1 & 2 & 1 & 0 & 8 \\ 4 & 1 & 1 & 0 & 1 & 6 \\ \end{array} \right]}. \] I colored this equality teal since it is beautealful.
-
In the posts on Saturday, October 9, 2021 I presented the background needed to understand why and how this poetic connection comes about. In the three handwritten pages below I will try to present these why and how in more detail.
- Pause to enjoy the teal!
- Please pay special attention to problems 22, 23, 24, 25 from Section 2.1. In each of these problems you are asked to prove an implication.
-
For each of these problems, and in general whenever you try to prove something, you should rewrite the statement of the problem as a clear implication. That is, as a statement of the form
- Recall that the converse of the implication $p \Rightarrow q$ is the implication $q \Rightarrow p$. Also recall that the converse can be wrong when the original proposition is true.
- For Problem 22 in Section 2.1 write down the converse and answer whether it is true or false. Justify your answer.
- For Problem 24 in Section 2.1 write down the converse and answer whether it is true or false. Justify your answer. This problem is closely related to Problem 26 in Section 2.1.
- Problem 11 in Section 1.6 as stated is inconsistent with the solution that is given at the back of the book. As given, Problem 11 does not have a solution.
- On exams I usually assign 4 problems. Often these problems have several parts (a) and (b) part. In this file you can find some problems in the form that they could appear on the exam.
- We did Section 1.8 and Section 1.9 on Friday and today.
- Suggested problems for Section 1.8: 1-4, 12, 13-17, 19, 20, 25, 27, 28
- Suggested problems for Section 1.9: 1, 3, 4, 5, 7, 8, 11, 12, 18, 19, 23 25, 26, 27, 28, 29, 30
- In the textbook the authors list several reflections transformations across some popular lines like: $x_2 = 0$ (this is $x_1$-axis), $x_1 = 0$ (this is $x_2$-axis), $x_2 = x_1$ (this is the diagonal of the first and the third quadrant), and $x_2 = -x_1$ (this is the diagonal of the second and the fourth quadrant). But why not establish the standard matrix of the reflection across the line which makes the angle $\theta$ with the positive $x_1$-axis? It is not more difficult than the standard matrix of the rotation by the angle $\theta$ in counterclockwise direction, which is \[ \left[\! \begin{array}{cc} \cos(\theta) & -\sin(\theta) \\[5pt] \sin(\theta) & \cos(\theta) \end{array}\!\right] \]
-
The picture below will help us determine the standard matrix of the reflection across the blue line which makes angle $\theta$ with the positive $x_1$-axis. Denote this reflection by
\[
F:\mathbb{R}^2 \to \mathbb{R}^2.
\]
To determine the standard matrix of this reflection we need to calculate the coordinates of the vectors
\[
F \mathbf{e}_1 = F \left[\! \begin{array}{c}
1 \\[3pt]
0
\end{array}\!\right] \quad \text{and} \quad F \mathbf{e}_2 = F \left[\! \begin{array}{c}
0 \\[3pt]
1
\end{array}\!\right]
\]
In the picture below the vector $F \mathbf{e}_1$ is dark orange and the vector $F \mathbf{e}_2$ dark purple.
- By the definition of the reflection $F$, the angle formed by the light orange coordinate vector $\mathbf{e}_1$ and its reflection the dark orange vector $F \mathbf{e}_1$ is $2\theta.$ Therefore, \[ F \mathbf{e}_1 = F \left[\! \begin{array}{c} 1 \\[3pt] 0 \end{array}\!\right] = \left[\! \begin{array}{c} \cos(2\theta) \\[3pt] \sin(2\theta) \end{array}\!\right]. \]
- In this item we calculate the coordinates of the dark purple vector $F \mathbf{e}_2$ which is the reflection of the light purple coordinate vector $\mathbf{e}_2.$ First, we observe that the light gray right triangles in the picture below are congruent. This claim follows from the fact that the hypothenuse of each of these triangles is of length $1$ and the triangles have the same angle $2\theta$ at the origin. That the angle at the origin of the top light gray triangle is $2\theta$ follows from the definition of the reflection. To calculate the angle at the origin for the lower light gray triangle we calculate the angle between the light purple coordinate vector $\mathbf{e}_2$ and its reflection, the dark purple vector $F \mathbf{e}_2;$ since the angle between the light purple coordinate vector $\mathbf{e}_2$ and the blue line is $\displaystyle \frac{\pi}{2} - \theta$, the angle between is $\mathbf{e}_2$ and $F \mathbf{e}_2$ is \[ 2 \left(\frac{\pi}{2} - \theta\right) = \pi - 2 \theta. \] Since the sum of this angle and the angle at the origin for the lower light gray triangle equals $\pi,$ we have proven that the angle at the origin for the lower light gray triangle equals $2\theta.$ In the preceding item we proved that the horizontal side of the top light gray right triangle is $\cos(2\theta)$ and its vertical side is $\sin(2\theta)$. As a consequence, the horizontal side of the lower light gray right triangle is $\sin(2\theta)$ and its vertical side is $\cos(2\theta)$. Adjusting for the positioning in the coordinate system we get \[ F \mathbf{e}_2 = F \left[\! \begin{array}{c} 0 \\[3pt] 1 \end{array}\!\right] = \left[\! \begin{array}{c} \sin(2\theta) \\[3pt] -\cos(2\theta) \end{array}\!\right]. \] Finally we have that the standard matrix of the reflection across the blue line which makes angle $\theta$ with the positive $x_1$-axis is \[ \left[\! \begin{array}{cc} \cos(2\theta) & \sin(2\theta) \\[5pt] \sin(2\theta) & -\cos(2\theta) \end{array}\!\right]. \] Enjoy Reflections!
Enjoy Reflections!
-
Problems 41, 42, 43, 44 in Section 1.7: Linear independence are very interesting and important. The matrices in these problems are not easy to row reduce by hand, so the textbook recommends that we use a calculator. Here I am offering a simpler matrix and more detailed guidance for the calculations. This is my version of these four problems.
Problem. Consider the following $4\times 6$ matrix \[ A = \left[ \begin{array}{cccccc} 1 & 1 & 4 & 1 & 0 & 6 \\ 2 & 1 & 3 & 0 & 1 & 4 \\ 3 & 1 & 2 & 1 & 0 & 8 \\ 4 & 1 & 1 & 0 & 1 & 6 \\ \end{array} \right]. \] Denote the columns of $A$ by $\mathbf{a}_1,$ $\mathbf{a}_2,$ $\mathbf{a}_3,$ $\mathbf{a}_4,$ $\mathbf{a}_5,$ and $\mathbf{a}_6.$ That is, \[ \mathbf{a}_1 = \left[ \begin{array}{cccccc} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} \right], \ \mathbf{a}_2 = \left[ \begin{array}{c} 1\\ 1 \\ 1 \\ 1 \\ \end{array} \right], \ \mathbf{a}_3 = \left[ \begin{array}{c} 4 \\ 3 \\ 2 \\ 1 \\ \end{array} \right], \ \mathbf{a}_4 = \left[ \begin{array}{c} 1 \\ 0 \\ 1 \\ 0 \\ \end{array} \right], \ \mathbf{a}_5 = \left[ \begin{array}{c} 0\\ 1\\ 0\\ 1 \\ \end{array} \right], \ \mathbf{a}_6 = \left[ \begin{array}{c} 6 \\ 4 \\ 8 \\ 6 \\ \end{array} \right]. \] Answer the following questions:
- Find the Reduced Row Echelon Form of $A$. (Please make sure that it is done correctly.)
- Is the vector $\mathbf{a}_1$ linearly independent? Explain using the definition.
- Are the vectors $\mathbf{a}_1,$ $\mathbf{a}_2$ linearly independent? Explain using the definition.
- Are the vectors $\mathbf{a}_1,$ $\mathbf{a}_2,$ $\mathbf{a}_3$ linearly independent? Explain using the definition. If the answer is No, then express $\mathbf{a}_3$ as a linear combination of $\mathbf{a}_1$ and $\mathbf{a}_2.$ That is, find the real numbers $\alpha_1$ and $\alpha_2$ such that \[ \mathbf{a}_3 = \alpha_1 \mathbf{a}_1+ \alpha_2 \mathbf{a}_2. \] Make a record of the numbers $\alpha_1$ and $\alpha_2.$
- Are the vectors $\mathbf{a}_1,$ $\mathbf{a}_2,$ $\mathbf{a}_4$ linearly independent? Explain using the definition.
- Are the vectors $\mathbf{a}_1,$ $\mathbf{a}_2,$ $\mathbf{a}_4,$ $\mathbf{a}_5$ linearly independent? Explain using the definition. If the answer is No, then express $\mathbf{a}_5$ as a linear combination of $\mathbf{a}_1,$ $\mathbf{a}_2$ and $\mathbf{a}_4.$ That is, find the real numbers $\beta_1,$ $\beta_2$ and $\beta_4$ such that \[ \mathbf{a}_5 = \beta_1 \mathbf{a}_1+ \beta_2 \mathbf{a}_2 + \beta_4 \mathbf{a}_4. \] Make a record of the numbers $\beta_1,$ $\beta_2$ and $\beta_4.$
- Are the vectors $\mathbf{a}_1,$ $\mathbf{a}_2,$ $\mathbf{a}_4,$ $\mathbf{a}_6$ linearly independent? Explain using the definition. If the answer is No, then express $\mathbf{a}_6$ as a linear combination of $\mathbf{a}_1,$ $\mathbf{a}_2$ and $\mathbf{a}_4.$ That is, find the real numbers $\gamma_1,$ $\gamma_2$ and $\gamma_4$ such that \[ \mathbf{a}_6 = \gamma_1 \mathbf{a}_1+ \gamma_2 \mathbf{a}_2 + \gamma_4 \mathbf{a}_4. \] Make a record of the numbers $\gamma_1,$ $\gamma_2$ and $\gamma_4.$
- The moral of this problem is that all the information you found about the linear independence and dependence of the columns of $A$ is contained in the Reduced Row Echelon Form of $A$. I would like you to carefully review your findings and discover how are all the facts about the columns of $A$ that you found in this problem encoded in the Reduced Row Echelon Form of $A$.
-
Let me answer some of the questions asked above. (Also see the follow-up on October 21.)
- The row reduction algorithm applied to the matrix $A$ gives its Reduced Row Echelon Form: \[ A = \Bigl[ \begin{array}{cccccc} \mathbf{a}_1 & \mathbf{a}_2 & \mathbf{a}_3 & \mathbf{a}_4 & \mathbf{a}_5 & \mathbf{a}_6 \end{array} \Bigr] = \left[ \begin{array}{cccccc} 1 & 1 & 4 & 1 & 0 & 6 \\ 2 & 1 & 3 & 0 & 1 & 4 \\ 3 & 1 & 2 & 1 & 0 & 8 \\ 4 & 1 & 1 & 0 & 1 & 6 \\ \end{array} \right] \sim \cdots \sim \left[ \begin{array}{ccrcrc} 1 & 0 & -1 & 0 & 0 & 1 \\ 0 & 1 & 5 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 & -1 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \right]. \] Remark We obtained the preceding RREF by performing row operations on the rows of $A.$ It is important to realize that the same row operations would lead to the following Reduced Row Echelon Forms: \[ \Bigl[ \begin{array}{cc} \mathbf{a}_1 & \mathbf{a}_2 \end{array} \Bigr] = \left[ \begin{array}{cc} 1 & 1 \\ 2 & 1 \\ 3 & 1 \\ 4 & 1 \\ \end{array} \right] \sim \cdots \sim \left[ \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ 0 & 0 \\ 0 & 0 \\ \end{array} \right] \] and \[ \Bigl[ \begin{array}{ccc} \mathbf{a}_1 & \mathbf{a}_2 & \mathbf{a}_3 \end{array} \Bigr] = \left[ \begin{array}{ccc} 1 & 1 & 4 \\ 2 & 1 & 3 \\ 3 & 1 & 2 \\ 4 & 1 & 1 \\ \end{array} \right] \sim \cdots \sim \left[ \begin{array}{ccrcrc} 1 & 0 & -1 \\ 0 & 1 & 5 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} \right] \] and \[ \Bigl[ \begin{array}{ccc} \mathbf{a}_1 & \mathbf{a}_2 & \mathbf{a}_4 \end{array} \Bigr] = \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 2 & 1 & 0 \\ 3 & 1 & 1 \\ 4 & 1 & 0 \\ \end{array} \right] \sim \cdots \sim \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end{array} \right] \] and \[ \Bigl[ \begin{array}{cccc} \mathbf{a}_1 & \mathbf{a}_2 & \mathbf{a}_4 & \mathbf{a}_5 \end{array} \Bigr] = \left[ \begin{array}{cccc} 1 & 1 & 1 & 0 \\ 2 & 1 & 0 & 1 \\ 3 & 1 & 1 & 0 \\ 4 & 1 & 0 & 1 \\ \end{array} \right] \sim \cdots \sim \left[ \begin{array}{ccrcrc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 0 \\ \end{array} \right] \] and \[ \Bigl[ \begin{array}{cccc} \mathbf{a}_1 & \mathbf{a}_2 & \mathbf{a}_4 & \mathbf{a}_5 \end{array} \Bigr] = \left[ \begin{array}{cccc} 1 & 1 & 1 & 0 \\ 2 & 1 & 0 & 1 \\ 3 & 1 & 1 & 0 \\ 4 & 1 & 0 & 1 \\ \end{array} \right] \sim \cdots \sim \left[ \begin{array}{ccrcrc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 0 \\ \end{array} \right] \] and \[ \Bigl[ \begin{array}{cccc} \mathbf{a}_1 & \mathbf{a}_2 & \mathbf{a}_4 & \mathbf{a}_6 \end{array} \Bigr] = \left[ \begin{array}{cccc} 1 & 1 & 1 & 6 \\ 2 & 1 & 0 & 4 \\ 3 & 1 & 1 & 8 \\ 4 & 1 & 0 & 6 \\ \end{array} \right] \sim \cdots \sim \left[ \begin{array}{ccrcrc} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 \\ \end{array} \right]. \]
- The vector $\mathbf{a}_1$ is linearly independent. Recall the definition of linear independence. A vector $\mathbf{v}_1$ is linearly independent if the homogeneous equation $x_1 \mathbf{v}_1 = \mathbf{0}$ has only the trivial solution. Consider the homogeneous equation $x_1 \mathbf{a}_1 = \mathbf{0}.$ The preceding equation is equivalent to \[ x_1 \left[ \begin{array}{cccccc} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} \right] = \left[ \begin{array}{cccccc} 0 \\ 0 \\ 0 \\ 0 \\ \end{array} \right], \] which in turn is equivalent to $x_1 = 0.$ Hence the equation $x_1 \mathbf{a}_1 = \mathbf{0}$ has only the trivial solution. This proves that the vector $\mathbf{a}_1$ is linearly independent.
- The vectors $\mathbf{a}_1$ and $\mathbf{a}_2$ are linearly independent. To prove this claim we need to prove that the homogeneous vector equation $x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 = \mathbf{0}$ has only the trivial solution. Since we already know that \[ \Bigl[ \begin{array}{cc} \mathbf{a}_1 & \mathbf{a}_2 \end{array} \Bigr] = \left[ \begin{array}{cc} 1 & 1 \\ 2 & 1 \\ 3 & 1 \\ 4 & 1 \\ \end{array} \right] \sim \cdots \sim \left[ \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ 0 & 0 \\ 0 & 0 \\ \end{array} \right], \] the equation $x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 = \mathbf{0}$ is equivalent to the equation \[ x_1 \left[ \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] + x_2 \left[ \begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \\ \end{array} \right] = \left[ \begin{array}{c} 0 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] \] and the last equation is equivalent to $x_1 = 0$ and $x_2 =0$. Hence $\mathbf{a}_1$ and $\mathbf{a}_2$ are linearly independent.
- The vectors $\mathbf{a}_1,$ $\mathbf{a}_2,$ $\mathbf{a}_3$ are not linearly independent. These vectors are linearly dependent. We claim that the homogeneous vector equation $x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 + x_3 \mathbf{a}_3 = \mathbf{0}$ has infinitely many solution. Since we already know that \[ \Bigl[ \begin{array}{ccc} \mathbf{a}_1 & \mathbf{a}_2 & \mathbf{a}_3 \end{array} \Bigr] = \left[ \begin{array}{ccc} 1 & 1 & 4 \\ 2 & 1 & 3 \\ 3 & 1 & 2 \\ 4 & 1 & 1 \\ \end{array} \right] \sim \cdots \sim \left[ \begin{array}{ccr} 1 & 0 & -1 \\ 0 & 1 & 5 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} \right], \] the equation $x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 + x_3 \mathbf{a}_3= \mathbf{0}$ is equivalent to the equation \[ x_1 \left[ \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] + x_2 \left[ \begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \\ \end{array} \right] + x_2 \left[ \begin{array}{r} -1 \\ 5 \\ 0 \\ 0 \\ \end{array} \right]= \left[ \begin{array}{c} 0 \\ 0 \\ 0 \\ 0 \\ \end{array} \right]. \] In the last equation the variable $x_3$ is free. All solutions of this equation are given by $x_1 = s,$ $x_2 = -5s,$ $x_3 = s$ where $s$ is any real number. For $s=1$ we get a specific linear dependence relation \[ 1 \mathbf{a}_1 + (-5) \mathbf{a}_2 + 1 \mathbf{a}_3 = \mathbf{0}$. \] A different way to get the same relation is to solve the nonhomogeneous equation $x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 = \mathbf{a}_3.$ It is very interesting to observe that we already have everything that we need to solve this equation. We already know that \[ \Bigl[ \begin{array}{cc|c} \mathbf{a}_1 & \mathbf{a}_2 & \mathbf{a}_3 \end{array} \Bigr] = \left[ \begin{array}{ccc} 1 & 1 & 4 \\ 2 & 1 & 3 \\ 3 & 1 & 2 \\ 4 & 1 & 1 \\ \end{array} \right] \sim \cdots \sim \left[ \begin{array}{cc|r} 1 & 0 & -1 \\ 0 & 1 & 5 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} \right]. \] Therefore, $x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 = \mathbf{a}_3$ is equivalent to the equation \[ x_1 \left[ \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] + x_2 \left[ \begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \\ \end{array} \right] = \left[ \begin{array}{r} -1 \\ 5 \\ 0 \\ 0 \\ \end{array} \right]. \] Hence the only solution of the nonhomogeneous equation $x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 = \mathbf{a}_3$ is $x_1 = -1$ and $x_2 = 5.$ That is \[ \mathbf{a}_3 = (-1) \mathbf{a}_1 +5 \mathbf{a}_2. \] Verify! \[ \left[ \begin{array}{r} 4 \\ 3 \\ 2 \\ 1 \\ \end{array} \right] = (-1) \left[ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} \right] + 5 \left[ \begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \\ \end{array} \right]. \]
- Similar to III.
- Similar to IV.
- Similar to IV and VI.
- Would you please think about this? The connections that are present in RREF are beautiful. We will discuss these many times in future classes.
- We started Section 1.7: Linear independence today. Suggested problems: 2, 4, 5, 8, 10, 11, 17, 21, 23, 24, 25, 26, 27, 28, 29, 32, 33, 34, 35, 36, 37, 38, 39, 40
- We discussed Section 1.6: Applications of Linear Systems. We did two applications: Balancing Chemical Equations and Network Flow. Suggested problems for Section 1.6: 5-8, 11-14.
- An important physical application of linear systems is in Problems 33 and 34 in Section 1.1. These problems show how to find an approximation for the steady-state temperature distribution of a thin plate when the temperature around the boundary is known. In this problem approximations for the steady-state temperature distribution are found at only four points. But this problem gives a blueprint on how to find the approximations at any rectangular grid of points. If we take a large grid, for example $400 = 20\times20$ points, then we would need to solve a linear system of 400 equations with 400 unknowns. It is an interesting challenge to figure out what would be the $400\times400$ matrix of this system. I did not pursue this question further, so I do not know how feasable this is. In Math 430 we show how to find the steady-state temperature distribution in a thin plate when the temperature around the boundary is known using partial differential equations.
- More importantly, however, I talked about my favorite application of vectors: COLORS. In fact, I love this application so much that I wrote a webpage to celebrate it: Color Cube.
- We finished Section 1.5. Suggested problems for Section 1.5: 1, 3, 5, 6, 7, 9, 11, 12, 13-16, 19, 21, 23, 24, 26, 29, 32, 35, 37-40.
- Let $m$ and $n$ be positive integers, that is $m, n \in \mathbb{N}.$ Let $\color{green}{A}$ be an $m\times n$ matrix. We explained the relationship between the solution set of the homogeneous equation $\color{green}{A}\color{red}{\mathbf{x}} = \mathbf{0}$ and the solution set of a consistent nonhomogeneous equation $\color{green}{A}\color{red}{\mathbf{x}} = \color{green}{\mathbf{b}}$; see Theorem 6 for details.
-
Let $m, n \in \mathbb{N}.$ Let $\color{green}{A}$ be an $m\times n$ matrix. A few points about the solution set of a homogeneous equation
\[
\color{green}{A}\color{red}{\mathbf{x}} = \mathbf{0}.
\]
The preceding matrix equation can be rewritten as a homogenous system with $m$ equations and $n$ unknowns. The unknowns are collected in the vector $\color{red}{\mathbf{x}} \in \mathbb{R}^n.$ Here $\mathbf{0}$ is the zero vector in $\mathbb{R}^m.$
- The homogeneous equation $\color{green}{A}\color{red}{\mathbf{x}} = \mathbf{0}$ always has a solution (it is consistent). One solution is always the zero vector in $\mathbb{R}^n.$
- Another explanation why the homogeneous equation $\color{green}{A}\color{red}{\mathbf{x}} = \mathbf{0}$ always has a solution is to consider its augmented matrix \[ \bigl[\begin{array}{c|c} \color{green}{A} & \mathbf{0} \end{array} \bigr]. \] As we perform row reduction, the last column will always be $\mathbf{0}.$ Therefore the last column of the reduced row echelon form of the matrix $\bigl[\begin{array}{c|c} \color{green}{A} & \mathbf{0} \end{array} \bigr]$ will not be a pivot column. Hence the matrix equation $\color{green}{A}\color{red}{\mathbf{x}} = \mathbf{0}$ is consistent.
-
We have the following dichotomy for the solution:
- The zero vector in $\mathbb{R}^n$ is a unique solution. This case occurs if and only if each column of the reduced row echelon form of $\color{green}{A}$ is a pivot column. In other words, there are no free variables.
- There are infinitely many solutions. This case occurs if and only if there are free variables. In this case the solution set can be written as a span of several vectors. In fact, we can write the solution set as a span of as many vectors as there are free variables.
- For example, let $\color{green}{A}$ be a $3\times 4$ matrix and assume that \[ \bigl[\begin{array}{c|c} \color{green}{A} & \mathbf{0} \end{array} \bigr] \sim \cdots \sim \left[\!\begin{array}{rrrr|r} 1 & -2 & 0 & -1 & 0 \\ 0 & 0 & 1 & 2 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array}\! \right] \] In this case we have two free variables and the solution set of the matrix equation $\color{green}{A}\color{red}{\mathbf{x}} = \mathbf{0}$ can be written as a span of two vectors in $\mathbb{R}^4.$ To find those vectors we need to solve the corresponding system of linear equations: \begin{alignat*}{10} &x_1 & & - &&2 x_2 & & && && && - && && x_4 && = &&0\\ & & & && & & && &&x_3 && + && 2 && x_4 && = &&0 \end{alignat*} The solution of this system in parametric vector form is \[ \left[\!\begin{array}{c} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array}\! \right] = \left[\!\begin{array}{c} 2 s + t \\ s \\ -2 t \\ t \end{array}\! \right] = \left[\!\begin{array}{c} 2 s + 1 t \\ 1 s + 0 t \\ 0 s -2 t \\ 0 s + 1 t \end{array}\! \right] = s \left[\!\begin{array}{c} 2 \\ 1 \\ 0 \\ 0 \end{array}\! \right] + t \left[\!\begin{array}{r} 1 \\ 0 \\ -2 \\ 1 \end{array}\! \right], \] where $s$ and $t$ are arbitrary real numbers. Hence, the solution set of the homogeneous matrix equation $\color{green}{A}\color{red}{\mathbf{x}} = \mathbf{0}$ can be written as \[ \operatorname{Span}\left\{ \left[\!\begin{array}{c} 2 \\ 1 \\ 0 \\ 0 \end{array}\! \right], \left[\!\begin{array}{r} 1 \\ 0 \\ -2 \\ 1 \end{array}\! \right] \right\}. \]
- On Friday we discussed Section 1.4: The Matrix Equation $A\mathbf{x} = \mathbf{b}$. Suggested problems for Section 1.4: 1, 5, 13, 14, 15, 16,17-20, 21, 22, 23, 24, 25, 26, 35, 36 and problems added in this post 32 and 34.
- On Friday we started Section 1.5 which talks about writing solution sets of linear systems in parametric vector form. Suggested problems for Section 1.5: 1, 3, 5, 6, 7, 9, 11, 12, 13, 15, 16, 19, 21. While working on these problems, try to recognize a span of one, or two, or three vectors when you write a formula for the solution in parametric vector form.
-
The following Problem is inspired by Problem 32 in Section 1.3.
Consider the vectors $\color{green}{\mathbf{a}_1},$ $\color{green}{\mathbf{a}_2},$ $\color{green}{\mathbf{a}_3},$ and $\color{#00FF00}{\mathbf{b}}$ in $\mathbb{R}^2$ as shown in the picture below.
- Is the vector equation \[ \color{red}{x_1} \color{green}{\mathbf{a}_1} + \color{red}{x_2} \color{green}{\mathbf{a}_2} + \color{red}{x_3} \color{green}{\mathbf{a}_3} = \color{#00FF00}{\mathbf{b}} \] consistent or inconsistent.
- Find the reduced row echelon form of the augmented matrix \[ \left[\begin{array}{ccc|c} \color{green}{\mathbf{a}_1} & \color{green}{\mathbf{a}_2} & \color{green}{\mathbf{a}_3} & \color{#00FF00}{\mathbf{b}} \end{array} \right]. \]
- Find the solution set of the vector equation \[ \color{red}{x_1} \color{green}{\mathbf{a}_1} + \color{red}{x_2} \color{green}{\mathbf{a}_2} + \color{red}{x_3} \color{green}{\mathbf{a}_3} = \color{#00FF00}{\mathbf{b}} \] and represent the solution set in parametric vector form.
-
Consider two specific vectors in $\mathbb{R}^3$
\[
\bbox[#50FF50]{\left[\! \begin{array}{r} 1 \\ -3 \\ 1
\end{array} \!\right]} \quad \text{and} \quad \bbox[#8080FF]{\left[\! \begin{array}{r} -4 \\ 1 \\ 2
\end{array} \!\right]}
\]
as given in the picture below:
- We ask the question: Is the vector $\left[\! \begin{array}{r} 2 \\ 1 \\ -4 \end{array} \!\right]$ in the span of the vectors $\bbox[#50FF50]{\left[\! \begin{array}{r} 1 \\ -3 \\ 1 \end{array} \!\right]}$ and $\bbox[#8080FF]{\left[\! \begin{array}{r} -4 \\ 1 \\ 2 \end{array} \!\right]}$? Or, the same question in mathematical notation: Is the following statement true \[ \left[\begin{array}{r} 2 \\ 1 \\ -4 \end{array} \right] \in \operatorname{Span}\left\{ \bbox[#50FF50]{\left[\! \begin{array}{r} 1 \\ -3 \\ 1 \end{array} \!\right]}, \bbox[#8080FF]{\left[\! \begin{array}{r} -4 \\ 1 \\ 2 \end{array} \!\right]} \right\}? \] And two more questions: Is the following statement true \[ \left[\begin{array}{r} 6 \\ -7 \\ 0 \end{array} \right] \in \operatorname{Span}\left\{ \bbox[#50FF50]{\left[\! \begin{array}{r} 1 \\ -3 \\ 1 \end{array} \!\right]}, \bbox[#8080FF]{\left[\! \begin{array}{r} -4 \\ 1 \\ 2 \end{array} \!\right]} \right\}? \qquad \left[\begin{array}{r} -7 \\ -1 \\ 5 \end{array} \right] \in \operatorname{Span}\left\{ \bbox[#50FF50]{\left[\! \begin{array}{r} 1 \\ -3 \\ 1 \end{array} \!\right]}, \bbox[#8080FF]{\left[\! \begin{array}{r} -4 \\ 1 \\ 2 \end{array} \!\right]} \right\}? \]
-
Really interesting aspect of linear algebra is that these three questions are just vector equations in disguise. In fact, we are asking if the following vector equations have solutions (are consistent):
\[
x_1 \bbox[#50FF50]{\left[\! \begin{array}{r} 1 \\ -3 \\ 1
\end{array} \!\right]} +x_2 \bbox[#8080FF]{\left[\! \begin{array}{r} -4 \\ 1 \\ 2
\end{array} \!\right]} = \left[\begin{array}{r} 2 \\ 1 \\ -4
\end{array} \right], \quad
x_1 \bbox[#50FF50]{\left[\! \begin{array}{r} 1 \\ -3 \\ 1
\end{array} \!\right]} +x_2 \bbox[#8080FF]{\left[\! \begin{array}{r} -4 \\ 1 \\ 2
\end{array} \!\right]} = \left[\begin{array}{r} 6 \\ -7 \\ 0
\end{array} \right], \quad
x_1 \bbox[#50FF50]{\left[\! \begin{array}{r} 1 \\ -3 \\ 1
\end{array} \!\right]} +x_2 \bbox[#8080FF]{\left[\! \begin{array}{r} -4 \\ 1 \\ 2
\end{array} \!\right]} = \left[\begin{array}{r} -7 \\ -1 \\ 5
\end{array} \right].
\]
In turn, these vector equations are in fact systems of linear equations, like we did on the first day of classes:
These systems are solved by row reducing the augmented matrices. But, this is huge, we can do three row reductions in one go: \begin{align*} \left[\!\begin{array}{rr|rrr} 1 & -4 & 2 & 6& -7 \\ -3 & 1 & 1 & -7& -1 \\ 1 & 2 & -4& 0& 5 \end{array}\! \right] & \sim \left[\!\begin{array}{rr|rrr} 1 & -4 & 2 & 6& -7 \\ 0 & -11 & 7 & 11 & -22 \\ 0 & 6 & -6& -6 & 12 \end{array}\! \right] \\ & \sim \left[\!\begin{array}{rr|rrr} 1 & -4 & 2 & 6& -7 \\ 0 & 1 & -\frac{7}{11} & -1 & 2 \\ 0 & 1 & -1& -1 & 2 \end{array}\! \right] \\ & \sim \left[\!\begin{array}{rr|rrr} 1 & -4 & 2 & 6& -7 \\ 0 & 1 & -\frac{7}{11} & -1 & 2 \\ 0 & 0 & -\frac{4}{11}& 0 & 0 \end{array}\! \right] \\ & \sim \left[\!\begin{array}{rr|rrr} 1 & -4 & 2 & 6& -7 \\ 0 & 1 & -\frac{7}{11} & -1 & 2 \\ 0 & 0 & 1 & 0 & 0 \end{array}\! \right] \\ & \sim \left[\!\begin{array}{rr|rrr} 1 & -4 & 0 & 6& -7 \\ 0 & 1 & 0 & -1 & 2 \\ 0 & 0 & 1 & 0 & 0 \end{array}\! \right] \\ & \sim \left[\!\begin{array}{rr|rrr} 1 & 0 & 0 & 2 & 1 \\ 0 & 1 & 0 & -1 & 2 \\ 0 & 0 & 1 & 0 & 0 \end{array}\! \right] \qquad \text{this matrix is in RREF} \end{align*}System 1 Systems 2 Systems 3 \begin{alignat*}{8} &x_1 & & - 4 &x_2 & &=&& 2\\ -3 &x_1 & & + &x_2 & & =&& 1 \\ &x_1 & & + 2 &x_2 & & =&& -4 \end{alignat*} \begin{alignat*}{8} &x_1 & & - 4 &x_2 & &=&& 6\\ -3 &x_1 & & + &x_2 & & =&&-7 \\ &x_1 & & + 2 &x_2 & & =&& 0 \end{alignat*} \begin{alignat*}{8} &x_1 & & - 4 &x_2 & &=&& -7\\ -3 &x_1 & & + &x_2 & & =&& -1 \\ &x_1 & & + 2 &x_2 & & =&& 5 \end{alignat*} -
Conclusions:
- Since the the first augmented column of the RREF is a pivot column and this augmented column corresponds to System 1, we conclude that System 1 is inconsistent. Therefore, it is true that \[ \left[\begin{array}{r} 2 \\ 1 \\ -4 \end{array} \right] \not\in \operatorname{Span}\left\{ \bbox[#50FF50]{\left[\! \begin{array}{r} 1 \\ -3 \\ 1 \end{array} \!\right]}, \bbox[#8080FF]{\left[\! \begin{array}{r} -4 \\ 1 \\ 2 \end{array} \!\right]} \right\}. \]
- Since the second augmented column of the RREF is not a pivot column and this augmented column corresponds to System 2, we conclude that System 2 is consistent. From the RREF we can read even more \[ \left[\begin{array}{r} 6 \\ -7 \\ 0 \end{array} \right] = 2 \bbox[#50FF50]{\left[\! \begin{array}{r} 1 \\ -3 \\ 1 \end{array} \!\right]} - \bbox[#8080FF]{\left[\! \begin{array}{r} -4 \\ 1 \\ 2 \end{array} \!\right]}. \] Therefore, it is true that \[ \left[\begin{array}{r} 6 \\ -7 \\ 0 \end{array} \right] \in \operatorname{Span}\left\{ \bbox[#50FF50]{\left[\! \begin{array}{r} 1 \\ -3 \\ 1 \end{array} \!\right]}, \bbox[#8080FF]{\left[\! \begin{array}{r} -4 \\ 1 \\ 2 \end{array} \!\right]} \right\}. \]
- Since the third augmented column of the RREF is not a pivot column and this augmented column corresponds to System 3, we conclude that System 3 is consistent. From the RREF we can read even more \[ \left[\begin{array}{r} -7 \\ -1 \\ 5 \end{array} \right] = \bbox[#50FF50]{\left[\! \begin{array}{r} 1 \\ -3 \\ 1 \end{array} \!\right]} + 2 \bbox[#8080FF]{\left[\! \begin{array}{r} -4 \\ 1 \\ 2 \end{array} \!\right]}. \] Therefore, it is true that \[ \left[\begin{array}{r} -7 \\ -1 \\ 5 \end{array} \right] \in \operatorname{Span}\left\{ \bbox[#50FF50]{\left[\! \begin{array}{r} 1 \\ -3 \\ 1 \end{array} \!\right]}, \bbox[#8080FF]{\left[\! \begin{array}{r} -4 \\ 1 \\ 2 \end{array} \!\right]} \right\}. \]
-
The questions which are answered in the previous items can be answered by stating a universal problem:
-
The picture below is an attempt to illustrate
\[
\operatorname{Span}\left\{ \bbox[#50FF50]{\left[\! \begin{array}{r} 1 \\ -3 \\ 1
\end{array} \!\right]}, \bbox[#8080FF]{\left[\! \begin{array}{r} -4 \\ 1 \\ 2
\end{array} \!\right]} \right\}
\]
geometrically. In the picture below this span is represented by the yellow translucent plane in $\mathbb{R}^3$. In this plane I placed a grid imposed by the green and the blue vector. To indicate that there are many vectors in this plane, I placed nine gray vectors in the picture all of which are in the span.
- In the post of Thursday, September 23, 2021 we discussed the important questions of existence and uniqueness of solutions of the linear equation with one unknown $\color{green}{a} \color{red}{x} = \color{green}{b}$ where $\color{green}{a}$ and $\color{green}{b}$ are arbitrary real numbers. Before proceeding please recall our findings.
-
Now we want to answer the important questions of existence and uniqueness of the solution of a system of $m$ linear equations each with $n$ unknowns. Here $m$ and $n$ are positive integers. (In set notation we write $m,n\in \mathbb{N}.$) A linear system with $m$ equations each with $n$ unknowns can be written as follows:
\begin{equation} \label{eq:LS} \tag{LS}
\require{amsmath}
\begin{array}{ccccccccc}
\color{green}{a_{11}} \color{red}{x_{1}} & + &
\color{green}{a_{12}} \color{red}{x_{2}} & + & \cdots & + &
\color{green}{a_{1n}} \color{red}{x_{n}} & = & \color{green}{b_{1}} \\
\color{green}{a_{21}} \color{red}{x_{1}} & + &
\color{green}{a_{22}} \color{red}{x_{2}} & + & \cdots & + &
\color{green}{a_{2n}} \color{red}{x_{n}} & = & \color{green}{b_{2}} \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \\
\color{green}{a_{m1}} \color{red}{x_{1}} & + &
\color{green}{a_{m2}} \color{red}{x_{2}} & + & \cdots & + &
\color{green}{a_{mn}} \color{red}{x_{n}} & = & \color{green}{b_{m}}
\end{array}
\end{equation}
To answer the important questions of existence and uniqueness of the solution of system \eqref{eq:LS} we
proceed as follows:
- First: we write the augmented matrix of this system: \begin{equation} \label{eq:AM} \tag{AM} \left[\!\begin{array}{cccc|c} \color{green}{a_{11}} & \color{green}{a_{12}} & \cdots & \color{green}{a_{1n}} & \color{green}{b_{1}} \\ \color{green}{a_{21}} & \color{green}{a_{22}} & \cdots & \color{green}{a_{2n}} & \color{green}{b_{2}} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ \color{green}{a_{m1}} & \color{green}{a_{m2}} & \cdots & \color{green}{a_{mn}} & \color{green}{b_{m}} \\ \end{array}\! \right] \end{equation} It is important to note that the augmented matris of the system \eqref{eq:LS} is completely green matrix with $m$ rows and $n+1$ columns. The last column is the augmented column.
- Second: we find the Reduced Row Echelon Form of the matrix in \eqref{eq:AM}; call this matrix RREF of \eqref{eq:AM}.
-
Third: using the matrix
RREF of \eqref{eq:AM} we can answer the existence and uniqueness questions as follows:
The question of the Existence of solution leads to the following dichotomy:
- Solution does not exist: If the last column of the RREF of \eqref{eq:AM} is a pivot column, than the system \eqref{eq:LS} does not have a solution.
- Solution does exist: If the last column of the RREF of \eqref{eq:AM} is not a pivot column, than the system \eqref{eq:LS} does have a solution.
- Solution is not unique: If the RREF of \eqref{eq:AM} has at least two columns that are not pivot columns one of which is the last column, than the system \eqref{eq:LS} has infinitely many solutions.
- Solution is unique: If the last column of the RREF of \eqref{eq:AM} is not a pivot column and all other columns of this matrix are pivot columns, than the solution of the system \eqref{eq:LS} is unique.
- Solution does not exist: the last column of the RREF of \eqref{eq:AM} is a pivot column.
- Solution is not unique: the RREF of \eqref{eq:AM} has at least two columns that are not pivot columns one of which is the last column.
- Solution is unique: the last column of the RREF of \eqref{eq:AM} is not a pivot column and all other columns of this matrix are pivot columns
- Yesterday we discussed Section 1.3: Vector Equations. Suggested problems for Section 1.3: 1, 5, 9, 15, 17, 18, 19, 21-25, 32.
- Today we talked about Section 1.2. Suggested problems for Section 1.2: 3, 5, 6, 7, 8, 12, 17-31.
- In addition to the above problems in Section 1.2 do Problem 33.
- Also, in addition to the problems suggested for Section 1.1 do Problem 33 and Problem 34.
- A useful link is Wikipedia's Row echelon form.
- A matrix whose all entries are zero is called a zero matrix. A row of a matrix is said to be a zero row if all the entries in that row are zero. The leftmost nonzero entry of a nonzero row is called the leading entry of a row. The zeros preceding the leading entry are called the leading zeros of a row. All entries of a zero row are leading zeros.
- This is a restatement of Wikipidia's definition of reduced row echelon form:
Each zero matrix is in reduced row echelon form. A nonzero matrix is in reduced row echelon form if it satisfies the following three conditions:
- Each nonzero row has strictly less leading zeros then the row below it.
- The leading entry of each nonzero row is equal to $1$.
- The leading entry of each nonzero row is the only nonzero entry in its column.
-
To illustrate the definition of the reduced row echelon form I made a picture of a $12\times 25$ matrix (that is a matrix with $12$ rows and $25$ columns which is in reduced row echelon form. To emphasize the role of the leading zeros, I colored them blue. To emphasize the role of leading $1$s, I colored them green. I also colored in green the each pivot column. The entries of the matrix that are not specifically written as $0$s or $1$s can be any real numbers. Please notice how blue leading zeros form steps which climb from right to left. Also notice that each stair hosts a pivot position, that is the leading $1$ in a nonzero row.
- A very good exercise in understanding RREF (reduced row echelon form) is to write down all $2\!\times\!3$ matrices which are in RREF. There are seven of them. Below I list the matrix with no pivot columns, then all matrices with one pivot column, then the matrices with two pivot columns. Those are all possibilities since each pivot column has pivot position occupied by the leading entry which needs its own row and we are studying matrices with only two rows. In the matrices below stars ($*$) stand for arbitrary real numbers. \begin{align*} & \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \\ & \begin{bmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix},\quad \begin{bmatrix} 0 & 1 & * \\ 0 & 0 & 0 \end{bmatrix},\quad \begin{bmatrix} 1 & * & * \\ 0 & 0 & 0 \end{bmatrix},\\ & \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad \begin{bmatrix} 1 & * & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad \begin{bmatrix} 1 & 0 & * \\ 0 & 1 & * \end{bmatrix}, \quad \end{align*}
- Here are all possible $3\!\times\!4$ matrices in RREF (reduced row echelon form). There are fifteen of them. \begin{align*} & \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}, \\ & \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}, \ \begin{bmatrix} 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix},\ \begin{bmatrix} 0 & 1 & * & * \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}, \ \begin{bmatrix} 1 & * & * & * \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix},\\ & \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}, \ \begin{bmatrix} 0 & 1 & * & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}, \ \begin{bmatrix} 1 & * & * & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}, \ \begin{bmatrix} 0 & 1 & 0 & * \\ 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 \end{bmatrix}, \ \begin{bmatrix} 1 & * & 0 & * \\ 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 \end{bmatrix}, \ \begin{bmatrix} 1 & 0 & * & * \\ 0 & 1 & * & * \\ 0 & 0 & 0 & 0 \end{bmatrix}, \\ & \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}, \ \begin{bmatrix} 1 & * & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix},\ \begin{bmatrix} 1 & 0 & * & 0 \\ 0 & 1 & * & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}, \ \begin{bmatrix} 1 & 0 & 0 & * \\ 0 & 1 & 0 & * \\ 0 & 0 & 1 & * \end{bmatrix}, \end{align*}
- Here are all possible $4\!\times\!3$ matrices in RREF (reduced row echelon form). There are eight of them. \begin{align*} & \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \\ & \begin{bmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \quad \begin{bmatrix} 0 & 1 & * \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix},\quad \begin{bmatrix} 1 & * & * \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \\ & \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \quad \begin{bmatrix} 1 & * & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \quad \begin{bmatrix} 1 & 0 & * \\ 0 & 1 & * \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \\ & \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}. \end{align*}
- Notice that in all the matrices listed in the preceding item the bottom row is the zero row. By removing that zero row we would get all possible $3\!\times\!3$ matrices in RREF (reduced row echelon form). Thus, there is eight different types of $3\!\times\!3$ matrices in RREF (reduced row echelon form). This is true in general: If $m\geq n$, than the number of different types of $m\!\times\!n$ matrices in RREF is the same as the number of different types of $n\!\times\!n$ matrices in RREF.
- Another good exercise is to think of the above matrices as augmented matrices of systems of equations and state for each corresponding system whether it has: No Solutions (NS), Unique Solution (US), Infinitely Many Solutions (MS).
- Another interesting exercise, but for Math 309, is to calculate how many $m\!\times\!n$ matrices are in RREF. Just for the record: Let $k$ be a nonnegative integer and let $m, n$ be positive integers such that $k \leq m \leq n.$ It turns out that there are exactly \[ \displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!} \] matrices of size $m\!\times\!n$ with $k$ pivots (leading $1$s). The symbol $\displaystyle \binom{n}{k}$ is the standard notation for the binomial coefficient $n$-choose-$k$. Since an arbitrary $m\!\times\!n$ matrix can have $k \in \{0,1,\ldots,m\}$ pivots, it follows that the number of possible RREF types for an $m\!\times\!n$ matrix is \[ \sum_{k=0}^m \binom{n}{k}. \] For example, with $m=3$ and $n=4$, as seen above, there are \[ \binom{4}{0} + \binom{4}{1} + \binom{4}{2} + \binom{4}{3} = 1 + 4 + 6 + 4 = 15. \] possible RREF types of matrices. It is interesting to observe that for an $n\!\times\!n$ matrix there are \[ \sum_{k=0}^n \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n-1} + \binom{n}{n} = 2^n \] possible RREF types. If you take Math 309 you will understand the background of these formulas.
- In conclusion, for an $m\!\times\!n$ matrix with $m\lt n$ there are \[ \sum_{k=0}^m \binom{n}{k} \] possible RREF types and if $m \geq n$ there are \[ 2^n \] possible RREF types.
- Read Section 1.1 and Section 1.2. Assigned problems for Section 1.1: 3, 6, 7, 5, 9, 11,12, 16, 17, 18, 21, 22, 23, 24, 25, 27, 31, 33. Assigned problems for Section 1.2: 3, 5, 6, 7, 8, 12, 17-31.
-
On Friday I wanted to solve the following system of linear equations:
\begin{alignat*}{8}
&x_1 & & + &&x_2 & & - &&2 &&x_3 &&= -&&5\\
2 &x_1 & & - &&x_2 & & + && &&x_3 &&= &&8 \\
3 &x_1 & & && & & - && && x_3 &&= &&3
\end{alignat*}
This system is solved by row reducing its augmented matrix:
\begin{align*}
\left[\!\begin{array}{crr|r}
1 & 1 & -2 & -5 \\
2 & -1 & 1 & 8 \\
3 & 0 & -1 & 3
\end{array}\! \right] & \sim
\left[\!\begin{array}{crr|r}
1 & 1 & -2 & -5 \\
0 & -3 & 5 & 18 \\
0 & -3 & 5 & 18
\end{array}\! \right] \quad \begin{array}{l}
\text{(two row replacements)}
\end{array} \\
& \sim
\left[\!\begin{array}{crr|r}
1 & 1 & -2 & -5 \\
0 & -3 & 5 & 18 \\
0 & 0 & 0 & 0
\end{array}\! \right] \quad \begin{array}{l}
\text{(one row replacements)} \end{array} \\
& \sim
\left[\!\begin{array}{crr|r}
1 & 1 & -2 & -5 \\
0 & 1 & -5/3 & -6 \\
0 & 0 & 0 & 0
\end{array}\! \right] \quad \begin{array}{l}
\text{(one row scaling)} \\[-5pt]
\text{(and one row replacements to obtain} \\[-6pt]
\text{the matrix below)}
\end{array} \\
& \sim
\left[\!\begin{array}{crr|r}
1 & 0 & -1/3 & 1 \\
0 & 1 & -5/3 & -6 \\
0 & 0 & 0 & 0
\end{array}\! \right] \quad \begin{array}{l}
\text{This matrix is in Reduced Row Echelon Form.} \\[-5pt]
\text{I always like to row reduce a matrix} \\[-5pt]
\text{to its RREF - Reduced Row Echelon Form.}
\end{array}
\end{align*}
Why are the matrices presented above row equivalent?
- On the first line, the two matrices are row equivalent since the matrix on the right is obtained from the matrix on the left by performing two row operations. The first row operation was a row replacement: the second row $\left[\!\begin{array}{crr|r} 2 & -1 & 1 & 8 \end{array}\! \right]$ is replaced by the sum of itself and the multiple of the first row $ \left[\!\begin{array}{crr|r} 1 & 1 & -2 & -5 \end{array}\! \right]$ by $-2$: \begin{align*} \left[\!\begin{array}{crr|r} 2 & -1 & 1 & 8 \end{array}\! \right] + (-2) \left[\!\begin{array}{crr|r} 1 & 1 & -2 & -5 \end{array}\! \right] & = \left[\!\begin{array}{crr|r} 2 & -1 & 1 & 8 \end{array}\! \right] + \left[\!\begin{array}{crr|r} -2 & -2 & 4 & 10 \end{array}\! \right] \\ & = \left[\!\begin{array}{crr|r} 2 - 2 & -1 - 2 & 1 + 4 & 8 + 10 \end{array}\! \right] \\ & = \left[\!\begin{array}{crr|r} 0 & -3 & 5 & 18 \end{array}\! \right] \end{align*} The second row operation was again a row replacement: the third row $\left[\!\begin{array}{crr|r} 3 & 0 & -1 & 3 \end{array}\! \right]$ is replaced by the sum of itself and the multiple of the first row $ \left[\!\begin{array}{crr|r} 1 & 1 & -2 & -5 \end{array}\! \right]$ by $-3$: \begin{align*} \left[\!\begin{array}{crr|r} 3 & 0 & -1 & 3 \end{array}\! \right] + (-3) \left[\!\begin{array}{crr|r} 1 & 1 & -2 & -5 \end{array}\! \right] & = \left[\!\begin{array}{crr|r} 3 & 0 & -1 & 3 \end{array}\! \right] + \left[\!\begin{array}{crr|r} -3 & -3 & 6 & 15 \end{array}\! \right] \\ & = \left[\!\begin{array}{crr|r} 3 - 3 & 0 - 3 & -1 + 6 & 3 + 15 \end{array}\! \right] \\ & = \left[\!\begin{array}{crr|r} 0 & -3 & 5 & 18 \end{array}\! \right] \end{align*} Thinking about the corresponding system of linear equations, what we achieved at this step is that we eliminated unknown $x_1$ from the second and the third equation.
- The matrix on the second line is row equivalent to the matrix above it since it is obtained from the matrix above it by performing a row replacement: the third row $\left[\!\begin{array}{crr|r} 0 & -3 & 5 & 18 \end{array}\! \right]$ is replaced by the sum of itself and the second row $ \left[\!\begin{array}{crr|r} 0 & -3 & 5 & 18 \end{array}\! \right]$ multiplied by $-1$: \begin{align*} \left[\!\begin{array}{crr|r} 0 & -3 & 5 & 18 \end{array}\! \right] + (-1) \left[\!\begin{array}{crr|r} 0 & -3 & 5 & 18 \end{array}\! \right] & = \left[\!\begin{array}{crr|r} 0 & 0 & 0 & 0 \end{array}\! \right] \end{align*} Thinking about the corresponding system of linear equations, what we achieved at this step is that we reduced the number of equations from three to two.
- The matrix on the third line is row equivalent to the matrix above itself since it is obtained from the matrix above itself by performing a row scaling: the second row $\left[\!\begin{array}{crr|r} 0 & -3 & 5 & 18 \end{array}\! \right]$ is replaced by the multiple of itself $-1/3$: \[ (-1/3) \left[\!\begin{array}{crr|r} 0 & -3 & 5 & 18 \end{array}\! \right] = \left[\!\begin{array}{crr|r} 0 & 1 & -5/3 & -6 \end{array}\! \right] \] Thinking about the corresponding system of linear equations, what we achieved at this step is that we now have the coefficient $1$ with the unknown $x_2$ in the second equation.
- The matrix on the fourth line is row equivalent to the matrix above itself since it is obtained from the matrix above itself by performing a row replacement: the first row $\left[\!\begin{array}{crr|r} 1 & 1 & -2 & -5 \end{array}\! \right]$ is replaced by the sum of itself and the second row $ \left[\!\begin{array}{crr|r} 0 & 1 & -5/3 & -6 \end{array}\! \right]$ multiplied by $-1$: \begin{align*} \left[\!\begin{array}{crr|r} 1 & 1 & -2 & -5 \end{array}\! \right] + (-1) \left[\!\begin{array}{crr|r} 0 & 1 & -5/3 & -6 \end{array}\! \right] & = \left[\!\begin{array}{crr|r} 1 & 0 & -1/3 & 1 \end{array}\! \right] \end{align*} Thinking about the corresponding system of linear equations, what we achieved at this step is that we eliminated unknown $x_2$ from the first equation.
- Since the matrices \[ \left[\!\begin{array}{crr|r} 1 & 1 & -2 & -5 \\ 2 & -1 & 1 & 8 \\ 3 & 0 & -1 & 3 \end{array}\! \right] \sim \left[\!\begin{array}{crr|r} 1 & 0 & -1/3 & 1 \\ 0 & 1 & -5/3 & -6 \\ 0 & 0 & 0 & 0 \end{array}\! \right] \] are row equivalent, the corresponding systems are equivalent systems. That is, the solution set of the given system is the same as the solution set of the system \begin{alignat*}{8} &x_1 & & && & & - &&1/3 &&\, x_3 &&= &&1\\ & & & &&x_2 & & - &&5/3 &&\, x_3 &&= -&&6 \end{alignat*} In the preceding system there is no restriction on $x_3$; $x_3$ is so-called free variable. I like introducing a new name for the free variable, say $s$. Then the solution of the preceding system is given by \begin{equation*} x_1 = \frac{1}{3} s + 1, \quad x_2 = \frac{5}{3} s - 6, \quad x_3 = s, \end{equation*} where $s$ is an arbitrary real number. In set notation, $s \in \mathbb{R}.$ For example, with $s=3$ we obtain that \[ x_1 = 2, \quad x_2 = -1, \quad x_3 = 3, \] is a solution to the given system.
- It is always fun to verify whether the solution realy satisfies the given system. Substitute $x_1 = \frac{1}{3} s + 1,$ $x_2 = \frac{5}{3} s - 6$ and $x_3 = s,$ and see what we get: \begin{alignat*}{8} &(1/3 \, s + 1) & & + &&(5/3 \, s - 6) & & - &&2 &&s &&= 2s - 5 +2s = -&&5\\ 2 &(1/3 \, s + 1) & & - &&(5/3 \, s - 6) & & + && &&s &&= -s + 8 + s = &&8 \\ 3 &(1/3 \, s + 1) & & && & & - && && s &&= s + 3 - s = &&3 \end{alignat*} Hence we found all the solutions of the given system.
-
Finally, let us illustrate the system
\begin{alignat*}{8}
&x_1 & & + &&x_2 & & - &&2 &&x_3 &&= -&&5\\
2 &x_1 & & - &&x_2 & & + && &&x_3 &&= &&8 \\
3 &x_1 & & && & & - && && x_3 &&= &&3
\end{alignat*}
geometrically in $x_1x_2x_3$-space, that is in the space $\mathbb{R}^3.$ Each equation is represented by a plane. The first equation is represented by the brown plane, the second equation is represented by the blue plane and the third equation is represented by the green plane.
-
A natural question is: How are row operations reflected in the illustration of the system with planes?
The systems that correspond to the row equivalent matrices on lines 2 and 3 in the row reduction above are illustrated by the same picture; the planes do not change. The system corresponding to the last matrix in Reduced Row Echelon Form is represented by the simplest planes. What is the simplicity of these planes? The first plane is parallel to the coordinate axis $x_2.$ The second plane is parallel to the coordinate axis $x_1.$ (Being parallel to coordinate ases is a very desirable feature for a plane.)Given System Systems 2 and 3 "Row Reduced" System \begin{alignat*}{8} &x_1 & & + &&x_2 & & - &&2 &&x_3 &&= -&&5\\ 2 &x_1 & & - &&x_2 & & + && &&x_3 &&= &&8 \\ 3 &x_1 & & && & & - && && x_3 &&= &&3 \end{alignat*} \begin{alignat*}{8} &x_1 & & + &&x_2 & & - &&\phantom{5/} 2&&x_3 &&= -&&5\\ & & & &&x_2 & & - &&5/3 &&x_3 &&= -&&6 \\ & & & && & & && && && && \end{alignat*} \begin{alignat*}{8} &x_1 & & && & & - &&1/3 &&x_3 &&= &&1\\ & & & \phantom{+} &&x_2 & & - &&5/3 &&x_3 &&= -&&6 \\ & & & && & & && && && && \end{alignat*} 
-
Now recall the system that we solved on Friday:
\begin{alignat*}{8}
&x_1 & & + &&x_2 & & - &&2 &&x_3 &&= &&5\\
2 &x_1 & & - &&x_2 & & + && &&x_3 &&= &&8 \\
3 &x_1 & & && & & - && && x_3 &&= &&3
\end{alignat*}
The only difference is that in the first equation $-5$ is replaced by $5$. We found out that this system is inconsistent. That is, there is no solution. Below is the corresponding illustration in $\mathbb{R}^3.$
- Before starting with linear algebra, I want to illustrate two important mathematical questions on the linear equation with one unknown (the simplest linear equation). These two questions we will encounter later in a more complicated setting.
- Consider the general form of the linear equation with one independent variable \[ \color{green}{a} \color{red}{x} = \color{green}{b}. \] In this equation $\color{red}{x}$ is unknown, while $\color{green}{a}$ and $\color{green}{b}$ are coefficients; that is known, but not specified, real numbers. We seek to find all real numbers which are solutions of $\color{green}{a} \color{red}{x} = \color{green}{b}.$ A real number $s$ is a solution of $\color{green}{a} \color{red}{x} = \color{green}{b}$ if the expression $\color{green}{a} s = \color{green}{b}$ is an algebraic identity.
-
Two important questions are as follows:
- Question 1: Existence of solution Does the equation $\color{green}{a} \color{red}{x} = \color{green}{b}$ have a solution?
- Question 2: Uniqueness of solution Provided that the equation $\color{green}{a} \color{red}{x} = \color{green}{b}$ has a solution, is the solution unique?
- The answers to these questions depend on the numbers $\color{green}{a}$ and $\color{green}{b}$. Below are the answers with a geometric illustration.
-
The question of the Existence of solution leads to the following dichotomy:
- Solution does not exist: If $\color{green}{a}=0$ and $\color{green}{b} \neq 0,$ than the equation $\color{green}{a} \color{red}{x} = \color{green}{b}$ does not have a solution.
- Solution does exist: If $\color{green}{a}\neq 0$ or $\color{green}{b} = 0,$ than the equation $\color{green}{a} \color{red}{x} = \color{green}{b}$ does have a solution.
-
The question of the Uniqueness of solution leads to the following dichotomy:
- Solution is not unique: If $\color{green}{a}=0$ and $\color{green}{b} = 0,$ than the solution of the equation $\color{green}{a} \color{red}{x} = \color{green}{b}$ is not unique. In fact, every real number is a solution since $0\cdot s = 0$ is an algebraic identity for all real numbers $s.$
- Solution is unique: If $\color{green}{a}\neq 0,$ than the solution of the equation $\color{green}{a} \color{red}{x} = \color{green}{b}$ is unique.
-
The two dichotomies presented above give us the following trichotomy:
- Solution does not exist: $\color{green}{a}=0$ and $\color{green}{b} \neq 0.$
- Solution is not unique: $\color{green}{a}=0$ and $\color{green}{b} = 0.$
- Solution is unique: $\color{green}{a}\neq 0.$
- Stay tuned for the answers to these questions for systems of linear equations.
- The information sheet
- We will start with Section 1.1 Systems of Linear Equations. Suggested problems are 3, 6, 7, 5, 9, 11, 12, 16, 17, 18, 21, 22, 23, 24, 25, 27, 31, 33.
-
Just reading Section 1.1 you will experience that linear algebra is a subject full of new terminology:
- linear equation,
- coefficients of a linear equation,
- system of linear equations or linear system or just system,
- a solution of a linear system,
- the solution set of a linear system,
- consistent linear system,
- inconsistent linear system,
- equivalent systems,
- coefficient matrix of a system,
- augmented matrix of a system,
- elementary row operations,
- row-equivalent matrices.
- Learning the terminology of a field is crucial to getting to understand that field. This is true in general and particularly true in Linear Algebra. Therefore I started a webpage with Glossary of Linear Algebra Terms with my comments.
-
What is the oldest linear algebra problem?
-
Clay tablet VAT 8389 from the Old Babylonian period, from 2000 to 1600 BC, contains what is believed to be the earliest word problem that can be interpreted as a system of linear equations:
A translation of this word problem into a system of linear equations is as follows: \begin{alignat*}{4} &x_1 & &\ + &x_2 & = 1800 \\ \tfrac{2}{3} &x_1 & &- \tfrac{1}{2} &x_2 & = \phantom{1}500. \end{alignat*} -
Problem 40 of the Rhind papyrus which is dated to 1550 BC is:
Denote by $x_1$ the smallest number and by $x_2$ the common difference. After simplification, the above problem translates into the following system of linear equations: \begin{alignat*}{5} 5 &x_1 & & + 10 &x_2 & = 100 \\ \tfrac{11}{7} &x_1 & & - \phantom{1}\tfrac{2}{7} &x_2 & = \phantom{10}0. \end{alignat*} -
Most importantly for us, the oldest known treatment of systems of linear equations from antiquity which resembles the methods that we will use in this class is in Chapter 8 of the Chinese textbook Nine Chapters of the Mathematical Art which is at least 1800 years old.
-
Clay tablet VAT 8389 from the Old Babylonian period, from 2000 to 1600 BC, contains what is believed to be the earliest word problem that can be interpreted as a system of linear equations: