- Since we are working with vectors in this class, and since I am using colors to clarify relationship between various mathematical quantities that we encounter, I hope you will find it useful to see how colors can be organized using vectors in the unit cube; see the web-page dedicated to the Color Cube
- Here is a list of topics for the fin exam.
- Suggested problems for Section 7.4: 3, 7, 11, 13, 14, 15, 17, 21
-
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].
\]
- (I) 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]. \]
- (II) 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$.
- (III) To complete the matrix $U$ we need an orthonormal basis for $\mathbb{R}^4$. 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]. \]
- 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. 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.
- During the class today I created this Mathematica file. The file is called 20190814.nb. Right-click on the 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.
- Suggested problems for Section 7.2: 1, 3, 5, 7, 9, 13, 17, 19, 20, 21, 23, 25
-
I will write about polychotomies in mathematics here. A polychotomy is a partition of a given set of mathematical objects into disjoint classes which are all given distinct names.
-
A dichotomy is a partition of a given set of mathematical objects into two disjoint classes each of which is given a name. The following are examples of dichotomies.
- The most important dichotomy for numbers is the partition of numbers into the singleton set $\{0\}$ consisting of only zero and the set of all nonzero numbers. Further, dichotomy for the nonzero real numbers is the partition of the nonzero real numbers into positive real numbers and negative real numbers.
- An important dichotomy for the set of real numbers is the partition into rational and irrational numbers.
- A useful dichotomy for complex numbers is the partition of the complex numbers into the real and nonreal numbers. A complex number $z$ is said to be nonreal if the imaginary part of $z$ is nonzero.
- Consider the set of all square matrices. A square matrix $M$ is said to be singular if $\det M = 0.$ A square matrix $M$ is said to be nonsingular if $\det M \neq 0.$ You also learned that a square matrix is invertible if and only if it is nonsingular. Thus, singular-invertible is a dichotomy for square matrices.
-
A trichotomy is a partition of a given set of mathematical objects into three disjoint classes each of which is given a name. The following are examples of trichotomies.
- The most important trichotomy for the set of real numbers is the partition of numbers into singleton set $\{0\}$ consisting of only zero, the set of positive real numbers and the set of negative real numbers. As we mention before this trichotomy arrises as two dichotomies.
- In high school you learned about the trichotomy involving quadratic equations $a x^2 + b x + c = 0$ with $a\neq 0.$ Such equation can have: no solutions, exactly one solution, and exactly two solutions.
-
A quadruplicity is a partition of a given set of mathematical objects into four disjoint classes each of which is given a name. I started writing about polychotomies because of the following quadruplicity which arrises with quadratic forms.
-
Let $Q : \mathbb R^n \to \mathbb R$ be a quadratic form. We distinguish the following four types of quadratic forms:
- $Q$ is said to be a zero quadratic form if $Q(\mathbf x) = 0$ for all $\mathbf x \in \mathbb R^n.$
- $Q$ is said to be a positive semidefinite quadratic form if $Q(\mathbf x) \geq 0$ for all $\mathbf x \in \mathbb R^n$ and there exists $\mathbf v \in \mathbb R^n$ such that $Q(\mathbf v) \gt 0.$
- $Q$ is said to be a negative semidefinite quadratic form if $Q(\mathbf x) \leq 0$ for all $\mathbf x \in \mathbb R^n$ and there exists $\mathbf v \in \mathbb R^n$ such that $Q(\mathbf v) \lt 0.$
- $Q$ is said to be an indefinite quadratic form if there exists $\mathbf v \in \mathbb R^n$ such that $Q(\mathbf v) \gt 0$ and there exists $\mathbf u \in \mathbb R^n$ such that $Q(\mathbf u) \lt 0.$
- $Q$ is said to be a positive definite quadratic form if $Q(\mathbf x) \gt 0$ for all $\mathbf x \in \mathbb R^n\!\setminus\!\{\mathbf 0\}.$
- $Q$ is said to be a negative definite quadratic form if $Q(\mathbf x) \lt 0$ for all $\mathbf x \in \mathbb R^n\!\setminus\!\{\mathbf 0\}.$
In the image below I give a graphical representation of the above quadruplicity. The red dot represents the zero quadratic form, the green region represents the positive semidefinite quadratic forms, the blue region represents the negative semidefinite quadratic forms and the cyan region represents the indefinite quadratic forms.
In the image above, the dark green region represents the positive definite quadratic forms and the dark blue region represents the negative definite quadratic forms. These two regions are not parts of the above quadruplicity.
-
Let $Q : \mathbb R^n \to \mathbb R$ be a quadratic form. We distinguish the following four types of quadratic forms:
-
A dichotomy is a partition of a given set of mathematical objects into two disjoint classes each of which is given a name. The following are examples of dichotomies.
- Suggested problems for Section 7.1: 3, 4, 9, 11, 15, 19, 23, 24, 25, 27, 30, 33, 35.
-
In the first Theorem in the next item we work with complex numbers. We review some basic facts about complex numbers.
The Complex Numbers. A complex number is commonly represented as $z = x + i y$ where $i$ is the imaginary unit with the property $i^2 = -1$ and $x$ and $y$ are real numbers. The real number $x$ is called the real part of $z$ and the real number $y$ is called the imaginary part of $z.$ A real number is a special complex numbers whose imaginary part is $0.$ The set of all complex numbers is denoted by $\mathbb C.$
The Complex Conjugate. By $\overline{z}$ we denote the complex conjugate of $z$. The complex conjugate of $z = x+i y$ is the complex number $\overline{z} = x - i y.$ That is, the complex conjugate $\overline{z}$ is the complex numer which has the same real part as $z$ and the imaginary part of $\overline{z}$ is the opposite of the imaginary part of $z.$ Since $-0 = 0$, a comlex number $z$ is real if and only if $\overline{z} = z.$ The operation of complex conjugation respects the algebraic operations with complex numbers: \[ \overline{z + w} = \overline{z} + \overline{w}, \quad \overline{z - w} = \overline{z} - \overline{w}, \quad \overline{z\, w} = \overline{z}\, \overline{w}. \]
The Modulus. Let $z = x + i y$ be a complex number. Here $x$ is the real part of $z$ and $y$ is the imaginary part of $z.$ The modulus of $z$ is the nonnegative number $\sqrt{x^2+y^2}.$ The modulus of $z$ is denoted by $|z|.$ Clearly, $|z|^2 = z\overline{z}$.
Vectors with Complex Entries. Let $\mathbf v$ be a vector with complex entries. By $\overline{\mathbf{v}}$ we denote the vector whose entries are complex conugates of the corresponding entries of $\mathbf v.$ That is, \[ \mathbf v = \left[\begin{array}{c} v_1 \\ \vdots \\ v_n \end{array} \right], \qquad \overline{\mathbf v} = \left[\begin{array}{c} \overline{v}_1 \\ \vdots \\ \overline{v}_n \end{array} \right]. \] The following calculation for a vector with complex entries is often useful \[ \mathbf{v}^\top \overline{\mathbf{v}} = \bigl[v_1 \ \ v_2 \ \ \cdots \ \ v_n \bigr] \left[\begin{array}{c} \overline{v}_1 \\ \overline{v}_2 \\ \vdots \\ \overline{v}_n \end{array} \right] = \sum_{k=1}^n v_k\, \overline{v}_k = \sum_{k=1}^n |v_k|^2 \geq 0. \] Moreover, \[ \mathbf{v}^\top \overline{\mathbf{v}} = 0 \quad \text{if and only if} \quad \mathbf{v} = \mathbf{0}. \]
-
There are several 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 $\mathbf{v} = \bigl[v_1 \ \ v_2 \ \ \cdots \ \ v_n \bigr]^\top$ be a corresponding eigenvector. Then $\mathbf{v} \neq \mathbf{0}.$ We allow the possibility that $\lambda$ and the entries $v_1,$ $v_2,\ldots,$ $v_n$ of $\mathbf{v}$ are complex numbers. Since $\mathbf{v}$ is an eigenvector of $A$ corresponding to $\lambda$ we have \[ A \mathbf{v} = \lambda \mathbf{v}. \] Since $A$ is a symmetric matrix, all the entries of $A$ are real numbers. It follows from the properties of the complex conjugation that taking the complex conjugate of each side of the equality $A \mathbf{v} = \lambda \mathbf{v}$ yields \[ A \overline{\mathbf{v}} = \overline{\lambda} \overline{\mathbf{v}}. \] Since $A$ is symmetric, that is $A=A^\top$, we also have \[ A^\top \overline{\mathbf{v}} = \overline{\lambda} \overline{\mathbf{v}}. \] Multiplying both sides of the last equation by $\mathbf{v}^\top$ we get \[ \mathbf{v}^\top \bigl( A^\top \overline{\mathbf{v}} \bigr) = \mathbf{v}^\top ( \overline{\lambda} \overline{\mathbf{v}}). \] Since $\mathbf{v}^\top A^\top = \bigl(A\mathbf{v}\bigr)^\top$ and $\mathbf{v}^\top ( \overline{\lambda} \overline{\mathbf{v}}) = \overline{\lambda} \mathbf{v}^\top \overline{\mathbf{v}}$ the last displayed equality is equivalent to \[ \bigl(A\mathbf{v}\bigr)^\top \overline{\mathbf{v}} = \overline{\lambda} \mathbf{v}^\top \overline{\mathbf{v}}. \] Since $A \mathbf{v} = \lambda \mathbf{v},$ we further have \[ \bigl(\lambda \mathbf{v}\bigr)^\top \overline{\mathbf{v}} = \overline{\lambda} \mathbf{v}^\top \overline{\mathbf{v}}. \] That is, \[ \tag{*} \lambda \mathbf{v}^\top \overline{\mathbf{v}} = \overline{\lambda} \mathbf{v}^\top \overline{\mathbf{v}}. \] As explained in Vectors with Complex Entries item, $\mathbf{v} \neq \mathbf{0},$ implies $\mathbf{v}^\top \overline{\mathbf{v}} \gt 0.$ Now dividing both sides of equality (*) by $\mathbf{v}^\top \overline{\mathbf{v}} \gt 0$ yields \[ \lambda = \overline{\lambda}. \] As explained in The Complex Conjugate item above, this proves that $\lambda$ is a real number.
Theorem. Eigenspaces of a symmetric matrix which correspond to distinct eigenvalues are ofthogonal.
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+d - \sqrt{(a-d)^2 + 4 b^2} \Bigr), \quad \lambda_2 = \frac{1}{2} \Bigl( a+d + \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 $\mathbf{u}_1$ be a unit eigenvector corresponding to $\lambda_1$ and let $\mathbf{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, $\mathbf{u}_1$ and $\mathbf{u}_2$ are orthogonal, that is the matrix $U = \begin{bmatrix} \mathbf{u}_1 & \mathbf{u}_2 \end{bmatrix}$ is orthogonal. Since $\mathbf{u}_1$ and $\mathbf{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 $\mathbf{u}_1$ be a corresponding unit eigenvector. Let $\mathbf{v}_1$ and $\mathbf{v}_2$ be unit vectors such that the vectors $\mathbf{u}_1,$ Let $\mathbf{v}_1$ and $\mathbf{v}_2$ form an orthonormal basis for $\mathbb R^3.$ Then the matrix $V_1 = \bigl[\mathbf{u}_1 \ \ \mathbf{v}_1\ \ \mathbf{v}_2\bigr]$ is an orthogonal matrix and we have \[ V_1^\top A V_1 = \begin{bmatrix} \mathbf{u}_1^\top A \mathbf{u}_1 & \mathbf{u}_1^\top A \mathbf{v}_1 & \mathbf{u}_1^\top A \mathbf{v}_2 \\[5pt] \mathbf{v}_1^\top A \mathbf{u}_1 & \mathbf{v}_1^\top A \mathbf{v}_1 & \mathbf{v}_1^\top A \mathbf{v}_2 \\[5pt] \mathbf{v}_2^\top A \mathbf{u}_1 & \mathbf{v}_2^\top A \mathbf{v}_1 & \mathbf{v}_2^\top A \mathbf{v}_2 \\\end{bmatrix}. \] Since $A = A^\top$, $A\mathbf{u}_1 = \lambda_1 \mathbf{u}_1$ and since $\mathbf{u}_1$ is orthogonal to both $\mathbf{v}_1$ and $\mathbf{v}_2$ we have \[ \mathbf{u}_1^\top A \mathbf{u}_1 = \lambda_1, \quad \mathbf{v}_j^\top A \mathbf{u}_1 = \lambda_1 \mathbf{v}_j^\top \mathbf{u}_1 = 0, \quad \mathbf{u}_1^\top A \mathbf{v}_j = \bigl(A \mathbf{u}_1\bigr)^\top \mathbf{v}_j = 0, \quad \quad j \in \{1,2\}, \] and \[ \mathbf{v}_2^\top A \mathbf{v}_1 = \bigl(\mathbf{v}_2^\top A \mathbf{v}_1\bigr)^\top = \mathbf{v}_1^\top A^\top \mathbf{v}_2 = \mathbf{v}_1^\top A \mathbf{v}_2. \] Hence, \[ \tag{**} V_1^\top A V_1 = \begin{bmatrix} \lambda_1 & 0 & 0 \\[5pt] 0 & \mathbf{v}_1^\top A \mathbf{v}_1 & \mathbf{v}_1^\top A \mathbf{v}_2 \\[5pt] 0 & \mathbf{v}_1^\top A \mathbf{v}_2 & \mathbf{v}_2^\top A \mathbf{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} \mathbf{v}_1^\top A \mathbf{v}_1 & \mathbf{v}_1^\top A \mathbf{v}_2 \\[5pt] \mathbf{v}_1^\top A \mathbf{v}_2 & \mathbf{v}_2^\top A \mathbf{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.
-
On Wednesday we did Exercise 4 in Section 6.6. In this exercise we are given four data points
\[
( 2,3), \ \ (3,2), \ \ (5,1), \ \ (6,0),
\]
and we are asked to find the least-squares line that best fits the given data points. (We will call this line simply the least-squares line.)
- In class I noticed that these four points form a very narrow parallelogram. A characterizing property of a parallelogram is that its diagonals share the midpoint. For this parallelogram, the coordinates of the common midpoint of the diagonals are \[ \overline{x} = \frac{1}{4}(2+3+5+6) = 4, \quad \overline{y} = \frac{1}{4}(3+2+1+0) = 3/2. \] The long sides of this parallelogram are on the parallel lines $y = -2x/3 +4$ and $y = -2x/3 + 13/3.$ My guess in class was that the least square line is the line which is parallel to these two lines and half-way between them. That is the line $y = -2x/3 + 25/6.$ This line is the red line in the picture below. Clearly this line goes through the point $(4,3/2),$ the intersection of the diagonals of the parallelogram. The only way to verify this quess was to calculate the least-squares line for these four points. We did that by finding the least-squares solution of the equation \[ \left[\begin{array}{cc} 1 & 2 \\ 1 & 3 \\ 1 & 5 \\ 1 & 6 \end{array} \right] \left[\begin{array}{c} \beta_0 \\ \beta_1 \end{array} \right] = \left[\begin{array}{c} 3 \\ 2 \\ 1 \\ 0 \end{array} \right]. \] The corresponding normal equation is \[ \left[\begin{array}{cc} 4 & 16 \\ 16 & 74 \end{array} \right] \left[\begin{array}{c} \beta_0 \\ \beta_1 \end{array} \right] = \left[\begin{array}{c} 6 \\ 17 \end{array} \right]. \] Since the inverse of the above $2\!\times\!2$ matrix is \[ \frac{1}{40} \left[\begin{array}{cc} 74 & -16 \\ -16 & 4 \end{array} \right], \] the least-squares line for the given data points is \[ y = -\frac{7}{10}x + \frac{43}{10}. \] This line is the blue line in the picture below. The picture below strongly indicates that the blue line also goes through the point $(4,3/2).$ This is easily confirmed: \[ \frac{3}{2} = -\frac{7}{10}4 + \frac{43}{10}. \]
In the image below the the forest green points are the given data points. The red line is the line which I guessed could be the least-squares line. The blue line is the true least-squares line.
-
It is amazing that what we observed in the preceeding example is a universal:
Proposition. If the line $y = \beta_0 + \beta_1 x$ is the least-squares line for the data points \[ (x_1,y_1), \ldots, (x_m,y_m), \] then $\overline{y} = \beta_0 + \beta_1 \overline{x}$, where \[ \overline{x} = \frac{1}{m}(x_1+\cdots+x_m), \quad \overline{y} = \frac{1}{m}(y_1+\dots+y_m). \]
The above proposition is Exercise 14 in Section 6.6.Proof. Let \[ (x_1,y_1), \ldots, (x_m,y_m), \] be given data points and set \[ \overline{x} = \frac{1}{m}(x_1+\cdots+x_m), \quad \overline{y} = \frac{1}{m}(y_1+\dots+y_m). \] Let $y = \beta_0 + \beta_1 x$ be the least-squares line for the given data points. Then the vector $\left[\begin{array}{c} \beta_0 \\ \beta_1 \end{array} \right]$ satisfies the normal equation \[ \left[\begin{array}{cccc} 1 & 1 & \cdots & 1 \\ x_1 & x_2 & \cdots & x_m \end{array} \right] \left[\begin{array}{cc} 1 & x_1 \\ 1 & x_2 \\ \vdots & \vdots \\ 1 & x_m \end{array} \right] \left[\begin{array}{c} \beta_0 \\ \beta_1 \end{array} \right] = \left[\begin{array}{cccc} 1 & 1 & \cdots & 1 \\ x_1 & x_2 & \cdots & x_m \end{array} \right] \left[\begin{array}{c} y_1 \\ y_2 \\ \vdots \\ y_m \end{array} \right]. \] Multiplying the second matrix on the left-hand side and the third vector we get \[ \left[\begin{array}{cccc} 1 & 1 & \cdots & 1 \\ x_1 & x_2 & \cdots & x_m \end{array} \right] \left[\begin{array}{c} \beta_0 + \beta_1 x_1 \\ \beta_0 + \beta_1 x_2 \\ \vdots \\ \beta_0 + \beta_1 x_m \end{array} \right] = \left[\begin{array}{cccc} 1 & 1 & \cdots & 1 \\ x_1 & x_2 & \cdots & x_m \end{array} \right] \left[\begin{array}{c} y_1 \\ y_2 \\ \vdots \\ y_m \end{array} \right]. \] The above equality is an equality of vectors with two components. The top components of these vectors are equal: \[ (\beta_0 + \beta_1 x_1) + (\beta_0 + \beta_1 x_2) + \cdots + (\beta_0 + \beta_1 x_m) = y_1 + y_2 + \cdots + y_m. \] Therefore \[ m \beta_0 + \beta_1 (x_1+x_3 + \cdots + x_m) = y_1 + y_2 + \cdots + y_m. \] Dividing by $m$ we get \[ \beta_0 + \beta_1 \frac{1}{m} (x_1+x_3 + \cdots + x_m) = \frac{1}{m}( y_1 + y_2 + \cdots + y_m). \] Hence \[ \overline{y} = \beta_0 + \beta_1 \overline{x}. \] QED.
- Here is a list of topics for the second exam.
- During the class today I created this Mathematica file. The file is called 20190731.nb. Right-click on the 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.
- When you open the file 20190731.nb you can go through the notebook cell by cell and evaluate each cell individually, or you can evaluate the entire notebook by the keyboard sequence Alt+v o or with the manu item Evaluate ⇾ Evaluate Notebook.
-
You will find Mathematica 8 on computers in BH 215 and in the Math Center. Look in
Start -> Wolfram Mathematica -> Mathematica 8. Open Mathematica first, then open 20190405.nb from Mathematica. - More information on how to use Mathematica version 8 you can find on my Mathematica 8 page.
- Suggested problems for Section 6.6: 1, 2, 3, 4, 5, 6, 7, 8, 9, 14, 15, 16
-
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.
- 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 \[ \mathbf{x} \in \operatorname{Nul}(A^\top\!\! A ) \quad \text{if and only if} \quad \mathbf{x} \in \operatorname{Nul}(A). \] So, we prove this equivalence. Assume that $\mathbf{x} \in \operatorname{Nul}(A)$. Then $A\mathbf{x} = \mathbf{0}$. Consequently, $A^\top\!A\mathbf{x} = A^\top\mathbf{0} = \mathbf{0}$. Hence, $A^\top\!A\mathbf{x}= \mathbf{0}$, and therefore $\mathbf{x} \in \operatorname{Nul}(A^\top\!\! A )$. This proves, \[ \mathbf{x} \in \operatorname{Nul}(A) \quad \Rightarrow \quad \mathbf{x} \in \operatorname{Nul}(A^\top\!\! A ). \] Now we prove the converse, \[ \tag{*} \mathbf{x} \in \operatorname{Nul}(A^\top\!\! A ) \quad \Rightarrow \quad \mathbf{x} \in \operatorname{Nul}(A). \] Assume, $\mathbf{x} \in \operatorname{Nul}(A^\top\!\! A )$. Then, $A^\top\!\!A \mathbf{x} = \mathbf{0}$. Multiplying the last equality by $\mathbf{x}^\top$ we get $\mathbf{x}^\top\! (A^\top\!\! A \mathbf{x}) = 0$. Using the associativity of the matrix multiplication we obtain $(\mathbf{x}^\top\!\! A^\top)A \mathbf{x} = 0$. Using the Linear Algebra with the transpose operation we get $(A \mathbf{x})^\top\!A \mathbf{x} = 0$. Now recall that for every vector $\mathbf{v}$ we have $\mathbf{v}^\top \mathbf{v} = \|\mathbf{v}\|^2$. Thus, we have proved that $\|A\mathbf{x}\|^2 = 0$. Now recall that the only vector whose norm is $0$ is the zero vector, to conclude that $A\mathbf{x} = \mathbf{0}$. This means $\mathbf{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 demonstrate 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$.
-
Next I will state the $QR$ factorization of a matrix with linearly independent columns as a theorem.
Theorem. Every $n\times m$ matrix $A$ with linearly independent columns can be written as a product $A = QR$ where $Q$ is an $n\times m$ matrix whose columns form an orthonormal basis for the column space of $A$ and $R$ is an $m\times m$ upper triangular invertible matrix with positive entries on its diagonal.
- The $QR$ factorization of a matrix is just the Gram-Schmidt orthogonalization process for the columns of $A$ written in matrix form. The only difference is that a Gram-Schmidt orthogonalization process produces orthogonal vectors which we have to normalize to obtain the matrix $Q$ with orthonormal columns. A nice simple example is given by the $3\!\times\!2$ matrix \[ A = \left[ \begin{array}{rr} 1 & 1 \\[2pt] 2 & 4 \\[2pt] 2 & 3 \end{array}\right]. \] Denote the columns of $A$ by $\mathbf{a}_1$ and $\mathbf{a}_2$. The Gram-Schmidt orthogonalization of the vectors $\mathbf{a}_1$ and $\mathbf{a}_2$ leads to vectors \[ \mathbf{v}_1 = \left[ \begin{array}{r} 1 \\[2pt] 2 \\[2pt] 2 \end{array}\right], \quad \mathbf{v}_2 = \left[ \begin{array}{r} -2/3 \\[2pt] 2/3 \\[2pt] 1/3 \end{array}\right]. \] These vectors are calculated as \[ \tag{*} \mathbf{v}_1 = \mathbf{a}_1, \quad \mathbf{v}_2 = \mathbf{a}_2 - \frac{5}{3} \mathbf{v}_1. \] Next we normailze the vectors $\mathbf{v}_1$ and $\mathbf{v}_2$. The norm of vector $\mathbf{v}_1$ is $3$ and the norm of $\mathbf{v}_2$ is 1. Hence the following vectors are orthonormal: \[ \mathbf{u}_1 = \frac{1}{3} \left[ \begin{array}{r} 1 \\[2pt] 2 \\[2pt] 2 \end{array}\right], \quad \mathbf{u}_2 = \frac{1}{3} \left[ \begin{array}{r} -2 \\[2pt] 2 \\[2pt] 1 \end{array}\right]. \] We can rewrite equalities (*) using the vectors $\mathbf{u}_1$ and $\mathbf{u}_2$ as follows \[ \tag{**} \mathbf{a}_1 = 3\, \mathbf{u}_1 = 3\, \mathbf{u}_1 + 0\, \mathbf{u}_2, \quad \mathbf{a}_2 = \frac{5}{3} \, 3\, \mathbf{u}_1 + \mathbf{u}_2 = 5\,\mathbf{u}_1 + \mathbf{u}_2. \] In matrix form the equalities (**) can be written as \[ A = Q \left[ \begin{array}{rr} 3 & 5 \\[2pt] 0 & 1 \end{array}\right], \] where \[ Q = \frac{1}{3} \left[ \begin{array}{rr} 1 & -2 \\[2pt] 2 & 2 \\[2pt] 2 & 1 \end{array}\right] \] is a matrix with orthonormal columns and its column space is identical to the columns space of the matrix $A$. Here \[ R = \left[ \begin{array}{rr} 3 & 5 \\[2pt] 0 & 1 \end{array}\right]. \] Notice that on the diagonal of the matrix $R$ are the norms of the vectors $\mathbf{v}_1$ and $\mathbf{v}_2$ which we obtained by the Gram-Schmidt orthogonalization algorithm. Since the matrix $Q$ has orthonormal columns we have $Q^\top Q = I_2$. Therefore the matrix $R$ can be calculated as \[ R = Q^\top A. \] This might be simpler than making adjustments to the coefficients of the Gram-Schmidt orthogonalization algorithm as we did in this simple example. However, it is good to know that $R$ is closely related to those coefficients.
-
Next, I want to prove that $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.Thorem
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] \]
- We finished Section 6.3 today. As I already posted, suggested problems are: 1, 2, 4, 5, 7, 10, 11, 13, 15, 16 17, 19, 20, 21, 23
- There are two important theorems in Section 6.3: The Best Approximation Theorem (Theorem 9) and Theorem 10 which I would call Standard Matrix of an Orthogonal Projection.
-
The proof of Theorem 10 given in the book is deceptively simple. Please do understand the proof in the book. Below I will give another proof of this theorem.
Thorem
Assumptions
- AW. $\mathcal W$ is a subspace of $\mathbb R^n,$ $\mathbf u_1, \ldots, \mathbf u_m \in \mathcal W,$ and \[ \mathcal W = \operatorname{span} \{ \mathbf u_1, \ldots, \mathbf u_m \} \]
- AON. The set $\{ \mathbf u_1, \ldots, \mathbf u_m \}$ is an orthonomal set.
- SM. For every $\mathbf y \in \mathbb R^n$ we have \[ \operatorname{Proj}_{\mathcal W} \mathbf y = UU^\top \mathbf y, \] where $U = \bigl[ \mathbf u_1 \, \cdots \, \mathbf u_m \bigr].$
In the proof ot the theorem we use the following facts that have been established elsewhere.- UOC. Since AON holds, the matrix $U$ is an $n\!\times\!m$ matrix with orthonormal columns. Therefore, by Theorem 6 on page 390, we have $U^\top U = I_m.$
- TDP. Let $A$ be an $m\!\times\!n$ matrix. Then for every $\mathbf v \in \mathbb R^m$ and every $\mathbf x \in \mathbb R^n$ we have \[ \mathbf v \cdot (A \mathbf x) = \bigl(A^\top \mathbf v\bigr) \cdot \mathbf x. \]
- WCU. By AW and the definition of a column space we have $\mathcal W = \operatorname{Col} U.$
- DOP. Let $\mathbf y \in \mathbb R^n.$ By the definition of the orthogonal projection we have $\widehat{\mathbf y} = \operatorname{Proj}_{\mathcal W} \mathbf y$ if and only if \[ ( \mathbf y - \widehat{\mathbf y} ) \cdot \mathbf w = 0 \quad \text{for all} \quad \mathbf w \in \mathcal W. \]
The proof starts here.
Let $\mathbf y \in \mathbb R^n$ be arbitrary. By DOP, to prove that \[ UU^\top \mathbf y = \operatorname{Proj}_{\mathcal W} \mathbf y \] we have to prove that \[ \bigl( \mathbf y - UU^\top \mathbf y \bigr) \cdot \mathbf w = 0 \quad \text{for all} \quad \mathbf w \in \mathcal W. \] By WCU we have $\mathcal W = \operatorname{Col} U.$ Therefore the last displayed relation can be rewritten as \[ \bigl( \mathbf y - UU^\top \mathbf y \bigr) \cdot (U \mathbf a) = 0 \quad \text{for all} \quad \mathbf a \in \mathbb R^m. \] Let $\mathbf a \in \mathbb R^m$ be arbitrary and calculate \begin{alignat*}{2} \bigl( \mathbf y - UU^\top \mathbf y \bigr) \cdot (U \mathbf a) & = \mathbf y \cdot (U \mathbf a) - \bigl( UU^\top \mathbf y \bigr) \cdot (U \mathbf a) \qquad & \text{by TDP} \\ &= \bigl( U^\top \mathbf y \bigr) \cdot \mathbf a - \bigl( U^\top UU^\top \mathbf y \bigr) \cdot \mathbf a \qquad &\text{by UOC}\\ & = \bigl( U^\top \mathbf y \bigr) \cdot \mathbf a - \bigl(I_m U^\top \mathbf y \bigr) \cdot \mathbf a & \\ & = \bigl( U^\top \mathbf y \bigr) \cdot \mathbf a - \bigl( U^\top \mathbf y \bigr) \cdot \mathbf a & \\ & = 0 \end{alignat*} The first equality above follows from the distributivity of the inner product, the second equality follows from TDP and the third equality follows from UOC.
Since $\mathbf a \in \mathbb R^m$ was arbitrary the last calculation and WCU yield \[ \bigl( \mathbf y - UU^\top \mathbf y \bigr) \cdot \mathbf w = 0 \quad \text{for all} \quad \mathbf w \in \mathcal W. \] By DOP this proves that \[ \operatorname{Proj}_{\mathcal W} \mathbf y = UU^\top \mathbf y. \] The proof ends here.
- Suggested problems for Section 6.3: 1, 2, 4, 5, 7, 10, 11, 13, 15, 16 17, 19, 20, 21, 23
- Notice that the matrix $A$ in Exercise 32 in Section 6.1 is an orthogonal matrix in the terminology introduced in Section 6.2. It might be easier to write the matrix $A$ from Exercise 32 in Section 6.1 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. in Exercise 32 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 x$ using the formula $\bigl(A\mathbf x\bigr)^{\top} \bigl(A\mathbf x\bigr)$ and using the rules for the transpose operation and the formulas that you obtained for $A^{\top}A$. Similarly calculate $\bigl(A\mathbf x\bigr)^{\top} \bigl(A\mathbf y\bigr)$. In the last formulas you should work with general vectors $\mathbf x$ and $\mathbf y$ in $\mathbb R^4$, not specific vectors as they suggest in the book.
- Today we did Section 6.2. Suggested problems are: 2, 3, 5, 8, 9, 11, 13, 15, 17, 19, 21, 23, 25, 26, 27, 29.
- You need to know how to prove Theorem 4 in Section 6.2.
- 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, 32 (do this problem by hand), 33 (do this problem by hand).
- Here is a proof of the Law of Cosines and its connection to dot product.
- Here is a proof of the classical Pythagorean Theorem.
- On Tuesday I handed out Assignment 1. The assignment is due next Thursday, July 25.
- Today we did Appendix B Complex Numbers and Section 5.5. Suggested problems for Section 5.5: 1-6, 7-12, 13, 16, 17, 18, 21, 25, 26.
- I wrote my own introduction to complex numbers. In this introduction I offer an explanation for Euler's formula without using infinite series. Instead, I use differentiation rules.
- Today discussed Section 5.4. Suggested problems are: 1, 3 - 13, 17, 19 - 23, 27, 28.
-
Some interesting linear transformations of the vector space $\mathbb P_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.
- Proofs are important aspect of mathematics. Today I proved one direction of the Diagonalization Theorem. This is Theorem 5 in Section 5.3. Another proof that you need to understand and be to demonstrate your understanding is Theorem 2 in Section 5.1. Since the proof of this theorem in the book is somewhat criptic, I present a different proof of this theorem here.
- Today we reviewed Section 5.1, Section 5.2 and Section 5.3. Suggested problems for Section 5.1: 1, 3, 4, 5, 6, 8, 11, 15, 16, 17, 19, 20, 24-27, 29, 30, 31; for Section 5.2 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; for Section 5.3 are 2, 3, 5, 8, 9, 12, 13, 16, 18, 20, 23, 24.
- 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.
|
|
|
|
|
|
|
|
- Find the eigenvalues and the corresponding eigenspaces of the matrix \[ \left[ \begin{array}{cccc} 0 & 0 & -1 & -1 \\ -1 & 0 & 0 & 0 \\ 2 & 1 & 2 & 1 \\ -2 & -1 & -1 & 0 \end{array} \right] \] Is this matrix diagonalizable?
-
Problem 17 in Section 4.7 (which is based on Problem 38 in Section 4.3 and Problem 34 in Section 4.5) deals with the change-of-coordinates matrices in a vector space of functions. 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 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. In the book these trigonometric identities are just stated. I will prove them 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$. 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\}.$ -
Another remarkable fact about the functions $\mathbf x_0, \mathbf x_1, \mathbf x_2, \mathbf x_3, \mathbf x_4, \mathbf x_5, \mathbf x_{6}$ is that they are linearly independent. You are asked to prove this in Problem 38 in Section 4.3.
Here is a proof.
We will prove that the only linear combination of the functions $\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. - Since the vectors $\mathbf x_0, \mathbf x_1, \mathbf x_2, \mathbf x_3,\mathbf x_4, \mathbf x_5, \mathbf x_{6}$ are linearly independent, the set \[ \mathcal B = \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 = \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\}. \]
- Recall that we established the following two facts: (I) The set \[ \mathcal B = \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 = \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\}. \] (II) 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. \] Since $\mathcal B$ is a basis of $\mathcal M$, 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}\!\!=\!\!\left[\!\begin{array}{r} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\!\right]\!\!, \bigl[ \mathbf y_1\!\bigr]_{\mathcal B}\!\!=\!\!\left[\!\begin{array}{r} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\!\right]\!\!, \bigl[ \mathbf y_2\!\bigr]_{\mathcal B}\!\!=\!\!\left[\!\!\begin{array}{r} -1 \\ 0 \\ 2 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\!\right]\!\!, \bigl[ \mathbf y_3\!\bigr]_{\mathcal B}\!\!=\!\!\left[\!\!\begin{array}{r} 0 \\ -3 \\ 0 \\ 4 \\ 0 \\ 0 \\ 0 \end{array}\!\right]\!\!, \bigl[ \mathbf y_4\!\bigr]_{\mathcal B}\!\!=\!\!\left[\!\!\begin{array}{r} 1 \\ 0 \\ -8 \\ 0 \\ 8 \\ 0 \\ 0 \end{array}\!\right]\!\!, \bigl[ \mathbf y_5\!\bigr]_{\mathcal B}\!\!=\!\!\left[\!\!\begin{array}{r} 0 \\ 5 \\ 0 \\ -20 \\ 0 \\ 16 \\ 0 \end{array}\!\right]\!\!, \bigl[ \mathbf y_6\!\bigr]_{\mathcal B}\!\!=\!\!\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} : \mathcal M \to \mathbb R^7$ defined by $\mathbf v \mapsto [\mathbf v]_{\mathcal B}$ where $\mathbf v$ is an arbitrary function in $\mathcal M.$ \[ \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} = \bigl[\mathbf 0\bigr]_{\mathcal B}. \] Next, recall that the coordinate mapping is linear to conclude that \[ \beta_0 \bigl[\mathbf y_0\bigr]_{\mathcal B} + \beta_1 \bigl[\mathbf y_1\bigr]_{\mathcal B}+ \beta_2 \bigl[\mathbf y_2\bigr]_{\mathcal B} + \beta_3 \bigl[\mathbf y_3\bigr]_{\mathcal B}+ \beta_4\bigl[\mathbf y_4\bigr]_{\mathcal B}+ \beta_5 \bigl[\mathbf y_5\bigr]_{\mathcal B}+ \beta_6 \bigl[\mathbf y_{6}\bigr]_{\mathcal B} = \bigl[\mathbf 0\bigr]_{\mathcal B}. \] 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 \quad \text{for all} \quad k \in\{0,1,2,3,4,5,6\}. \] 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$, $\dim \mathcal M = 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 = \{\mathbf y_0, \mathbf y_1, \mathbf y_2, \mathbf y_3, \mathbf y_4, \mathbf y_5, \mathbf y_{6}\} \] is also a basis for $\mathcal M.$ - By Theorem 15 in Section 4.7 and the previous calculations we have \[ P_{{\mathcal B} \leftarrow {\mathcal C}} = \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} \leftarrow {\mathcal B}} = \bigl(P_{{\mathcal B} \leftarrow {\mathcal C}}\bigr)^{-1},$ we have \[ P_{{\mathcal C} \leftarrow {\mathcal B}} = \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 cosines 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 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. In the book these trigonometric identities are just stated. I will prove them here.
- The information sheet
-
We will start with a review. Please review
- The definition of an abstract vector space in Section 4.1, page 217.
- The definition a linearly independent set and the definition of a basis in Section 4.3; Examples 3, 4, 5, 6 and 10; Practice Problems 1, 2, 3, Exercises 1-8 and 38.
- Section 4.4: Theorem 7 (the unique representation theorem), 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.