- Here is a list of topics for the final exam.
- This probelm is related to Exercse 23 in Section 6.3. Given \[ A = \left[ \begin{array}{cccc} 1 & 2 & 2 & 3 \\ 2 & 1 & 1 & 0 \\ 3 & 4 & 4 & 5 \end{array} \right] \quad \text{and} \quad \mathbf{y} = \left[ \begin{array}{c} 1 \\ 2 \\ 3\\ 4 \end{array} \right], \] find a vector $\mathbf{v} \in \operatorname{Nul}A$ and a vector $\mathbf{w} \in \operatorname{Row} A$ such that \[ \mathbf{y} = \mathbf{v} + \mathbf{w}. \]
-
Here is a calculation of a singular value decomposition of the matrix
\[
A = \left[\!\begin{array}{rrr}
3 & -1 & 1 \\
-1 & 3 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1 \end{array}\right]
\]
To find the singular values and right singular vectors we calculate the matrix
\[
A^\top \!A = \left[\!\begin{array}{rrrr}
3 & -1 & 1 & 1 \\
-1 & 3 & 1 & 1 \\
1 & 1 & 1 & 1 \end{array}\right]
\left[\!\begin{array}{rrr}
3 & -1 & 1 \\
-1 & 3 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1 \end{array}\right] =
\left[\!\begin{array}{rrr}
12 & -4 & 4 \\
-4 & 12 & 4 \\
4 & 4 & 4 \end{array}\right] =
4 \left[\!\begin{array}{rrr}
3 & -1 & 1 \\
-1 & 3 & 1 \\
1 & 1 & 1 \end{array}\right].
\]
Observe that adding the first two columns and subtracting twice the third column gives the zero vector. Hence $\lambda_3 = 0$ is an eigenvalue of $A^\top\!A$ and a corresponding eigenvector is $\bigl[ -1 \ -1 \ \ 2 \bigr]^\top$. Since each row of $A^\top\!A$ sums to $12$, $\lambda_2 = 12$ is an eigenvalue of $A^\top\!A$ and a corresponding eigenvector is $\bigl[ 1 \ \ 1 \ \ 1 \bigr]^\top$. Since the vector $\bigl[ 1 \ -1 \ \ 0 \bigr]^\top$ is orthogonal to both earlier found eigenvectors it also must be an eigenvector of $A^\top\!A$. The corresponding eigenvalue is $\lambda_1 = 16$. Thus the singular values of $A$ are $\sigma_1 = 4$ and $\sigma_2 = 2\sqrt{3}$, and the matrices $\Sigma$ and $V$ are as follows
\[
\Sigma = \left[\!\begin{array}{rrr}
4 & 0 & 0 \\
0 & 2\sqrt{3} & 0 \\
0 & 0 & 0 \\
0 & 0 & 0 \end{array}\right]
\qquad V = \left[\!\begin{array}{rrr}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{3}} & -\frac{1}{\sqrt{6}} \\
-\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{3}} & -\frac{1}{\sqrt{6}} \\
0 & \frac{1}{\sqrt{3}} & \frac{2}{\sqrt{6}} \end{array}\right] = \bigl[ \mathbf{v}_1 \ \mathbf{v}_2 \ \mathbf{v}_3 \bigr].
\]
To find a $4\!\times\!4$ orthogonal matrix $U$ we first normalize vectors
\[
A \left[\!\begin{array}{r}
1 \\
-1 \\
0 \end{array}\right] = \left[\!\begin{array}{rrr}
3 & -1 & 1 \\
-1 & 3 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1 \end{array}\right] \left[\!\begin{array}{r}
1 \\
-1 \\
0 \end{array}\right] = \left[\!\begin{array}{r}
4 \\
-4 \\
0 \\
0 \end{array}\right] = 4 \left[\!\begin{array}{r}
1 \\
-1 \\
0 \\
0 \end{array}\right], \quad \text{hence} \quad \mathbf{u}_1 = \left[\!\begin{array}{r}
\frac{1}{\sqrt{2}} \\
-\frac{1}{\sqrt{2}} \\
0 \\
0 \end{array}\right],
\]
and
\[
A \left[\!\begin{array}{r}
1 \\
1 \\
1 \end{array}\right] = \left[\!\begin{array}{rrr}
3 & -1 & 1 \\
-1 & 3 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1 \end{array}\right] \left[\!\begin{array}{r}
1 \\
1 \\
1 \end{array}\right] = \left[\!\begin{array}{r}
3 \\
3 \\
3 \\
3 \end{array}\right] = 3 \left[\!\begin{array}{r}
1 \\
1 \\
1 \\
1 \end{array}\right], \quad \text{hence} \quad \mathbf{u}_2 = \left[\!\begin{array}{r}
\frac{1}{2} \\
\frac{1}{2} \\
\frac{1}{2} \\
\frac{1}{2} \end{array}\right].
\]
Just to confirm the equalities that were important in deduction of the construction of the matrix $U$, we confirm that $A\mathbf{v}_1 = \sigma_1 \mathbf{u}_1$ and $A\mathbf{v}_2 = \sigma_2 \mathbf{u}_2$:
\[
\left[\!\begin{array}{rrr}
3 & -1 & 1 \\
-1 & 3 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1 \end{array}\right] \left[\!\begin{array}{r}
\frac{1}{\sqrt{2}} \\
-\frac{1}{\sqrt{2}} \\
0 \end{array}\right] = 4 \left[\!\begin{array}{r}
\frac{1}{\sqrt{2}} \\
-\frac{1}{\sqrt{2}} \\
0 \\
0 \end{array}\right] \quad \text{and} \quad
\left[\!\begin{array}{rrr}
3 & -1 & 1 \\
-1 & 3 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1 \end{array}\right] \left[\!\begin{array}{r}
\frac{1}{\sqrt{3}} \\
\frac{1}{\sqrt{3}} \\
\frac{1}{\sqrt{3}} \end{array}\right] = 2\sqrt{3} \left[\!\begin{array}{r}
\frac{1}{2} \\
\frac{1}{2} \\
\frac{1}{2} \\
\frac{1}{2} \end{array}\right]
\]
It has been established in class that $\mathbf{u}_1$ and $\mathbf{u}_2$ form an orthonormal basis for $\operatorname{Col}A$. To complete the matrix $U$ we need an orthonormal basis for $\mathbb{R}^4$. There are two ways to approach finding vectors $\mathbf{u}_3$ and $\mathbf{u}_4$.
First method Since the space $\operatorname{Nul}\bigl(A^\top\bigr)$ is the orthogonal complement of $\operatorname{Col}A$, we can simply find the nullspace of $A^\top$, and then find two orhonormal vectors in $\operatorname{Nul}\bigl(A^\top\bigr).$ Here we go: \[ \textstyle \left[\!\begin{array}{rrrr} 3 & -1 & 1 & 1 \\ -1 & 3 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{array}\right] \sim \left[\!\begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 0 & 4 & 2 & 2 \\ 0 & -4 & -2 & -2 \end{array}\right] \sim \left[\!\begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 0 & 1 & 1/2 & 1/2 \\ 0 & 0 & 0 & 0 \end{array}\right] \sim \left[\!\begin{array}{rrrr} 1 & 0 & 1/2 & 1/2 \\ 0 & 1 & 1/2 & 1/2 \\ 0 & 0 & 0 & 0 \end{array}\right] \] Thus, \[ \operatorname{Nul}\bigl(A^\top\bigr) = \left\{ s \left[\!\begin{array}{r} -1 \\ -1 \\ 0 \\ 2 \end{array}\right] + t \left[\!\begin{array}{r} -1 \\ -1 \\ 2 \\ 0 \end{array}\right] \ : \ s, t \in \mathbb{R} \right\}. \] All the vectors in $\operatorname{Nul}\bigl(A^\top\bigr)$ are orthogonal to $\mathbf{u}_1$ and $\mathbf{u}_2$ (verify this). There are many pairs of orthonormal vectors in $\operatorname{Nul}\bigl(A^\top\bigr).$ One pair that cough my attention is obtained with $s=1/2$, $t=1/2$ and $s=1/2$, $t=-1/2$ and then normalized. That is the pair \[ \mathbf{u}_3 = \left[\!\begin{array}{r} -\frac{1}{2} \\ - \frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2} \end{array}\right] \quad \text{and} \quad \mathbf{u}_4 = \left[\!\begin{array}{c} 0 \\ 0 \\ -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{array}\right] \] Finally, \[ U = \left[\!\begin{array}{rrrr} \frac{1}{\sqrt{2}} & \frac{1}{2} & -\frac{1}{2} & 0 \\ -\frac{1}{\sqrt{2}} & \frac{1}{2} & -\frac{1}{2} & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} & -\frac{1}{\sqrt{2}} \\ 0 & \frac{1}{2} & \frac{1}{2} & \frac{1}{\sqrt{2}} \end{array}\right]. \] To celebrate our work we verify \[ \left[\!\begin{array}{rrr} 3 & -1 & 1 \\ -1 & 3 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array}\right] = \left[\!\begin{array}{rrrr} \frac{1}{\sqrt{2}} & \frac{1}{2} & -\frac{1}{2} & 0 \\ -\frac{1}{\sqrt{2}} & \frac{1}{2} & -\frac{1}{2} & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} & -\frac{1}{\sqrt{2}} \\ 0 & \frac{1}{2} & \frac{1}{2} & \frac{1}{\sqrt{2}} \end{array}\right] \left[\!\begin{array}{rrr} 4 & 0 & 0 \\ 0 & 2\sqrt{3} & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right] \left[\!\begin{array}{rrr} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 \\ \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} \\ -\frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{6}} & \frac{2}{\sqrt{6}} \end{array}\right] . \]
Second method To find two additional vectors in $\mathbb R^4$ which are orthogonal to the first two vectors in $U$ we apply Gram-Schmidt orthogonalization to the linearly independent vectors (a basis for $\mathbb{R}^4$) \[ \left[\!\begin{array}{r} 1 \\ -1 \\ 0 \\ 0 \end{array}\right] , \quad \left[\!\begin{array}{r} 1 \\ 1 \\ 1 \\ 1 \end{array}\right], \quad \left[\!\begin{array}{r} 1 \\ 0 \\ 0 \\ 0 \end{array}\right], \quad \left[\!\begin{array}{r} 0 \\ 0 \\ 1 \\ 0 \end{array}\right] \] The first two vectors are already orthogonal. To get the third vector we calculate \[ \left[\!\begin{array}{r} 1 \\ 0 \\ 0 \\ 0 \end{array}\right] - \frac{1}{2} \left[\!\begin{array}{r} 1 \\ -1 \\ 0 \\ 0 \end{array}\right] - \frac{1}{4} \left[\!\begin{array}{r} 1 \\ 1 \\ 1 \\ 1 \end{array}\right] = \frac{1}{4} \left[\!\begin{array}{r} 1 \\ 1 \\ -1 \\ -1 \end{array}\right] \] We can ignore the scaling coefficient $1/4$ and continue with three orthogonal vectors \[ \left[\!\begin{array}{r} 1 \\ -1 \\ 0 \\ 0 \end{array}\right] , \quad \left[\!\begin{array}{r} 1 \\ 1 \\ 1 \\ 1 \end{array}\right], \quad \left[\!\begin{array}{r} 1 \\ 1 \\ -1 \\ -1 \end{array}\right] \] To find the fourth vector we calculate \[ \left[\!\begin{array}{r} 0 \\ 0 \\ 1 \\ 0 \end{array}\right] - 0 \left[\!\begin{array}{r} 1 \\ -1 \\ 0 \\ 0 \end{array}\right] - \frac{1}{4} \left[\!\begin{array}{r} 1 \\ 1 \\ 1 \\ 1 \end{array}\right] -\frac{-1}{4} \left[\!\begin{array}{r} 1 \\ 1 \\ -1 \\ -1 \end{array}\right] = \frac{1}{2} \left[\!\begin{array}{r} 0 \\ 0 \\ 1 \\ -1 \end{array}\right] \] Thus the vectors (at this point it is a good idea to pause and quickly check that what I claim here is true) \[ \left[\!\begin{array}{r} 1 \\ -1 \\ 0 \\ 0 \end{array}\right] , \quad \left[\!\begin{array}{r} 1 \\ 1 \\ 1 \\ 1 \end{array}\right], \quad \left[\!\begin{array}{r} 1 \\ 1 \\ -1 \\ -1 \end{array}\right], \quad \left[\!\begin{array}{r} 0 \\ 0 \\ 1 \\ -1 \end{array}\right] \] form an orthogonal basis for $\mathbb R^4$. Consequently \[ U = \left[\!\begin{array}{rrrr} \frac{1}{\sqrt{2}} & \frac{1}{2} & \frac{1}{2} & 0 \\ -\frac{1}{\sqrt{2}} & \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & \frac{1}{2} & -\frac{1}{2} & \frac{1}{\sqrt{2}} \\ 0 & \frac{1}{2} & -\frac{1}{2} & -\frac{1}{\sqrt{2}} \end{array}\right] \]
- Suggested problems for Section 7.4: 3, 7, 11, 13, 14, 15, 17, 21
- SM. Let $m$ be a positive integer. Let $S$ be a symmetric $m\!\times\!m$ matrix. Then there exist real numbers \[ \lambda_1 \geq \lambda_1 \geq \cdots \geq \lambda_m \] and an orthonormal basis \[ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_m \] of $\mathbb{R}^m$ such that \[ S \mathbf{v}_k = \lambda_k \mathbf{v}_k \quad \text{for all} \quad k \in \{1,\ldots,m\}. \] This fact can conveniently be written in the matrix form as \[ S = V D V^\top \] where \[ V = \bigl[ \mathbf{v}_1 \ \ \mathbf{v}_2 \ \cdots \ \mathbf{v}_m \bigr] \quad \text{and} \quad D = \left[\! \begin{array}{cccc} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots &\lambda_m \end{array}\!\right]. \]
- SR. Let $n$ and $m$ be positive integers. Let $A$ be an $n\!\times\!m$ matrix. The matrices $A^\top A$ and $A$ have the same rank.
- Let $n$ and $m$ be positive integers. Let $A$ be an $n\!\times\!m$ matrix. Then $A^\top A$ is a symmetric $m\!\times\!m$ matrix. By previous item SM there exist real numbers \[ \lambda_1 \geq \lambda_1 \geq \cdots \geq \lambda_m \] and an orthonormal basis \[ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_m \] of $\mathbb{R}^m$ such that \[ A^\top A \mathbf{v}_k = \lambda_k \mathbf{v}_k \quad \text{for all} \quad k \in \{1,\ldots,m\}. \] In this case $\lambda_k$ can be expressed in terms of $A$ and $\mathbf{v}_k.$ To see this calculate the dot product \[ \mathbf{v}_k \cdot \bigl(A^\top A \mathbf{v}_k \bigr) = \lambda_k (\mathbf{v}_k \cdot \mathbf{v}_k ) = \lambda_k. \] Using the properties of the transpose we deduce \[ \mathbf{v}_k \cdot \bigl(A^\top A \mathbf{v}_k \bigr) = \bigl( A \mathbf{v}_k\bigr) \cdot \bigl(A \mathbf{v}_k \bigr) = \| A \mathbf{v}_k\|^2. \] From the last two displayed equalities we deduce that \[ \lambda_k = \| A \mathbf{v}_k\|^2. \]
- Suggested problems for Section 7.3: 1, 3, 5, 9, 11, 12
-
In Section 7.2 in the book the author does not discus quadratic forms with three variables. This is usually done in Math 224. Here are some animations that might help you understand the quadratic form $x_1^2 + x_2^2 - x_3^2$. Here I show the surfaces in ${\mathbb R}^3$ with equations $x_1^2 + x_2^2 - x_3^2 = c$ for different values of $c$. These surfaces are called hyperboloids. You can read more at the Wikipedia
Hyperboloid page. One sheet hyperboloids are often encountered in art, see these Wikipedia pages Hyperboloid structure and list of hyperboloid structures, do not miss the Gallery at the bottom of the last page.
Place the cursor over the image to start the animation.
Five of the above level surfaces.
- I wrote a draft of a list of topics for Exam 2.
- Suggested problems for Section 7.2: 1, 3, 5, 7, 9, 13, 17, 19, 20, 21, 23, 25
-
Do the following problem: Consider the following four data points
\[
( 0, 0, 5), \ \ (3, 0, 6), \ \ (3, 3, 14), \ \ (0, 3, 9).
\]
- Find the equation $z = \beta_0 + \beta_1 x +\beta_2 y$ of the least-squares plane that best fits the data points.
- Find the coordinates of the dark green points and the teal points in the picture below.
- Calculate the residual vector and the least-squares error.
- Find the equation of the plane through the data points \[ ( 0, 0, 5), \ \ (3, 0, 6), \ \ (0, 3, 9). \] Show that the least-squares error is larger for this plane than the error for the least-squares plane.
In this image the the navy blue points are the given data points and the light blue plane is the least-squares plane that best fits these data points. The dark green points are their projections onto the $xy$-plane. The teal points are the corresponding points in the least-square plane.
-
This is the continuation of my explorations from February 21. Here I present $4\!\times\!4$ matrices $Q$ with the following properties:
- The entries of $Q$ are in the set \[ \Bigl\{\ \frac{a}{b} \, \bigl| \bigr. \, a \in \{-9,-8,\ldots,-1,0,1,\ldots, 8, 9\}, \ b \in \{1,\ldots, 8, 9\} \Bigr\} \]
- $Q^{\top} Q = Q Q^{\top} = I_4$ (that is $Q$ has orthonormal columns and rows)
-
I wrote a Mathematica code that searched for all such matrices. There are a lot of them. However, I believe that all such matrices can be obtained from only twelve matrices by using simple operations. I list these twelve matrices in the next item. I have convinced myself that each desirable matrix described in the above item can be obtained from one of the twelve matrices listed in the next item by application of the following operations:
- the transpose
- a permutation of columns
- a permutation of rows
- multiplication of some rows by $-1$
- multiplication of some columns by $-1$
- These twelve matrices are very special: \[ \left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right], \quad \left[ \begin{array}{cccc} \frac{5}{9} & \frac{2}{9} & \frac{4}{9} & -\frac{2}{3} \\ \frac{2}{3} & -\frac{4}{9} & \frac{2}{9} & \frac{5}{9} \\ \frac{4}{9} & \frac{2}{3} & -\frac{5}{9} & \frac{2}{9} \\ -\frac{2}{9} & \frac{5}{9} & \frac{2}{3} & \frac{4}{9} \end{array} \right], \quad \left[ \begin{array}{cccc} \frac{1}{3} & -\frac{2}{9} & \frac{2}{9} & \frac{8}{9} \\ -\frac{2}{9} & \frac{8}{9} & \frac{1}{3} & \frac{2}{9} \\ \frac{2}{9} & \frac{1}{3} & -\frac{8}{9} & \frac{2}{9} \\ \frac{8}{9} & \frac{2}{9} & \frac{2}{9} & -\frac{1}{3} \end{array} \right], \] \[ \left[ \begin{array}{cccc} -\frac{1}{7} & \frac{4}{7} & \frac{4}{7} & \frac{4}{7} \\ \frac{4}{7} & -\frac{4}{7} & \frac{1}{7} & \frac{4}{7} \\ \frac{4}{7} & \frac{1}{7} & \frac{4}{7} & -\frac{4}{7} \\ \frac{4}{7} & \frac{4}{7} & -\frac{4}{7} & \frac{1}{7} \end{array} \right], \quad \left[ \begin{array}{cccc} \frac{2}{7} & -\frac{5}{7} & \frac{4}{7} & \frac{2}{7} \\ -\frac{5}{7} & \frac{2}{7} & \frac{4}{7} & \frac{2}{7} \\ \frac{4}{7} & \frac{4}{7} & \frac{1}{7} & \frac{4}{7} \\ \frac{2}{7} & \frac{2}{7} & \frac{4}{7} & -\frac{5}{7} \end{array} \right], \quad \left[ \begin{array}{cccc} \frac{5}{7} & -\frac{2}{7} & \frac{2}{7} & \frac{4}{7} \\ -\frac{2}{7} & \frac{4}{7} & \frac{5}{7} & \frac{2}{7} \\ \frac{2}{7} & \frac{5}{7} & -\frac{4}{7} & \frac{2}{7} \\ \frac{4}{7} & \frac{2}{7} & \frac{2}{7} & -\frac{5}{7} \end{array} \right], \] \[ \left[ \begin{array}{cccc} \frac{5}{6} & -\frac{1}{6} & \frac{1}{6} & \frac{1}{2} \\ -\frac{1}{6} & \frac{1}{2} & \frac{5}{6} & \frac{1}{6} \\ \frac{1}{6} & \frac{5}{6} & -\frac{1}{2} & \frac{1}{6} \\ \frac{1}{2} & \frac{1}{6} & \frac{1}{6} & -\frac{5}{6} \end{array} \right], \quad \left[ \begin{array}{cccc} -\frac{1}{5} & \frac{4}{5} & \frac{2}{5} & \frac{2}{5} \\ \frac{4}{5} & -\frac{1}{5} & \frac{2}{5} & \frac{2}{5} \\ \frac{2}{5} & \frac{2}{5} & \frac{1}{5} & -\frac{4}{5} \\ \frac{2}{5} & \frac{2}{5} & -\frac{4}{5} & \frac{1}{5} \end{array} \right], \quad \left[ \begin{array}{cccc} -\frac{2}{5} & \frac{2}{5} & \frac{1}{5} & \frac{4}{5} \\ \frac{2}{5} & -\frac{2}{5} & \frac{4}{5} & \frac{1}{5} \\ \frac{1}{5} & \frac{4}{5} & \frac{2}{5} & -\frac{2}{5} \\ \frac{4}{5} & \frac{1}{5} & -\frac{2}{5} & \frac{2}{5} \end{array} \right], \] \[ \left[ \begin{array}{cccc} -\frac{1}{5} & \frac{4}{5} & \frac{2}{5} & \frac{2}{5} \\ \frac{4}{5} & \frac{1}{5} & -\frac{2}{5} & \frac{2}{5} \\ \frac{2}{5} & -\frac{2}{5} & \frac{4}{5} & \frac{1}{5} \\ \frac{2}{5} & \frac{2}{5} & \frac{1}{5} & -\frac{4}{5} \end{array} \right], \quad \left[ \begin{array}{cccc} -\frac{5}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{2} \\ \frac{1}{6} & -\frac{5}{6} & \frac{1}{6} & \frac{1}{2} \\ \frac{1}{6} & \frac{1}{6} & -\frac{5}{6} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \end{array} \right], \quad \left[ \begin{array}{cccc} -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \end{array} \right]. \]
-
In Math 204 a common task is to look for an inverse of a small matrix. Guided by a desire to keep things simple I looked for all $3\!\times\!3$ matrices with entries in the set $\{-1,0,1,2,3\}$ and whose inverses have entries in the set
\[
\{-9,-8,\ldots,-1,0,1,\ldots, 8, 9\}.
\]
Again, I wrote a Mathematica program to search for all such matrices. It turns out that there are a lot of such matrices, hundreds of thousand of them. I wrote additional Mathematica code to convert found matrices into LaTeX code which I used to produce
this pdf file with a large number of such matrices. This pdf file is large, 5MB, 3119 pages. If you ever need such a matrix I hope you find it here.
In fact, invertible matrices with integer entries whose inverses also have integer entries are called unimodular matrices. You can learn more about unimodular matrices by reading the Wikipedia page dedicated to unimodular matrices.
- Suggested problems for Section 7.1: 3, 4, 9, 11, 15, 19, 23, 24, 25, 27, 30, 33, 35
-
There are important theorems in Section 7.1. Their proofs are presented in this item.
Theorem. All eigenvalues of a symmetric matrix are real.
Proof. Let $A$ be a symmetric $n\!\times\!n$ matrix and let $\lambda$ be an eigenvalue of $A$. Let $\vec{v} = \bigl[v_1 \ \ v_2 \ \ \cdots \ \ v_n \bigr]^\top$ be a corresponding eigenvector. Then $\vec{v} \neq \vec{0}.$ We allow the possibility that $\lambda$ and $v_1,$ $v_2,\ldots,$ $v_n$ are complex numbers. For a complex number $\alpha$ by $\overline{\alpha}$ we denote its complex conjugate. Recall that for a nonzero complex number $\alpha$ we have $\alpha\,\overline{\alpha} = |\alpha|^2 \gt 0.$ Since $\vec{v}$ is an eigenvector of $A$ corresponding to $\lambda$ we have \[ A \vec{v} = \lambda \vec{v}. \] Since $A$ is a all entries of $A$ are real numbers, taking the complex conjugate of both sides of the above equality we have \[ A\bigl[\overline{v_1} \ \ \overline{v_2} \ \ \cdots \ \ \overline{v_n} \bigr]^\top = \overline{\lambda} \bigl[\overline{v_1} \ \ \overline{v_2} \ \ \cdots \ \ \overline{v_n} \bigr]^\top. \] Here the complex conjugate of a complex number $z$ is denoted by $\overline{z}.$ Since $A$ is symmetric, that is $A=A^\top$, we also have \[ A^\top \bigl[\overline{v_1} \ \ \overline{v_2} \ \ \cdots \ \ \overline{v_n} \bigr]^\top = \overline{\lambda} \bigl[\overline{v_1} \ \ \overline{v_2} \ \ \cdots \ \ \overline{v_n} \bigr]^\top. \] Multiplying both sides of the last equation by $\vec{v}^\top = \bigl[v_1 \ \ v_2 \ \ \cdots \ \ v_n \bigr]$ we get \[ \vec{v}^\top A^\top \bigl[\overline{v_1} \ \ \overline{v_2} \ \ \cdots \ \ \overline{v_n} \bigr]^\top = \bigl[v_1 \ \ v_2 \ \ \cdots \ \ v_n \bigr] \overline{\lambda} \bigl[\overline{v_1} \ \ \overline{v_2} \ \ \cdots \ \ \overline{v_n} \bigr]^\top. \] By properties of matrix multiplication and of the transpose operation the last equality is equivalent to \[ \bigl(A\vec{v}\bigr)^\top \bigl[\overline{v_1} \ \ \overline{v_2} \ \ \cdots \ \ \overline{v_n} \bigr]^\top = \overline{\lambda} \bigl[v_1 \ \ v_2 \ \ \cdots \ \ v_n \bigr] \bigl[\overline{v_1} \ \ \overline{v_2} \ \ \cdots \ \ \overline{v_n} \bigr]^\top. \] Since $A \vec{v} = \lambda \vec{v}$, we further have \[ \lambda \, \vec{v}\, \bigl[\overline{v_1} \ \ \overline{v_2} \ \ \cdots \ \ \overline{v_n} \bigr]^\top = \overline{\lambda} \bigl[v_1 \ \ v_2 \ \ \cdots \ \ v_n \bigr] \bigl[\overline{v_1} \ \ \overline{v_2} \ \ \cdots \ \ \overline{v_n} \bigr]^\top, \] that is, \[ \tag{*} \lambda \, \bigl[v_1 \ \ v_2 \ \ \cdots \ \ v_n \bigr] \bigl[\overline{v_1} \ \ \overline{v_2} \ \ \cdots \ \ \overline{v_n} \bigr]^\top = \overline{\lambda} \bigl[v_1 \ \ v_2 \ \ \cdots \ \ v_n \bigr] \bigl[\overline{v_1} \ \ \overline{v_2} \ \ \cdots \ \ \overline{v_n} \bigr]^\top. \] Since $\vec{v} \neq \vec{0}$ we have \[ \bigl[v_1 \ \ v_2 \ \ \cdots \ \ v_n \bigr] \bigl[\overline{v_1} \ \ \overline{v_2} \ \ \cdots \ \ \overline{v_n} \bigr]^\top = \sum_{k=1}^n v_k\, \overline{v_k} = \sum_{k=1}^n |v_k|^2 \gt 0, \] and therefore equality (*) yields \[ \lambda = \overline{\lambda}. \] This proves that $\lambda$ is a real number.
Theorem. A symmetric $2\!\times\!2$ matrix is orthogonally diagonalizable.
Proof. Let $A = \begin{bmatrix} a & b \\ b & d \end{bmatrix}$ an arbitrary $2\!\times\!2$ be a symmetric matrix. We need to prove that there exists an orthogonal $2\!\times\!2$ matrix $U$ and a diagonal $2\!\times\!2$ matrix $D$ such that $A = UDU^\top.$ The eigenvalues of $A$ are \[ \lambda_1 = \frac{1}{2} \Bigl( a+b - \sqrt{(a-d)^2 + 4 b^2} \Bigr), \quad \lambda_2 = \frac{1}{2} \Bigl( a+b + \sqrt{(a-d)^2 + 4 b^2} \Bigr) \] If $\lambda_1 = \lambda_2$, then $(a-d)^2 + 4 b^2 = 0$, and consequently $b= 0$ and $a=d$; that is $A = \begin{bmatrix} a & 0 \\ 0 & a \end{bmatrix}$. Hence $A = UDU^\top$ holds with $U=I_2$ and $D = A$.
Now assume that $\lambda_1 \neq \lambda_2$. Let $\vec{u}_1$ be a unit eigenvector corresponding to $\lambda_1$ and let $\vec{u}_2$ be a unit eigenvector corresponding to $\lambda_2$. We proved that eigenvectors corresponding to distinct eigenvalues of a symmetric matrix are orthogonal. Since $A$ is symmetric, $\vec{u}_1$ and $\vec{u}_2$ are orthogonal, that is the matrix $U = \begin{bmatrix} \vec{u}_1 & \vec{u}_2 \end{bmatrix}$ is orthogonal. Since $\vec{u}_1$ and $\vec{u}_2$ are eigenvectors of $A$ we have \[ AU = U \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix} = UD. \] Therefore $A=UDU^\top.$ This proves that $A$ is orthogonally diagonalizable.
Theorem. For every positive integer $n$, a symmetric $n\!\times\!n$ matrix is orthogonally diagonalizable.
Proof. This statement can be proved by Mathematical Induction. The base case $n = 1$ is trivial. The case $n=2$ is proved above. To get a feel how mathematical induction proceeds we will prove the theorem for $n=3.$
Let $A$ be a $3\!\times\!3$ symmetric matrix. Then $A$ has an eigenvalue, which must be real. Denote this eigenvalue by $\lambda_1$ and let $\vec{u}_1$ be a corresponding unit eigenvector. Let $\vec{v}_1$ and $\vec{v}_2$ be unit vectors such that the vectors $\vec{u}_1,$ Let $\vec{v}_1$ and $\vec{v}_2$ form an orthonormal basis for $\mathbb R^3.$ Then the matrix $V_1 = \bigl[\vec{u}_1 \ \ \vec{v}_1\ \ \vec{v}_2\bigr]$ is an orthogonal matrix and we have \[ V_1^\top A V_1 = \begin{bmatrix} \vec{u}_1^\top A \vec{u}_1 & \vec{u}_1^\top A \vec{v}_1 & \vec{u}_1^\top A \vec{v}_2 \\[5pt] \vec{v}_1^\top A \vec{u}_1 & \vec{v}_1^\top A \vec{v}_1 & \vec{v}_1^\top A \vec{v}_2 \\[5pt] \vec{v}_2^\top A \vec{u}_1 & \vec{v}_2^\top A \vec{v}_1 & \vec{v}_2^\top A \vec{v}_2 \\\end{bmatrix}. \] Since $A = A^\top$, $A\vec{u}_1 = \lambda_1 \vec{u}_1$ and since $\vec{u}_1$ is orthogonal to both $\vec{v}_1$ and $\vec{v}_2$ we have \[ \vec{u}_1^\top A \vec{u}_1 = \lambda_1, \quad \vec{v}_j^\top A \vec{u}_1 = \lambda_1 \vec{v}_j^\top \vec{u}_1 = 0, \quad \vec{u}_1^\top A \vec{v}_j = \bigl(A \vec{u}_1\bigr)^\top \vec{v}_j = 0, \quad \quad j \in \{1,2\}, \] and \[ \vec{v}_2^\top A \vec{v}_1 = \bigl(\vec{v}_2^\top A \vec{v}_1\bigr)^\top = \vec{v}_1^\top A^\top \vec{v}_2 = \vec{v}_1^\top A \vec{v}_2. \] Hence, \[ \tag{**} V_1^\top A V_1 = \begin{bmatrix} \lambda_1 & 0 & 0 \\[5pt] 0 & \vec{v}_1^\top A \vec{v}_1 & \vec{v}_1^\top A \vec{v}_2 \\[5pt] 0 & \vec{v}_1^\top A \vec{v}_2 & \vec{v}_2^\top A \vec{v}_2 \\\end{bmatrix}. \] By the already proved theorem for $2\!\times\!2$ symmetric matrix there exists an orthogonal matrix $\begin{bmatrix} u_{11} & u_{12} \\[5pt] u_{21} & u_{22} \end{bmatrix}$ and a diagonal matrix $\begin{bmatrix} \lambda_2 & 0 \\[5pt] 0 & \lambda_3 \end{bmatrix}$ such that \[ \begin{bmatrix} \vec{v}_1^\top A \vec{v}_1 & \vec{v}_1^\top A \vec{v}_2 \\[5pt] \vec{v}_1^\top A \vec{v}_2 & \vec{v}_2^\top A \vec{v}_2 \end{bmatrix} = \begin{bmatrix} u_{11} & u_{12} \\[5pt] u_{21} & u_{22} \end{bmatrix} \begin{bmatrix} \lambda_2 & 0 \\[5pt] 0 & \lambda_3 \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} \\[5pt] u_{21} & u_{22} \end{bmatrix}^\top. \] Substituting this equality in (**) and using some matrix algebra we get \[ V_1^\top A V_1 = \begin{bmatrix} 1 & 0 & 0 \\[5pt] 0 & u_{11} & u_{12} \\[5pt] 0 & u_{21} & u_{22} \end{bmatrix} % \begin{bmatrix} \lambda_1 & 0 & 0 \\[5pt] 0 & \lambda_2 & 0 \\[5pt] 0 & 0 & \lambda_3 \end{bmatrix} % \begin{bmatrix} 1 & 0 & 0 \\[5pt] 0 & u_{11} & u_{12} \\[5pt] 0 & u_{21} & u_{22} \end{bmatrix}^\top \] Setting \[ U = V_1 \begin{bmatrix} 1 & 0 & 0 \\[5pt] 0 & u_{11} & u_{12} \\[5pt] 0 & u_{21} & u_{22} \end{bmatrix} \quad \text{and} \quad D = \begin{bmatrix} \lambda_1 & 0 & 0 \\[5pt] 0 & \lambda_2 & 0 \\[5pt] 0 & 0 & \lambda_3 \end{bmatrix} \] we have that $U$ is an orthogonal matrix, $D$ is a diagonal matrix and $A = UDU^\top.$ This proves that $A$ is orthogonally diagonalizable.
- Suggested problems for Section 6.6: 1, 2, 3, 4, 5, 6, 7, 8, 9, 14, 15, 16
- Matrices with orthonormal columns are important in what we are doing now. We often work with small matrices. It is also nice to work with matrices whose entries are one-digit integers, or fractions of such integers. It is not nice to work with entries are like $13/\sqrt{7}.$
-
So I got curious how many $3\!\times\!3$ matrices $Q$ have the following properties:
- The entries of $Q$ are in the set \[ \Bigl\{\ \frac{a}{b} \, \bigl| \bigr. \, a \in \{-9,-8,\ldots,-1,0,1,\ldots, 8, 9\}, \ b \in \{1,\ldots, 8, 9\} \Bigr\} \]
- $Q^{\top} Q = Q Q^{\top} = I_3$ (that is $Q$ has orthonormal columns and rows)
-
I wrote a Mathematica code that searched for all such matrices. There are a lot of them. However, I believe that all such matrices can be obtained from only eight matrices by using simple operations. I list these eight matrices in the next item. I have convinced myself that each desirable matrix described in the above item can be obtained from one of the eight matrices listed in the next item by application of the following operations:
- transpose
- a permutation of columns
- a permutation of rows
- multiplication of some rows by $-1$
- multiplication of some columns by $-1$
- These eight matrices are very special: \[ \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right], \quad \left[ \begin{array}{ccc} \frac{1}{3} & -\frac{2}{3} & \frac{2}{3} \\ -\frac{2}{3} & \frac{1}{3} & \frac{2}{3} \\ \frac{2}{3} & \frac{2}{3} & \frac{1}{3} \end{array} \right], \quad \left[ \begin{array}{ccc} -\frac{1}{3} & \frac{2}{3} & \frac{2}{3} \\ \frac{2}{3} & -\frac{1}{3} & \frac{2}{3} \\ \frac{2}{3} & \frac{2}{3} & -\frac{1}{3} \end{array} \right], \quad \left[ \begin{array}{ccc} \frac{2}{7} & \frac{3}{7} & \frac{6}{7} \\ \frac{3}{7} & -\frac{6}{7} & \frac{2}{7} \\ \frac{6}{7} & \frac{2}{7} & -\frac{3}{7} \end{array} \right], \] \[ \left[ \begin{array}{ccc} -\frac{2}{7} & \frac{6}{7} & \frac{3}{7} \\ \frac{3}{7} & -\frac{2}{7} & \frac{6}{7} \\ \frac{6}{7} & \frac{3}{7} & -\frac{2}{7} \end{array} \right], \quad \left[ \begin{array}{ccc} -\frac{8}{9} & \frac{1}{9} & \frac{4}{9} \\ \frac{1}{9} & -\frac{8}{9} & \frac{4}{9} \\ \frac{4}{9} & \frac{4}{9} & \frac{7}{9} \end{array} \right], \quad \left[ \begin{array}{ccc} -\frac{1}{9} & \frac{8}{9} & \frac{4}{9} \\ \frac{8}{9} & -\frac{1}{9} & \frac{4}{9} \\ \frac{4}{9} & \frac{4}{9} & -\frac{7}{9} \end{array} \right], \quad \left[ \begin{array}{ccc} \frac{1}{9} & \frac{8}{9} & \frac{4}{9} \\ \frac{4}{9} & -\frac{4}{9} & \frac{7}{9} \\ \frac{8}{9} & \frac{1}{9} & -\frac{4}{9} \end{array} \right]. \] Or, the same matrices written in a nicer way \[ \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right], \quad \frac{1}{3} \left[ \begin{array}{ccc} 1 & -2 & 2 \\ -2 & 1 & 2 \\ 2 & 2 & 1 \end{array} \right], \quad \frac{1}{3} \left[ \begin{array}{ccc} -1 & 2 & 2 \\ 2 & -1 & 2 \\ 2 & 2 & -1 \end{array} \right], \quad \frac{1}{7} \left[ \begin{array}{ccc} 2 & 3 & 6 \\ 3 & -6 & 2 \\ 6 & 2 & -3 \end{array} \right], \] \[ \frac{1}{7} \left[ \begin{array}{ccc} -2 & 6 & 3 \\ 3 & -2 & 6 \\ 6 & 3 & -2 \end{array} \right], \quad \frac{1}{9} \left[ \begin{array}{ccc} -8 & 1 & 4 \\ 1 & -8 & 4 \\ 4 & 4 & 7 \end{array} \right], \quad \frac{1}{9} \left[ \begin{array}{ccc} -1 & 8 & 4 \\ 8 & -1 & 4 \\ 4 & 4 & -7 \end{array} \right], \quad \frac{1}{9} \left[ \begin{array}{ccc} 1 & 8 & 4 \\ 4 & -4 & 7 \\ 8 & 1 & -4 \end{array} \right]. \]
-
In Math 204 a common task is to look for an inverse of a small matrix. Guided by a desire to keep things simple I looked for all $3\!\times\!3$ matrices with entries in the set $\{-1,0,1,2,3\}$ and whose inverses have entries in the set
\[
\{-9,-8,\ldots,-1,0,1,\ldots, 8, 9\}.
\]
Again, I wrote a Mathematica program to search for all such matrices. It turns out that there are a lot of such matrices, hundreds of thousand of them. I wrote additional Mathematica code to convert found matrices into LaTeX code which I used to produce
this pdf file with a large number of such matrices. This pdf file is large, 5MB, 3119 pages. If you ever need such a matrix I hope you find it here.
In fact, invertible matrices with integer entries whose inverses also have integer entries are called unimodular matrices. You can learn more about unimodular matrices by reading the Wikipedia page dedicated to unimodular matrices.
- Suggested problems for Section 6.5: 1, 3, 6, 7, 9, 13, 16, 17, 19, 20, 21, 22
-
Exercise 19 in Section 6.5 is very important. In fact, Exercise 19 in Section 6.5 is the following theorem:
Theorem. Let $A$ be an $n\!\times\!m$ matrix. Then $\operatorname{Nul}(A^\top\!\! A ) = \operatorname{Nul}(A)$.
Proof. The set equality $\operatorname{Nul}(A^\top\!\! A ) = \operatorname{Nul}(A)$ means \[ \vec{x} \in \operatorname{Nul}(A^\top\!\! A ) \quad \text{if and only if} \quad \vec{x} \in \operatorname{Nul}(A). \] So, we prove this equivalence. Assume that $\vec{x} \in \operatorname{Nul}(A)$. Then $A\vec{x} = \vec{0}$. Consequently, $A^\top\!A\vec{x} = A^\top\vec{0} = \vec{0}$. Hence, $A^\top\!A\vec{x}= \vec{0}$, and therefore $\vec{x} \in \operatorname{Nul}(A^\top\!\! A )$. This proves, \[ \vec{x} \in \operatorname{Nul}(A) \quad \Rightarrow \quad \vec{x} \in \operatorname{Nul}(A^\top\!\! A ). \] Now we prove the converse, \[ \tag{*} \vec{x} \in \operatorname{Nul}(A^\top\!\! A ) \quad \Rightarrow \quad \vec{x} \in \operatorname{Nul}(A). \] Assume, $\vec{x} \in \operatorname{Nul}(A^\top\!\! A )$. Then, $A^\top\!\!A \vec{x} = \vec{0}$. Multiplying the last equality by $\vec{x}^\top$ we get $\vec{x}^\top\! (A^\top\!\! A \vec{x}) = 0$. Using the associativity of the matrix multiplication we obtain $(\vec{x}^\top\!\! A^\top)A \vec{x} = 0$. Using the Linear Algebra with the transpose operation we get $(A \vec{x})^\top\!A \vec{x} = 0$. Now recall that for every vector $\vec{v}$ we have $\vec{v}^\top \vec{v} = \|\vec{v}\|^2$. Thus, we have proved that $\|A\vec{x}\|^2 = 0$. Now recall that the only vector whose norm is $0$ is the zero vector, to conclude that $A\vec{x} = \vec{0}$. This means $\vec{x} \in \operatorname{Nul}(A)$. This completes the proof of implication (*). The theorem is proved.
Corollary. Let $A$ be an $n\!\times\!m$ matrix. The columns of $A$ are linearly independent if and only if the $m\!\times\!m$ matrix $A^\top\!\! A$ is invertible.
Corollary. Let $A$ be an $n\!\times\!m$ matrix. Then $\operatorname{Col}(A^\top\!\! A ) = \operatorname{Col}(A^\top)$.
Corollary. Let $A$ be an $n\!\times\!m$ matrix. The matrices $A^\top$ and $A^\top\!\! A$ have the same rank.
- Suggested problems for Section 6.4: 2, 3, 5, 7, 9, 13, 15, 17, 19, 20
- The presentation of the $QR$ factorization in the textbook somewhat obscures the direct connection between the Gram-Schmidt orthogonalization algorithm and the $QR$ factorization. Below I will demostrate the connection.
- Let $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_m$ be linearly independent vectors in $\mathbb{R}^n$. The Gram-Schmidt orthogonalization algorithm produces the mutually orthogonal vectors \begin{align*} \mathbf{v}_1 & = \mathbf{x}_1 \\ \mathbf{v}_2 & = \mathbf{x}_2 - \frac{\mathbf{x}_2\cdot \mathbf{v}_1}{\mathbf{v}_1 \cdot \mathbf{v}_1} \mathbf{v}_1 \\ \mathbf{v}_3 & = \mathbf{x}_3 - \frac{\mathbf{x}_3\cdot \mathbf{v}_1}{\mathbf{v}_1 \cdot \mathbf{v}_1} \mathbf{v}_1 - \frac{\mathbf{x}_3\cdot \mathbf{v}_2}{\mathbf{v}_2 \cdot \mathbf{v}_2} \mathbf{v}_2 \\ & \ \ \vdots \\ \mathbf{v}_m & = \mathbf{x}_m - \frac{\mathbf{x}_m\cdot \mathbf{v}_1}{\mathbf{v}_1 \cdot \mathbf{v}_1} \mathbf{v}_1 - \cdots - \frac{\mathbf{x}_m\cdot \mathbf{v}_{m-1}}{\mathbf{v}_{m-1} \cdot \mathbf{v}_{m-1}} \mathbf{v}_{m-1} \\ \end{align*} We can rewrite the above vector equations as \begin{align*} \mathbf{x}_1 & = \mathbf{v}_1 \\ \mathbf{x}_2 & = \frac{\mathbf{x}_2\cdot \mathbf{v}_{1}}{\mathbf{v}_{1} \cdot \mathbf{v}_{1}} \mathbf{v}_1 + \mathbf{v}_2 \\ \mathbf{x}_3 & = \frac{\mathbf{x}_3\cdot \mathbf{v}_{1}}{\mathbf{v}_{1} \cdot \mathbf{v}_{1}} \mathbf{v}_1 + \frac{\mathbf{x}_3\cdot \mathbf{v}_{2}}{\mathbf{v}_{2} \cdot \mathbf{v}_{2}} \mathbf{v}_2 + \mathbf{v}_3 \\ & \ \ \vdots \\ \mathbf{x}_m & = \frac{\mathbf{x}_m\cdot \mathbf{v}_{1}}{\mathbf{v}_{1} \cdot \mathbf{v}_{1}} \mathbf{v}_1 + \cdots + \frac{\mathbf{x}_m\cdot \mathbf{v}_{m-1}}{\mathbf{v}_{m-1} \cdot \mathbf{v}_{m-1}} \mathbf{v}_{m-1} + \mathbf{v}_m \\ \end{align*} Now set \[ \mathbf{u}_k = \frac{1}{\|\mathbf{v}_k\|} \mathbf{v}_k \quad \text{for} \quad k \in \{1,\ldots,m\} \] and use the fact that $\mathbf{v}_k \cdot \mathbf{v}_k = \|\mathbf{v}_k\|^2$ to rewrite the vectors $\mathbf{x}_1,\dots, \mathbf{x}_m$ in terms of the orthonormal vectors $\mathbf{u}_1,\ldots,\mathbf{u}_m$: \begin{align*} \mathbf{x}_1 & = \|\mathbf{v}_1\| \mathbf{u}_1 \\ \mathbf{x}_2 & = \frac{\mathbf{x}_2\cdot \mathbf{v}_{1}}{\|\mathbf{v}_1\|} \mathbf{u}_1 + \|\mathbf{v}_2\| \mathbf{u}_2 \\ \mathbf{x}_3 & = \frac{\mathbf{x}_3\cdot \mathbf{v}_{1}}{\|\mathbf{v}_1\|} \mathbf{u}_1 + \frac{\mathbf{x}_3\cdot \mathbf{v}_{2}}{\|\mathbf{v}_2\|} \mathbf{u}_2 + \|\mathbf{v}_3\| \mathbf{u}_3 \\ & \ \ \vdots \\ \mathbf{x}_m & = \frac{\mathbf{x}_m\cdot \mathbf{v}_{1}}{\|\mathbf{v}_1\|} \mathbf{u}_1 + \cdots + \frac{\mathbf{x}_m\cdot \mathbf{v}_{m-1}}{\|\mathbf{v}_{m-1}\|} \mathbf{u}_{m-1} + \|\mathbf{v}_m\| \mathbf{u}_m \end{align*} Now set \[ \alpha_{jk} = \frac{\mathbf{x}_k\cdot \mathbf{v}_{j}}{\|\mathbf{v}_j\|} = \mathbf{x}_k\cdot \mathbf{u}_{j} \quad \text{for} \quad j \in \{1,\ldots,k-1\}, \ \ k \in \{2,\ldots,m\} \] and the above equations can be rewritten as \begin{align*} \mathbf{x}_1 & = \|\mathbf{v}_1\| \mathbf{u}_1 \\ \mathbf{x}_2 & = \alpha_{1,2} \mathbf{u}_1 + \|\mathbf{v}_2\| \mathbf{u}_2 \\ \mathbf{x}_3 & = \alpha_{1,3} \mathbf{u}_1 + \alpha_{2,3} \mathbf{u}_2 + \|\mathbf{v}_3\| \mathbf{u}_3 \\ & \ \ \vdots \\ \mathbf{x}_m & = \alpha_{1,m} \mathbf{u}_1 + \cdots + \alpha_{m-1,m} \mathbf{u}_{m-1} + \|\mathbf{v}_m\| \mathbf{u}_m \\ \end{align*} These vector equations can be written in matrix form as \[ \left[\begin{array}{ccccc} \mathbf{x}_1 & \mathbf{x}_2 & \mathbf{x}_3 & \cdots & \mathbf{x}_m \end{array} \right] = \left[\begin{array}{ccccc} \mathbf{u}_1 & \mathbf{u}_2 & \mathbf{u}_3 & \cdots & \mathbf{u}_m \end{array} \right] \left[\begin{array}{ccccc} \|\mathbf{v}_1\| & \alpha_{1,2} & \alpha_{1,3} & \cdots & \alpha_{1,m} \\ 0 & \|\mathbf{v}_2\| & \alpha_{2,3} & \cdots & \alpha_{2,m} \\ 0 & 0 & \|\mathbf{v}_3\| & \cdots & \alpha_{3,m} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \|\mathbf{v}_m\| \\ \end{array} \right] \] The above matrix equation is the $QR$ factorization \[ A = QR \] with \begin{align*} A & = \left[\begin{array}{ccccc} \mathbf{x}_1 & \mathbf{x}_2 & \mathbf{x}_3 & \cdots & \mathbf{x}_m \end{array} \right] \\ Q & = \left[\begin{array}{ccccc} \mathbf{u}_1 & \mathbf{u}_2 & \mathbf{u}_3 & \cdots & \mathbf{u}_m \end{array} \right] \end{align*} and the matrix $R$ is an upper triangular matrix with positive terms on the diagonal. Since the vectors $\mathbf{u}_1, \mathbf{u}_2,\ldots, \mathbf{u}_m$ are orthonormal, we have $Q^{\top} Q = I_m$. Therefore the $m\!\times\!m$ matrix $R$ can be calculated as $R = Q^{\top}A$.
- $QR$ factorization of a matrix $A$ with linearly independent columns is unique. Here is a proof.
In the next proof I am experimenting with a new way of presenting a theorem and its proof. Each theorem consists of assumptions and a claim. In the theorem below I label the assumptions by green labels with two capital letters. In this theorem they are BA, AQ, AR and QR. These are short abbreviations of the content of the assumptions. Here they are, respecitively, Basic Assumptions, Assumtions about $Q$, Assumtions about $R$, $QR$ factorizations are assumed. I label the claim of the theorem by two or three capital letters in red. Here it is QRU (standing for $QR$ is Unique). The logic for selecting green and red is that the assumtions are a pleasant part of a theorem and the claim is an unpleasant part since we have to strugle intellectually to prove the claim. Although this intellectual challenge should be a pleasant task, there is a certain level of uncertainty associated associated with it.
A vital part of each proof are facts that we know from previously proved theorems. These facts give a proof its flow. Here I list all such facts and label them with green labels since they are known and useful for our task at hand. Here they are UP (Upper trianglular Product), UI (Upper trianglular Inverse).
I introduced a blue label for a comment. Here UTP introduces a notation for Upper Triangular matrices with Positive terms on diagaonal.
What is a proof?
A proof is a procedure which uses previously stated (assumed or known) green labeled facts and logic to produce new green labeled facts. The goal of a proof is to produce a sequence of green labeled facts that will terminate with the (red labeled) claim of the theorem. In terms of the colors, the goal of a proof is to greenify the red claim of a theorem.Theorem
Assumptions
- BA. $A$ is an $n\!\times\!m$ real matrix with linearly independent columns.
- AQ. Assume $Q_1, Q_2$ are $n\!\times\!m$ real matrices such that \[ Q_1^{\top} Q_1 = I_m \quad \text{and} \quad Q_2^{\top} Q_2 = I_m \]
- AR. Assume $R_1, R_2$ are $m\!\times\!m$ real upper triangular matrices with positive entries on the diagonals.
- QR. Assume $A = Q_1 R_1$ and $A = Q_2 R_2$
- QRU. Then $Q_1 = Q_2$ and $R_1 = R_2$.
In the proof ot the theorem we use the following facts that have been established elsewhere.- UP. The product of two upper triangular matrices with positive entries on the diagonals is an upper triangular matrix with positive entries on the diagonal.
- UI. The inverse of an upper triangular matrix with positive entries on the diagonal is an upper triangular matrix with positive entries on the diagonal.
- UTP. UP and UI show that the set of upper triangular matrices with positive entries on the diagonals forms a multiplicative group. Basically it behaves as the set of positive real numbers with respect to multiplication. We will use the abbreviation a "UTP matrix" for an "upper triangular matrix with positive entries on the diagonal."
The proof starts here.- NR. By UI and AR the matrix $R_2$ is invertible and $R_2^{-1}$ is a UTP matrix. By UP the matrix $R= R_1 R_2^{-1}$ is a UTP matrix. In particular, $R$ is invertible.
- RQ1. By QR and NR we have \[ \tag{RQ} Q_1 R_1 R_2^{-1} = Q_1 R = Q_2. \] Multiplying (RQ) from the left by $Q_1^{\top}$ and using AQ we get \[ R = Q_1^{\top} Q_2. \]
- RQ2. Multiplying (RQ) from the left by $Q_2^{\top}$ and using AQ we get \[ Q_2^{\top} Q_1 R = I_m. \] Thus, \[ R^{-1} = Q_2^{\top} Q_1. \]
- RI. Notice that from RQ1 and RQ2 we have \[ R^{\top} = \bigl( Q_1^{\top} Q_2 \bigr)^{\top} = Q_2^{\top} Q_1 = R^{-1}. \] The equlity $R^{\top} = R^{-1}$ is vital to this proof: by the definition of the transpose and AR $R^T$ is a lover triangular matrix with the same positive diagonal entries as $R,$ while, by NR and UI, $R^{-1}$ is an upper triangular matrix with the diagonal entries which are reciprocals of the diagonal entries of $R.$ Consequently, $R^{\top} = R^{-1}$ yields that $R^{\top} = R^{-1}$ is a diagonal matrix whose entries on the diagonal are positive real numbers which equal their reciprocals. Since the only positive real number which equals its reciprocal is the number $1$, we conclude that all the diagonal entries of $R^{\top} = R^{-1}$ are $1$. Thus \[ R = I_m. \] QRU. By RI and NR \[ R_1R_2^{-1} = R = I_m. \] Thus $R_1 = R_2$. By equation (RQ) in RQ1 and RI we get \[ Q_1 = Q_2. \]
- QED. Since the red QRU has been turn into green QRU the proof has been completed.
- Find $QR$ factorizations of the following matrices \[ \left[ \begin{array}{ccc} -1 & -1 & 3 \\ 1 & 5 & -1 \\ 1 & 1 & 3 \\ -1 & -5 & 7 \end{array} \right] \quad \left[ \begin{array}{ccc} 6 & 8 & 7 \\ 3 & 6 & 0 \\ 2 & 2 & 0 \end{array} \right] \quad \left[ \begin{array}{ccc} 2 & 2 & 1 \\ 1 & 2 & 8 \\ 2 & 3 & 1 \end{array} \right] \quad \left[ \begin{array}{ccc} 4 & -1 & -7 \\ 2 & 8 & 7 \\ 2 & 4 & -8 \\ 1 & 5 & 5 \end{array} \right] \] \[ \left[ \begin{array}{ccc} 2 & -6 & 4 \\ -5 & 9 & 1 \\ 4 & 4 & 9 \\ 2 & -4 & 5 \end{array} \right] \]
- Suggested problems for Section 6.2: 2, 3, 5, 8, 9, 11, 13, 15, 17, 19, 21, 23, 25, 26, 27, 29. In the terminology of Section 6.2 the matrix $A$ posted on February 8, 2019 is an orthogonal matrix.
- Suggested problems for Section 6.3: 1, 2, 4, 5, 7, 10, 11, 13, 15, 16 17, 19, 20, 21, 23
-
In this image the light blue polygon represents subspace $\mathcal W$, the maroon vector and dark green vector are vectors in $\mathcal W$, the navy blue vector is a vector outside of the subspace $\mathcal W.$
- To understand the importance of the dot product one needs to review Law of cosines. Here is a short page that i wrote about the Law of cosines. Wikipedia offers six different proofs at its Law of cosines page. Find one proof that resonates best with you.
- We also did a vector form of the Pythagorean theorem. This is a good occasion to review the classical Pythagorean_theorem. Again Wikipedia offers several different proofs. I selected the following proof by rearrangement and made it into a "clickable'' proof.
- I want to emphasize the following exercises 24, 25, 26, 27, 28, 29, 31 from Section 6.1 posted on Friday. Also do Exercise 32. It is not a computer exercise. It can be done by hand; see the next item.
- Also do Exercise 32 in Section 6.1. It might be easier to write the matrix $A$ as \[ A = \frac{1}{2} \, \left[ \begin{array}{rrrr} 1 & 1 & 1 & 1 \\[6pt] 1 & 1 & -1 & -1 \\[6pt] 1 & -1 & 1 & -1 \\[6pt] 1 & -1 & -1 & 1 \end{array}\right] \] Solve part a. by hand. Look at the matrix $A^{\top}$. Do you notice anything special how this matrix relates to $A$? State your conclusion clearly. Next calculate the products $A^{\top}A$ and $A\,A^{\top}$. Now calculate the length of $A\mathbf u$ using the formula $\bigl(A\mathbf u\bigr)^{\top} \bigl(A\mathbf u\bigr)$ and using the rules for the transpose operation and the formulas that you obtained for $A^{\top}A$. Similarly calculate $\bigl(A\mathbf u\bigr)^{\top} \bigl(A\mathbf v\bigr)$. In the last formulas you should work with general vectors $\mathbf u$ and $\mathbf v$ in $\mathbb R^4$, not any specific vectors as they suggest in the book.
- We did Section 6.1 today. Suggested problems: 1, 5, 7, 8, 9-12, 13, 15-18, 20, 22, 24, 25, 26, 27, 28, 29, 30, 31
- Here is a proof of the Law of Cosines and its connection to dot product.
- I wrote a draft of a list of topics for Exam 1.
- Today we did Appendix B Complex Numbers and we started Section 5.5. Suggested problems for Section 5.5: 1-6, 7-12, 13, 16, 17, 18, 21, 25, 26.
- I handed out the first assignment yesterday. The assignment is due Thursday, February 7, 2019.
-
Some interesting linear transformations of the vector space $\mathbb P_n = \mathbb R[t]_{\leq n}$ of polynomials of degree $\leq n$, where $n$ is a positive integer. In these examples we always calculate the matrix of a linear transformation with respect to the basis of this space which consists of monomials:
\[
\mathcal M = \{1, t, t^2, \cdots, t^n\}.
\]
Sometimes it is convenient to introduce notation for monomials: We set $\phi_k(t) = t^k$ for a nonnegative integer $k.$
- Let $D: \mathbb P_n \to \mathbb P_n$ be the linear transformation of taking the derivative with respect to $t$. That is, for every $p(t) \in \mathbb P_n$ we set $(Dp)(t) = p'(t).$ Then the matrix representation of $D$ relative to $\mathcal M$ is the following $(n+1)\times(n+1)$ matrix \[ \left[\! \begin{array}{cccc} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & n \\ 0 & 0 & 0 & \cdots & 0 \\ \end{array}\!\right]. \] To be specific, denote by $a_{ij}$ the entry in the $i$-th row and $j$-th column of the above matrix. Then the only nonzero entries are $a_{j,j+1} = j$ with $j\in\{1,\ldots,n\}.$
- Let $R: \mathbb P_n \to \mathbb P_n$ be the linear transformation defined for every $p(t) \in \mathbb P_n$ by \[ (Rp)(t) = t^n p(1/t). \] Then the matrix representation of $R$ relative to $\mathcal M$ is the following $(n+1)\times(n+1)$ matrix \[ Z_{n+1} = \left[\! \begin{array}{ccccc} 0 & 0 & 0 & \cdots & 0 & 1 \\ 0 & 0 & 0 & \cdots & 1 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ 1 & 0 & 0 & \cdots & 0 & 0 \\ \end{array}\!\right]. \] To be specific, denote by $a_{ij}$ the entry in the $i$-th row and $j$-th column of the above matrix. Then the only nonzero entries are $a_{j,n+2-j} = j$ with $j\in\{1,\ldots,n,n+1\}.$ This matrix is called reverse identity matrix or anti-identity matrix.
-
Let $T: \mathbb P_n \to \mathbb P_n$ be the linear transformation defined for every $p(t) \in \mathbb P_n$ by
\[
(Tp)(t) = (1-t^2)p''(t) - tp'(t).
\]
Then the matrix representation of $T$ relative to $\mathcal M$ is the following $(n+1)\times(n+1)$ matrix
\[
\left[
\begin{array}{rrrrrcrrrr}
0 & 0 & 2 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 & 0\\
0 & -1 & 0 & 6 & 0 & 0 & \cdots & 0 & 0 & 0 & 0 \\
0 & 0 & -4 & 0 & 12 & 0 & \cdots & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & -9 & 0 & 20 & \cdots & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & -16 & 0 & \cdots & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & -25 & \cdots & 0 & 0 & 0 & 0 \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \\
0 & 0 & 0 & 0 & 0 & 0 & \cdots & -\alpha & 0 & \gamma & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & \cdots & 0 & -\beta & 0 & \zeta \\
0 & 0 & 0 & 0 & 0 & 0 & \cdots & 0 & 0 & -\delta & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 & -\eta \\
\end{array}
\right] \qquad \text{where} \quad \begin{array}{l}
\alpha = (n-3)^2 \\
\beta = (n-2)^2 \\
\gamma = (n-2)(n-1) \\
\delta = (n-1)^2 \\
\zeta = (n-1)n \\
\eta = n^2 \\
\end{array}
\]
To be specific, denote by $a_{ij}$ the entry in the $i$-th row and $j$-th column of the above matrix. Then the only nonzero entries are $a_{k,k} = - (k-1)^2$ with $k\in\{1,\ldots,n,n+1\}$ and $a_{k,k+2} = k(k+1)$ with $k\in\{1,\ldots,n-1\}$
The linear transformation introduced here is related to the Chebyshev differential equation and Chebyshev polynomials of the first kind, see my web-page about this topic using linear algebra.
- Today we started Section 5.4. Suggested problems are: 1, 3 - 13, 17, 19 - 23, 27, 28.
-
Today we discussed the Fundamental Theorem of Algebra. It is important in this course and it is not clear whether you will see it in other courses. This is somewhat colloquial statement of the therem from the
Wikipedia page devoted to the theorem: Every non-zero, single-variable, degree $n$ polynomial with complex coefficients has, counted with multiplicity, exactly $n$ complex roots. Below I give a formal statement of the theorem
- $n$ is a positive integer,
- $a_0, a_1, \ldots, a_n$ are complex numbers,
- $p(x) = a_0 + a_1 x + \cdots + a_n x^n,$
- $a_n \neq 0$
- a positive integer $k$,
- positive integers $m_1, \ldots, m_k$,
- distinct complex numbers $w_1, \ldots, w_k$,
- $n$ is called the degree of the polynomial $p(x)$, since $a_n \neq 0$;
- the complex numbers $w_1, \ldots, w_k$ are called the roots of the polynomial $p(x)$ since $p(w_1) = \cdots = p(w_k) = 0$;
- for each $j \in \{1,\ldots,k\}$ the positive integer $m_j$ is called the multiplicity of the root $w_j$;
- the positive integer $k$ is called the number of distinct roots of $p(x).$
- The Fundamental Theorem of Algebra is proved in Math 430: Complex Analysis. However, there are easier proofs. See for example this proof from a linear algebra course at UC Davis. I wrote this proof for another linear algebra class.
-
It might be a good idea to give a definition of a polynomial.
A polynomial in a single variable $x$ is an algebraic expression of the form
\[
a_{0} + a_{1}x+ a_{2}x^{2}+ \cdots + a_{n-1}x^{n-1}+ a_{n}x^{n}
\]
where $n$ is a nonnegative integer, $a_{0}, a_{1},\ldots ,a_{n-1}, a_{n}$ are constant complex numbers and $x$ is the variable. Here "variable" means that $x$ represents no particular value, although any value may be substituted for it. We often introduce abbreviated notation for polynomials, for example
\[
p(x) = a_{0} + a_{1}x + a_{2}x^{2} + \cdots + a_{n-1}x^{n-1}+ a_{n}x^{n}.
\]
- Special polynomials $1 = x^0$, $x = x^1$, $x^2$, $\ldots$, $x^n$, $\ldots$ are called monomials. Here $n$ is a nonnegative integer. The exponent in a monomial is called the degree of a monomial.
- Using linear algebra terminology, a polynomial is simply a linear combination of monomials.
- The complex numbers $a_{0}, a_{1},\ldots , a_{n-1}, a_{n}$ are said to be the coefficients of the polynomial $p(x).$ More precisely, with a nonnegative integer $k$, the coefficient multiplying the monomial $x^k$ is called the $k$-th coefficient of a polynomial. A monomial multiplied by its coefficient is said to be a term of a polynomial. It is customary not to write polynomial terms with zero coefficients.
- Example: $p(x) = 0 + e x +0 x^2 - \pi x^3 + 0 x^4 = e x - \pi x^3.$ The terms of this polynomial are $0 x^0$, $e x^1$, $0 x^2$, $\pi x^3$. There is no point in listing more terms, since they all have zero coefficinets. The degree of this polynomial is $3.$
- The polynomial whose all coefficients are zero is called the zero polynomial.
- The degree of a nonzero polynomial is the highest degree of its monomials with nonzero coefficients. It is customary define the degree of the zero polynomial to be $-\infty.$
- Polynomials with small degrees have special names. The zero polynomial and the polynomials of degree $0$ are called constant polynomials. The zero polynomial and the polynomials of degree $0$ and $1$ are called linear polynomials. The polynomials of degree $2$ are called quadratic polynomials. The polynomials of degree $3$ are called cubic polynomials. The polynomials of degree $4$ are called quartic polynomials. The polynomials of degree $5$ are called quintic polynomials.
-
The following statement is a consequence of the Fundamental Theorem of Algebra.
-
If $A$ is an $n\times n$ matrix and
\[
p(\lambda) = \det(A-\lambda I),
\]
that is $p(\lambda)$ is the characteristic polynomial of $A$, then $p(\lambda)$ is a polynomial of degree $n$. (In fact the coefficient with $\lambda^n$ is $(-1)^n$.) Thus, the Fundamental Theorem of Algebra applies to the characteristic polynomial. The significance of the numbers from the Fundamental Theorem of Algebra for the matrix $A$ is as follows:
- The complex numbers $w_1, \ldots, w_k$ are the all the distinct eigenvalues of $A$; the set of all eigenvalues of $A$, that is the set \[ \{w_1, \ldots, w_k\} \] is called the spectrum of $A.$
- The positive integer $k$ is called the number of distinct eigenvalues of $A.$
- For each $j \in \{1,\ldots,k\}$ the positive integer $m_j$ is called the algebraic multiplicity of the eigenvalue $w_j.$
- Since $m_1+\cdots+m_k = n$ the algebraic multiplicities of the distinct eigenvalues of $A$ add up to the size of the matrix $A.$
- For each $j \in \{1,\ldots,k\}$ the dimension of the eigenspace of $A$ corresponding to $w_j$ is $\leq m_j$, that is \[ \dim \bigl(\operatorname{nul}(A-w_j I)\bigr) \leq m_j. \]
- I illustrated these concepts with the matrix \[ \left[ \begin{array}{rrrr} 0 & 0 & -1 & -1 \\ -1 & 0 & 0 & 0 \\ 2 & 1 & 2 & 1 \\ -2 & -1 & -1 & 0 \end{array} \right] \] You can also try \[ \left[ \begin{array}{rrrr} -1 & 2 & 0 & 2 \\ 0 & -1 & 0 & 0 \\ 2 & -6 & 1 & -2 \\ 0 & 2 & 0 & 1 \end{array} \right] \]
- Notice that I have updated the post of January 14.
- Today we reviewed Section 5.2. Suggested problems are 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.
- Today we proved a theorem which gives a sufficient condition for linear independence of eigenvectors of a linear transformaion. Simply stated in English it reads: Eigenvectors corresponding to distinct eigenvalues are linearly independent. This is Theorem 2 in Section 5.1. The proof that I presented here is different from the proof in the textbook.
- We proceeded by discussing diagonalization as in Section 5.3. Suggested problems for Section 5.3 are 2, 3, 5, 8, 9, 12, 13, 16, 18, 20, 23, 24.
- Today we reviewed 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.
- 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.
|
|
|
|
|
|
|
|
- The last few days we discussed change of coordinates in the context of vector spaces $\mathbb R^n$ with $n$ being a positive integer.
-
Today we discussed Problem 17 in Section 4.7 which is based on Problem 38 in Section 4.3 and Problem 34 in Section 4.5. In these problems you are asked to consider the following trigonometric functions
\begin{alignat*}{2}
\mathbf x_0 &= 1, & \qquad \mathbf y_0 &= 1, \\
\mathbf x_1 &= \cos t, & \qquad \mathbf y_1 &= \cos t, \\
\mathbf x_2 &= (\cos t)^2, & \qquad \mathbf y_2 &= \cos(2t), \\
\mathbf x_3 &= (\cos t)^3, & \qquad \mathbf y_3 &= \cos(3t), \\
\mathbf x_4 &= (\cos t)^4, & \qquad \mathbf y_4 &= \cos(4t), \\
\mathbf x_5 &= (\cos t)^5, & \qquad \mathbf y_5 &= \cos(5t), \\
\mathbf x_6 &= (\cos t)^6, & \qquad \mathbf y_6 &= \cos(6t). \\
\end{alignat*}
Thus, the functions $\mathbf x_0,\ldots,\mathbf x_6,$ are powers of the cosine function and the functions $\mathbf y_0,\ldots,\mathbf y_6,$ are multiple angle cosine functions. In fact, there is no particular reason to limit our considerations to these seven functions. We could consider any positive integer $n$, and consider
\begin{alignat*}{2}
\mathbf x_k &= (\cos t)^k, & \qquad \mathbf y_k &= \cos(kt), \\
\end{alignat*}
for all $k \in \{0,1,\ldots,n\}.$
-
The first remarkable fact about these functions is that for an arbitrary positive integer $n$ we have
\[
\mathbf y_n \in \operatorname{span} \bigl\{ \mathbf x_0, \mathbf x_1,\ldots,\mathbf x_n \bigr\}.
\]
To prove this claim we need trigonometric identities presented in the textbook in Problem 34 in Section 4.5. I will prove those identities here. The proof is based on the addition formulas for the cosine function. The method I present here is called Chebyshev method. Let $n$ be a positive integer greater than $1.$ Then we have
\begin{align*}
\cos(nt) = \cos\bigl((n-1)t + t \bigr) & = \cos\bigl((n-1)t \bigr) \cos t - \sin\bigl((n-1)t \bigr) \sin t \\
\cos\bigl((n-2)t \bigr) = \cos\bigl((n-1)t - t \bigr) & = \cos\bigl((n-1)t \bigr) \cos t + \sin\bigl((n-1)t \bigr) \sin t \\
\end{align*}
Adding the last two identities yields
\[
\cos(nt) + \cos\bigl((n-2)t \bigr) = 2 \cos\bigl((n-1)t \bigr) \cos t
\]
and, more importantly, we have
\begin{equation*} \tag{rr}
\cos(nt) = 2 \cos\bigl((n-1)t \bigr) \cos t - \cos\bigl((n-2)t \bigr).
\end{equation*}
This formula gives $\cos(nt)$ in terms of two previous multiple angle cosines $\cos\bigl((n-1)t \bigr)$ and $\cos\bigl((n-2)t \bigr).$ Such a formula is called a recursion or a recurrence relation. For $n=2$ we have \[
\cos(2t) = 2 \cos(1t) \cos t - \cos(0t) = 2(\cos t)^2 - 1.
\]
Or, in our notation
\[
\mathbf y_2 = - \mathbf x_0 + 2 \mathbf x_2.
\]
That is $\mathbf y_2 \in \operatorname{span} \bigl\{\mathbf x_0, \mathbf x_2\bigr\}.$ Next we apply the recursion (rr) to $n=3$ and we get (using already established formula for $\cos(2t)$)
\[
\cos(3t) = 2 \cos(2t) \cos t - \cos t = 2\bigl( 2(\cos t)^2 - 1 \bigr) \cos t - \cos t = 4 (\cos t)^3 - 3 \cos t.
\]
That is
\[
\mathbf y_3 = - 3 \mathbf x_1 + 4 \mathbf x_3,
\]
implying that $\mathbf y_3 \in \operatorname{span} \bigl\{\mathbf x_1, \mathbf x_3\bigr\}.$ Continuing to $n=4$ we get
\begin{align*}
\cos(4t) & = 2 \cos(3t) \cos t - \cos(2t) \\
& = 2 \bigl( 4 (\cos t)^3 - 3 \cos t \bigr) \cos t - \bigl(2(\cos t)^2 - 1 \bigr) \\
& = 8 (\cos t)^4 - 8 (\cos t)^2 + 1.
\end{align*}
That is
\[
\mathbf y_4 = \mathbf x_0 - 8 \mathbf x_2 + 8 \mathbf x_4,
\]
implying that $\mathbf y_4 \in \operatorname{span} \bigl\{\mathbf x_0, \mathbf x_2, \mathbf x_4 \bigr\}.$ Continuing to $n=5$ we get
\begin{align*}
\cos(5t) & = 2 \cos(4t) \cos t - \cos(3t) \\
& = 2 \bigl( 8 (\cos t)^4 - 8 (\cos t)^2 + 1 \bigr) \cos t - \bigl( 4 (\cos t)^3 - 3 \cos t \bigr) \\
& = 16 (\cos t)^5 - 20 (\cos t)^3 + 5 \cos t.
\end{align*}
That is
\[
\mathbf y_5 = 5 \mathbf x_1 - 20 \mathbf x_3 + 16 \mathbf x_5,
\]
implying that $\mathbf y_5 \in \operatorname{span} \bigl\{\mathbf x_1, \mathbf x_3, \mathbf x_5 \bigr\}.$ Continuing to $n=6$ we get
\begin{align*}
\cos(6t) & = 2 \cos(5t) \cos t - \cos(4t) \\
& = 2 \bigl( 16 (\cos t)^5 - 20 (\cos t)^3 + 5 \cos t \bigr) \cos t - \bigl( 8 (\cos t)^4 - 8 (\cos t)^2 + 1 \bigr) \\
& = 32 (\cos t)^6 - 48 (\cos t)^4 + 18 (\cos t)^2 - 1.
\end{align*}
That is
\[
\mathbf y_6 = - \mathbf x_0 + 18 \mathbf x_2 - 48 \mathbf x_4 + 32 \mathbf x_6,
\]
implying that $\mathbf y_6 \in \operatorname{span} \bigl\{\mathbf x_0, \mathbf x_2, \mathbf x_4, \mathbf x_6 \bigr\}.$
In general, for a positive integer $n$ we have \begin{equation*} \cos(n t) = 2^{n-1} n \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{(-1)^k}{4^k (n-k)} \binom{n-k}{k} (\cos t)^{n-2k}, \end{equation*} Here $\lfloor \cdot \rfloor$ denotes the floor function and $\displaystyle \binom{m}{k}$ denotes a binomial coefficient, that is \[ \binom{m}{k} = \frac{m!}{k! (m-k)!}. \] The above formula for $\cos(nt)$ I derived from Viète's formulas for sine and cosine of multiple angles. I think that Viète's formulas are not difficult to prove by Mathematical induction.
For an even $n = 2m$ a slight manipulation of the above formula for $\cos(nt)$ expressed in terms of the functions $\mathbf x_k$ gives \begin{equation*} \mathbf y_{2m} = (-1)^{m} m \sum_{k=0}^{m} \frac{(-4)^k}{m+k} \binom{m+k}{m-k} \mathbf x_{2k}. \end{equation*} Thus $\mathbf y_{2m} \in \operatorname{span} \bigl\{\mathbf x_0, \mathbf x_2, \cdots, \mathbf x_{2m}\bigr\}.$ Similarly for an odd $n=2m+1$ we have \begin{equation*} \mathbf y_{2m+1} = (-1)^{m} (2m+1) \sum_{k=0}^{m} \frac{(-4)^k}{m+1+k} \binom{m+1+k}{m-k} \mathbf x_{2k+1}. \end{equation*} Thus $\mathbf y_{2m+1} \in \operatorname{span} \bigl\{\mathbf x_1, \mathbf x_3, \ldots, \mathbf x_{2m+1}\bigr\}.$ -
Another remarkable fact about the functions $\mathbf x_0, \mathbf x_1, \ldots, \mathbf x_{n}$ is that they are linearly independent. You are asked to prove this with $n=6$ in Problem 38 in Section 4.3.
Here is a proof.
We will prove that the only linear combination of the funcions $\mathbf x_0, \mathbf x_1, \mathbf x_2, \mathbf x_3,\mathbf x_4, \mathbf x_5, \mathbf x_{6}$ which results in the zero function is the trivial linear combination. Assume that $\alpha_0, \alpha_1, \ldots, \alpha_6 \in \mathbb R$ are such that \begin{equation*} \alpha_0 \mathbf x_0 + \alpha_1 \mathbf x_1+\alpha_2 \mathbf x_2 + \alpha_3 \mathbf x_3+\alpha_4\mathbf x_4+\alpha_5 \mathbf x_5+\alpha_6 \mathbf x_{6} = \mathbf 0. \end{equation*} The preceding equality means that for all $t \in \mathbb R$ we have \begin{equation*} \alpha_0 + \alpha_1 (\cos t) +\alpha_2 (\cos t)^2 + \alpha_3 (\cos t)^3 +\alpha_4 (\cos t)^4 +\alpha_5 (\cos t)^5+\alpha_6 (\cos t)^6 = 0. \end{equation*} Now we introduce the substitution $s = \cos t.$ Since the range of $\cos t$ is the interval $[-1,1]$, the preceding equality means that for all $s \in [-1,1]$ we have \begin{equation*} \alpha_0 + \alpha_1 s +\alpha_2 s^2 + \alpha_3 s^3 +\alpha_4 s^4 +\alpha_5 s^5+\alpha_6 s^6 = 0. \end{equation*} Differentiating both sides of the preceding equality sith respect to $s$ yields that for all $s \in (-1,1)$ we have \begin{align*} \alpha_1 + 2 \alpha_2 s + 3 \alpha_3 s^2 + 4 \alpha_4 s^3 + 5 \alpha_5 s^4 + 6 \alpha_6 s^5 & = 0 \\ 2 \alpha_2 + 6 \alpha_3 s + 12 \alpha_4 s^2 + 20 \alpha_5 s^3 + 30 \alpha_6 s^4 & = 0 \\ 6 \alpha_3 + 24 \alpha_4 s + 60 \alpha_5 s^2 + 120 \alpha_6 s^3 & = 0 \\ 24 \alpha_4 + 120 \alpha_5 s + 360 \alpha_6 s^2 & = 0 \\ 120 \alpha_5 + 720 \alpha_6 s & = 0 \\ 720 \alpha_6 & = 0 \\ \end{align*} Now, substituting $s = 0$ in the last 7 equalities yields \begin{align*} \alpha_0 & = 0 \\ \alpha_1 & = 0 \\ 2 \alpha_2 & = 0 \\ 6 \alpha_3 & = 0 \\ 24 \alpha_4 & = 0 \\ 120 \alpha_5 & = 0 \\ 720 \alpha_6 & = 0 \\ \end{align*} Hence, $\alpha_0 = \alpha_1 = \alpha_2 = \alpha_3 = \alpha_4 =\alpha_5 = \alpha_6 = 0.$ This proves that the functions $\mathbf x_0, \mathbf x_1, \ldots, \mathbf x_{n}$ are linearly independent.
The method that we used for 7 functions $\mathbf x_0, \mathbf x_1, \mathbf x_2, \mathbf x_3,\mathbf x_4, \mathbf x_5, \mathbf x_{6}$ can be used for $n$ functions $\mathbf x_k$ with $k \in \{0,1,\ldots,n\}$ for every positive integer $n.$ Assume that \[ \sum_{j=0}^n \alpha_j \mathbf x_j = \mathbf 0. \] That is, assume that for every $t \in \mathbb R$ we have \[ \sum_{j=0}^n \alpha_j (\cos t)^j = 0. \] Substitution $s = \cos t$ yields that for every $s \in [-1,1]$ we have \[ \sum_{j=0}^n \alpha_j s^j = 0. \] Let $k \in \{0,1,\ldots,n\}$ be arbitrary. Taking the $k$-th derivative with respect to $s$ of both sides of the preceding equality yields that for all $s \in (-1,1)$ we have \[ \sum_{j=k}^n \frac{j!}{(j-k)!} \alpha_j s^{j-k} = 0. \] Now, substituting $s = 0$ in the last equality gives \[ k! \alpha_k = 0. \] Since $k! \neq 0$, we obtain $\alpha_k = 0.$ Since $k \in \{0,1,\ldots,n\}$ was arbitrary we have proved that $\alpha_k = 0$ for all $k \in \{0,1,\ldots,n\}.$ Thus, we have proved the implication \[ \sum_{j=0}^n \alpha_j \mathbf x_j = \mathbf 0 \quad \Rightarrow \quad \alpha_k = 0 \ \ \text{for all} \ \ k \in \{0,1,\ldots,n\}. \] That is, we proved that the vectors $\mathbf x_0, \mathbf x_1, \ldots, \mathbf x_{n}$ are linearly independent. - Since the vectors $\mathbf x_0, \mathbf x_1, \ldots, \mathbf x_{n}$ are linearly independent, the set \[ \mathcal B_n = \bigl\{ \mathbf x_0, \mathbf x_1, \ldots, \mathbf x_{n} \bigr\} \] is a basis of the space \[ \mathcal M_n = \operatorname{span} \bigl\{ \mathbf x_0, \mathbf x_1, \ldots, \mathbf x_{n} \bigr\}. \] Here $n$ is an arbitrary positive integer.
- Now recall that we established the following facts: The set \[ \mathcal B_6 = \bigl\{ \mathbf x_0, \mathbf x_1, \mathbf x_2, \mathbf x_3, \mathbf x_4, \mathbf x_5, \mathbf x_{6} \bigr\} \] is a basis of the space \[ \mathcal M_6 = \operatorname{Span} \bigl\{ \mathbf x_0, \mathbf x_1, \mathbf x_2, \mathbf x_3, \mathbf x_4, \mathbf x_5, \mathbf x_{6} \bigr\}. \] The following identities hold: \begin{align*} \mathbf y_0 & = \mathbf x_0 \\ \mathbf y_1 & = \mathbf x_1 \\ \mathbf y_2 & = - \mathbf x_0 + 2 \mathbf x_2 \\ \mathbf y_3 & = - 3 \mathbf x_1 + 4 \mathbf x_3 \\ \mathbf y_4 & = \mathbf x_0 - 8 \mathbf x_2 + 8 \mathbf x_4 \\ \mathbf y_5 & = 5 \mathbf x_1 - 20 \mathbf x_3 + 16 \mathbf x_5 \\ \mathbf y_6 & = - \mathbf x_0 + 18 \mathbf x_2 - 48 \mathbf x_4 + 32 \mathbf x_6 \\ \end{align*} In particular \[ \operatorname{Span} \bigl\{ \mathbf y_0, \mathbf y_1, \mathbf y_2, \mathbf y_3, \mathbf y_4, \mathbf y_5, \mathbf y_{6} \bigr\} \subseteq \operatorname{Span} \bigl\{ \mathbf x_0, \mathbf x_1, \mathbf x_2, \mathbf x_3, \mathbf x_4, \mathbf x_5, \mathbf x_{6} \bigr\} = \mathcal M_6. \] Since $\mathcal B_6$ is a basis of $\mathcal M_6$, the formulas for $\mathbf y$-s in terms of $\mathbf x$-s can be expressed as coordinate vectors as follows: \[ \bigl[ \mathbf y_0\!\bigr]_{\mathcal B_6}\!\!=\!\!\left[\!\begin{array}{r} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\!\right]\!\!, \bigl[ \mathbf y_1\!\bigr]_{\mathcal B_6}\!\!=\!\!\left[\!\begin{array}{r} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\!\right]\!\!, \bigl[ \mathbf y_2\!\bigr]_{\mathcal B_6}\!\!=\!\!\left[\!\!\begin{array}{r} -1 \\ 0 \\ 2 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\!\right]\!\!, \bigl[ \mathbf y_3\!\bigr]_{\mathcal B_6}\!\!=\!\!\left[\!\!\begin{array}{r} 0 \\ -3 \\ 0 \\ 4 \\ 0 \\ 0 \\ 0 \end{array}\!\right]\!\!, \bigl[ \mathbf y_4\!\bigr]_{\mathcal B_6}\!\!=\!\!\left[\!\!\begin{array}{r} 1 \\ 0 \\ -8 \\ 0 \\ 8 \\ 0 \\ 0 \end{array}\!\right]\!\!, \bigl[ \mathbf y_5\!\bigr]_{\mathcal B_6}\!\!=\!\!\left[\!\!\begin{array}{r} 0 \\ 5 \\ 0 \\ -20 \\ 0 \\ 16 \\ 0 \end{array}\!\right]\!\!, \bigl[ \mathbf y_6\!\bigr]_{\mathcal B_6}\!\!=\!\!\left[\!\!\begin{array}{r} -1 \\ 0 \\ 18 \\ 0 \\ -48 \\ 0 \\ 32 \end{array}\!\right]\!\!. \]
-
The coordinate vectors in the previous item answer the question (a) in Problem 34 in Section 4.5. To answer the question (b) in this problem we need to prove that the functions $\mathbf y_0, \mathbf y_1, \mathbf y_2, \mathbf y_3, \mathbf y_4, \mathbf y_5, \mathbf y_{6}$ are linearly independent.
Here is a proof that the functions $\mathbf y_0, \mathbf y_1, \mathbf y_2, \mathbf y_3, \mathbf y_4, \mathbf y_5, \mathbf y_{6}$ are linearly independent.
Let $\beta_0, \beta_1, \beta_2, \beta_3, \beta_4, \beta_5, \beta_6 \in \mathbb R$ and assume that \[ \beta_0 \mathbf y_0 + \beta_1 \mathbf y_1+ \beta_2 \mathbf y_2+ \beta_3 \mathbf y_3+ \beta_4 \mathbf y_4+ \beta_5 \mathbf y_5+ \beta_6 \mathbf y_{6} = \mathbf 0. \] Now apply the coordinate mapping $[\cdot]_{\mathcal B_6} : \mathcal M_6 \to \mathbb R^7$ defined by $\mathbf v \mapsto [\mathbf v]_{\mathcal B_6}$ where $\mathbf v$ is an arbitrary function in $\mathcal M_6.$ \[ \bigl[\beta_0 \mathbf y_0 + \beta_1 \mathbf y_1+ \beta_2 \mathbf y_2+ \beta_3 \mathbf y_3+ \beta_4 \mathbf y_4+ \beta_5 \mathbf y_5+ \beta_6 \mathbf y_{6}\bigr]_{\mathcal B_6} = \bigl[\mathbf 0\bigr]_{\mathcal B_6}. \] Next, recall that the coordinate mapping is linear to conclude that \[ \beta_0 \bigl[\mathbf y_0\bigr]_{\mathcal B_6} + \beta_1 \bigl[\mathbf y_1\bigr]_{\mathcal B_6}+ \beta_2 \bigl[\mathbf y_2\bigr]_{\mathcal B_6} + \beta_3 \bigl[\mathbf y_3\bigr]_{\mathcal B_6}+ \beta_4\bigl[\mathbf y_4\bigr]_{\mathcal B_6}+ \beta_5 \bigl[\mathbf y_5\bigr]_{\mathcal B_6}+ \beta_6 \bigl[\mathbf y_{6}\bigr]_{\mathcal B_6} = \bigl[\mathbf 0\bigr]_{\mathcal B_6}. \] Now we rewrite the previous equality using the coordinate vectors from the previous item: \[ \beta_0 \left[\!\begin{array}{r} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\!\right]\!+\beta_1\!\left[\!\begin{array}{r} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\!\right]\!+\beta_2\!\left[\!\!\begin{array}{r} -1 \\ 0 \\ 2 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\!\right]\!+\beta_3\!\left[\!\!\begin{array}{r} 0 \\ -3 \\ 0 \\ 4 \\ 0 \\ 0 \\ 0 \end{array}\!\right]\!+\beta_4\!\left[\!\!\begin{array}{r} 1 \\ 0 \\ -8 \\ 0 \\ 8 \\ 0 \\ 0 \end{array}\!\right]\!+\beta_5\!\left[\!\!\begin{array}{r} 0 \\ 5 \\ 0 \\ -20 \\ 0 \\ 16 \\ 0 \end{array}\!\right]\!+\beta_6\!\left[\!\!\begin{array}{r} -1 \\ 0 \\ 18 \\ 0 \\ -48 \\ 0 \\ 32 \end{array}\!\right] = \left[\!\begin{array}{r} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\!\right]. \] The preceding vector equation is equivalent to the following matrix equation \[ \left[\!\begin{array}{rrrrrrr} 1 & 0 & -1 & 0 & 1 & 0 & -1 \\ 0 & 1 & 0 & -3 & 0 & 5 & 0 \\ 0 & 0 & 2 & 0 & -8 & 0 & 18 \\ 0 & 0 & 0 & 4 & 0 & -20 & 0 \\ 0 & 0 & 0 & 0 & 8 & 0 & -48 \\ 0 & 0 & 0 & 0 & 0 & 16 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 32 \end{array}\!\right] \left[\!\begin{array}{r} \beta_0 \\ \beta_1 \\ \beta_2 \\ \beta_3 \\ \beta_4 \\ \beta_5 \\ \beta_6 \end{array}\!\right] = \left[\!\begin{array}{r} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\!\right]. \] Since the matrix in the last equation is upper triangular with the nonzero entries on the diagonal, the above equation has only the trivial solution. That is \[ \beta_0 = \beta_1 = \beta_2 = \beta_3 = \beta_4 = \beta_5 = \beta_6 = 0. \] Thus, we have proved the implication \[ \sum_{j=0}^6 \beta_j \mathbf y_j = \mathbf 0 \quad \Rightarrow \quad \beta_k = 0 \ \text{for all} \ k \in\{0,1,\ldots,n\}. \] Consequently, the functions $\mathbf y_0, \mathbf y_1, \mathbf y_2, \mathbf y_3, \mathbf y_4, \mathbf y_5, \mathbf y_{6}$ are linearly independent.
Since $\mathbf y_0, \mathbf y_1, \mathbf y_2, \mathbf y_3, \mathbf y_4, \mathbf y_5, \mathbf y_{6} \in \mathcal M_6$, $\dim \mathcal M_6 = 7$ and $\mathbf y_0, \mathbf y_1, \mathbf y_2, \mathbf y_3, \mathbf y_4, \mathbf y_5, \mathbf y_{6}$ are linearly independent, by Theorem 12 in Section 4.5 (The Basis Theorem) the set \[ \mathcal C_6 = \{\mathbf y_0, \mathbf y_1, \mathbf y_2, \mathbf y_3, \mathbf y_4, \mathbf y_5, \mathbf y_{6}\} \] is a basis for $\mathcal M_6.$ - As before, there is nothing special about the number $6$ in the previous item. The conclusion holds for an arbitrary positive integer $n$: the functions $\mathbf y_k$ with $k \in \{0,1,\ldots,n\}$ are linearly independent. The set of functions \[ \mathcal C_n = \{\mathbf y_0, \mathbf y_1, \ldots, \mathbf y_{n}\} \] is a basis of the space $\mathcal M_n.$ The proofs are very similar to the special case of $n=6.$
- By Theorem 15 in Section 4.7 and the previous calculations we have \[ P_{{\mathcal B}_6 \leftarrow {\mathcal C}_6} = \left[\!\begin{array}{rrrrrrr} 1 & 0 & -1 & 0 & 1 & 0 & -1 \\ 0 & 1 & 0 & -3 & 0 & 5 & 0 \\ 0 & 0 & 2 & 0 & -8 & 0 & 18 \\ 0 & 0 & 0 & 4 & 0 & -20 & 0 \\ 0 & 0 & 0 & 0 & 8 & 0 & -48 \\ 0 & 0 & 0 & 0 & 0 & 16 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 32 \end{array}\!\right] \] Since $P_{{\mathcal C}_6 \leftarrow {\mathcal B}_6} = \bigl(P_{{\mathcal B}_6 \leftarrow {\mathcal C}_6}\bigr)^{-1},$ we have \[ P_{{\mathcal C}_6 \leftarrow {\mathcal B}_6} = \left[ \begin{array}{ccccccc} 1 & 0 & \frac{1}{2} & 0 & \frac{3}{8} & 0 & \frac{5}{16} \\ 0 & 1 & 0 & \frac{3}{4} & 0 & \frac{5}{8} & 0 \\ 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & \frac{15}{32} \\ 0 & 0 & 0 & \frac{1}{4} & 0 & \frac{5}{16} & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{8} & 0 & \frac{3}{16} \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{16} & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{32} \end{array} \right] \] Again, by Theorem 15 in Section 4.7 we have \begin{align*} \mathbf x_0 & = \mathbf y_0 \\ \mathbf x_1 & = \mathbf y_1 \\ \mathbf x_2 & = \frac{1}{2} \bigl( \mathbf y_0 + \mathbf y_2 \bigr) \\ \mathbf x_3 & = \frac{1}{4} \bigl( 3 \mathbf y_1 + \mathbf y_3 \bigr) \\ \mathbf x_4 & = \frac{1}{8} \bigl( 3 \mathbf y_0 + 4 \mathbf y_2 + \mathbf y_4 \bigr) \\ \mathbf x_5 & = \frac{1}{16} \bigl( 10 \mathbf y_1 + 5 \mathbf y_3 + \mathbf y_5 \bigr) \\ \mathbf x_6 & = \frac{1}{32} \bigl( 10 \mathbf y_0 + 15 \mathbf y_2 +6 \mathbf y_4 + \mathbf y_6 \bigr) \end{align*} This solves Problem 17 in Section 4.7.
- It is nice to rewrite the last formulas of the previous item in terms of the specific funcions which are involved: \begin{align*} 1 & = 1 \\ \cos t & = \cos t \\ (\cos t)^2 & = \frac{1}{2} \bigl( 1 + \cos(2t) \bigr) \\ (\cos t)^3 & = \frac{1}{4} \bigl( 3 \cos(t) + \cos(3t) \bigr) \\ (\cos t)^4 & = \frac{1}{8} \bigl( 3 + 4 \cos(2t) + \cos(4t) \bigr) \\ (\cos t)^5 & = \frac{1}{16} \bigl( 10 \cos(t)+ 5 \cos(3t) + \cos(5t)\bigr) \\ (\cos t)^6 & = \frac{1}{32} \bigl( 10 + 15 \cos(2t) +6 \cos(4t) + \cos(6t)\bigr) \end{align*} It is truly remarkable that in Chapter 6 we will develop a completely different way of deriving formulas like these. See Section 6.7, specifically An Inner Product for $C[a,b]$ on page 433 and Section 6.8, specifically Fourier Series on page 440. It turns out that in the sense of Section 6.7 the functions $\cos(kt)$ are mutually orthogonal. Using the method from Section 6.8 we will be able to derive the following formulas \begin{align*} (\cos t)^{2m} & = \frac{1}{2^{2m}} \binom{2m}{m} + \frac{1}{2^{2m-1}} \sum_{k=1}^{m} \binom{2m}{m-k} \cos(2kt) \\ (\cos t)^{2m+1} & =\frac{1}{2^{2m}} \sum_{k=0}^{m} \binom{2m+1}{m-k} \cos((2k+1)t) \end{align*} for all nonnegative integers $m.$
-
And finally, it would be nice to plot these fourteen functions:
And all seven multiple angle cosine functions on one graph:
${\mathbf y}_0 = 1$
${\mathbf x}_0 = 1$
${\mathbf y}_1 = \cos t$
${\mathbf x}_1 = \cos t$
${\mathbf y}_2 = \cos(2t)$
${\mathbf x}_2 = (\cos t)^2$
${\mathbf y}_3 = \cos(3t)$
${\mathbf x}_3 = (\cos t)^3$
${\mathbf y}_4 = \cos(4t)$
${\mathbf x}_4 = (\cos t)^4$
${\mathbf y}_5 = \cos(5t)$
${\mathbf x}_5 = (\cos t)^5$
${\mathbf y}_6 = \cos(6t)$
${\mathbf x}_6 = (\cos t)^6$
Finally it is nice to illustrate how gradually partial approximations of $(\cos t)^6$ by multiple cosines gradually approach this function.
$(\cos t)^6 \approx \frac{5}{16}$
$(\cos t)^6 \approx \frac{5}{16}+\frac{15}{32} \cos(2t)$
$(\cos t)^6 \approx \frac{5}{16}+\frac{15}{32} \cos(2t)+\frac{3}{16} \cos(4t)$
$(\cos t)^6 = \frac{5}{16}+\frac{15}{32} \cos(2t)+\frac{3}{16} \cos(4t)+\frac{1}{32} \cos(6t)$
-
The first remarkable fact about these functions is that for an arbitrary positive integer $n$ we have
\[
\mathbf y_n \in \operatorname{span} \bigl\{ \mathbf x_0, \mathbf x_1,\ldots,\mathbf x_n \bigr\}.
\]
To prove this claim we need trigonometric identities presented in the textbook in Problem 34 in Section 4.5. I will prove those identities here. The proof is based on the addition formulas for the cosine function. The method I present here is called Chebyshev method. Let $n$ be a positive integer greater than $1.$ Then we have
\begin{align*}
\cos(nt) = \cos\bigl((n-1)t + t \bigr) & = \cos\bigl((n-1)t \bigr) \cos t - \sin\bigl((n-1)t \bigr) \sin t \\
\cos\bigl((n-2)t \bigr) = \cos\bigl((n-1)t - t \bigr) & = \cos\bigl((n-1)t \bigr) \cos t + \sin\bigl((n-1)t \bigr) \sin t \\
\end{align*}
Adding the last two identities yields
\[
\cos(nt) + \cos\bigl((n-2)t \bigr) = 2 \cos\bigl((n-1)t \bigr) \cos t
\]
and, more importantly, we have
\begin{equation*} \tag{rr}
\cos(nt) = 2 \cos\bigl((n-1)t \bigr) \cos t - \cos\bigl((n-2)t \bigr).
\end{equation*}
This formula gives $\cos(nt)$ in terms of two previous multiple angle cosines $\cos\bigl((n-1)t \bigr)$ and $\cos\bigl((n-2)t \bigr).$ Such a formula is called a recursion or a recurrence relation. For $n=2$ we have \[
\cos(2t) = 2 \cos(1t) \cos t - \cos(0t) = 2(\cos t)^2 - 1.
\]
Or, in our notation
\[
\mathbf y_2 = - \mathbf x_0 + 2 \mathbf x_2.
\]
That is $\mathbf y_2 \in \operatorname{span} \bigl\{\mathbf x_0, \mathbf x_2\bigr\}.$ Next we apply the recursion (rr) to $n=3$ and we get (using already established formula for $\cos(2t)$)
\[
\cos(3t) = 2 \cos(2t) \cos t - \cos t = 2\bigl( 2(\cos t)^2 - 1 \bigr) \cos t - \cos t = 4 (\cos t)^3 - 3 \cos t.
\]
That is
\[
\mathbf y_3 = - 3 \mathbf x_1 + 4 \mathbf x_3,
\]
implying that $\mathbf y_3 \in \operatorname{span} \bigl\{\mathbf x_1, \mathbf x_3\bigr\}.$ Continuing to $n=4$ we get
\begin{align*}
\cos(4t) & = 2 \cos(3t) \cos t - \cos(2t) \\
& = 2 \bigl( 4 (\cos t)^3 - 3 \cos t \bigr) \cos t - \bigl(2(\cos t)^2 - 1 \bigr) \\
& = 8 (\cos t)^4 - 8 (\cos t)^2 + 1.
\end{align*}
That is
\[
\mathbf y_4 = \mathbf x_0 - 8 \mathbf x_2 + 8 \mathbf x_4,
\]
implying that $\mathbf y_4 \in \operatorname{span} \bigl\{\mathbf x_0, \mathbf x_2, \mathbf x_4 \bigr\}.$ Continuing to $n=5$ we get
\begin{align*}
\cos(5t) & = 2 \cos(4t) \cos t - \cos(3t) \\
& = 2 \bigl( 8 (\cos t)^4 - 8 (\cos t)^2 + 1 \bigr) \cos t - \bigl( 4 (\cos t)^3 - 3 \cos t \bigr) \\
& = 16 (\cos t)^5 - 20 (\cos t)^3 + 5 \cos t.
\end{align*}
That is
\[
\mathbf y_5 = 5 \mathbf x_1 - 20 \mathbf x_3 + 16 \mathbf x_5,
\]
implying that $\mathbf y_5 \in \operatorname{span} \bigl\{\mathbf x_1, \mathbf x_3, \mathbf x_5 \bigr\}.$ Continuing to $n=6$ we get
\begin{align*}
\cos(6t) & = 2 \cos(5t) \cos t - \cos(4t) \\
& = 2 \bigl( 16 (\cos t)^5 - 20 (\cos t)^3 + 5 \cos t \bigr) \cos t - \bigl( 8 (\cos t)^4 - 8 (\cos t)^2 + 1 \bigr) \\
& = 32 (\cos t)^6 - 48 (\cos t)^4 + 18 (\cos t)^2 - 1.
\end{align*}
That is
\[
\mathbf y_6 = - \mathbf x_0 + 18 \mathbf x_2 - 48 \mathbf x_4 + 32 \mathbf x_6,
\]
implying that $\mathbf y_6 \in \operatorname{span} \bigl\{\mathbf x_0, \mathbf x_2, \mathbf x_4, \mathbf x_6 \bigr\}.$
- The information sheet
-
We will start with a review. Please review
- The definition of a basis in Section 4.3 and Examples 3, 4, 5, 6 and 10; Practice Problems 1, 2, 3, Exercises 1-8 and 38.
- Section 4.4: Theorem 7, the definition of coordinates with respect to a basis, the definition of a change-of-coordinates matrix on page 249 and the definition and the properties of a coordinate mapping; Examples 1, 2, 4, 5, 6; Practice Problems 1, 2; Exercises 3, 4, 5, 7, 9, 10, 11, 13, 18, 21, 32.
- Section 4.5: Theorem 10, the definition of a finite-dimensional vector space and its dimension and the Basis Theorem; Examples 1, 2, 3, 4; Practice Problems 1, 2; Exercises 2, 3, 7, 22, 24, and 34.
- Section 4.7 Change of Basis. Suggested exercises are 2, 3, 4, 6, 8, 9, 11, 12, 13, 14, 15, 16, 17, 19, 20.
- In exercises 38 from Section 4.3, 34 from Section 4.5 and 17 from Section 4.7 you are asked to work in a seven-dimensional vector space of trigonometric functions whose basis is: \[ \mathcal B = \{ \mathbf x_0, \cdots, \mathbf x_6 \} \quad \text{where} \quad \mathbf x_k = (\cos t)^k, \ k \in \{0,1,\ldots,6\}. \] It turns out that another basis of this space is \[ \mathcal C = \{ \mathbf y_0, \cdots, \mathbf y_6 \} \quad \text{where} \quad \mathbf y_k = \cos( k t), \ k \in \{0,1,\ldots,6\}. \] Since this is a seven-dimensional vector space all calculations are long. You can get a good sense how to proceed with this problem by studying subspaces of this space; for example, a four-dimensional subspace spanned by $\{ \mathbf x_0, \mathbf x_1, \mathbf x_2, \mathbf x_3 \}.$
-
It is a good idea to familiarize yourself with the software package Mathematica. We have Mathematica version 8.
- In class I demonstrated the Mathematica file Change_of_Coordinates. The file is called Change_of_Coordinates.nb. Notice that in file names I always use the underscore symbol instead of just a blank space.
- First download the file to your computer. Right-click on this underlined link. In the pop-up menu that appears your browser will offer you to save the file in your directory. Make sure that you save it with the exactly same name. After saving the file you can open it with Mathematica 8. You will find Mathematica 8 on all computers in BH 215. Open Mathematica first, then open Change_of_Coordinates.nb from Mathematica.
- More information on how to use Mathematica version 8 you can find on my Mathematica 8 page.