Advanced Linear Algebra: Are you ready?

Solution

This question is meant to check whether you have mastered mathematical induction.

• Base case: \(k = 0 \text{.}\)

  We need to show that \(L( \sum_{i=0}^{0-1} \alpha_i v_i ) = \sum_{i=0}^{0-1} \alpha_i L( v_i ) \text{.}\)

  \begin{equation*} \begin{array}{l} L( \sum_{i=0}^{0-1} \alpha_i v_i ) \\ ~~~ = ~~~~ \lt \mbox{ arithmetic } \gt \\ L( \sum_{i=0}^{-1} \alpha_i v_i ) \\ ~~~ = ~~~~ \lt \mbox{ summation over empty range. Here } 0 \mbox{ equals the zero vector } \gt \\ L( 0 ) \\ ~~~ = ~~~~ \lt \mbox{ a linear transformation maps } \mbox{the zero vector to a zero vector } \gt \\ 0 \\ ~~~ = ~~~~ \lt \mbox{ summation over empty range } \gt \\ \sum_{i=0}^{-1} \alpha_i L( v_i ) \\ ~~~ = ~~~~ \lt \mbox{ algebra } \gt \\ \sum_{i=0}^{0-1} \alpha_i L( v_i ) \end{array} \end{equation*}

• Inductive step: Assume the Inductive Hypothesis (I.H.):

  \begin{equation*} L( \sum_{i=0}^{k-1} \alpha_i v_i ) = \sum_{i=0}^{k-1} \alpha_i L( v_i ). \end{equation*}

  for \(k = N \) with \(N \ge 0 \text{.}\)

  Under this assumption we need to show that

  \begin{equation*} L( \sum_{i=0}^{k-1} \alpha_i v_i ) = \sum_{i=0}^{k-1} \alpha_i L( v_i ). \end{equation*}

  for \(k = N+ 1 \text{.}\)

  \begin{equation*} \begin{array}[t]{l} L( \sum_{i=0}^{(N+1)-1} \alpha_i v_i ) \\ ~~~ = ~~~~ \lt \mbox{ arithmetic } \gt \\ L( \sum_{i=0}^{N} \alpha_i v_i ) \\ ~~~ = ~~~~ \lt \mbox{ split off last term } \gt \\ L( \sum_{i=0}^{N-1} \alpha_i v_i + \alpha_N v_N ) \\ ~~~ = ~~~~ \lt L \mbox{ is a linear transformation } \gt \\ L( \sum_{i=0}^{N-1} \alpha_i v_i ) + L( \alpha_N v_N ) \\ ~~~ = ~~~~ \lt L \mbox{ is a linear transformation } \gt \\ L( \sum_{i=0}^{N-1} \alpha_i v_i ) + \alpha_N L( v_N ) \\ ~~~ = ~~~~ \lt \mbox{ I.H. } \gt \\ \sum_{i=0}^{N-1} \alpha_i L( v_i ) + \alpha_N L( v_N ) \\ ~~~ = ~~~~ \lt \mbox{ add term to summation } \gt \\ \sum_{i=0}^{N} \alpha_i L( v_i ) \\ ~~~ = ~~~~ \lt \mbox{ algebra } \gt \\ \sum_{i=0}^{(N+1)-1} \alpha_i L( v_i ) . \end{array} \end{equation*}

• By the Principle of Mathematical Induction, the result holds.

  This assertion is important, since it completes the reasoning. Alternatively, or in addition, you can state up front that you will use a proof by induction.

Alternative solution

• An alternative style of proof establishes that the expression simplifies to true via an "equivalence style" proof.

  Base case: \(k = 0 \text{.}\)

  We need to show that \(L( \sum_{i=0}^{0-1} \alpha_i v_i ) = \sum_{i=0}^{0-1} \alpha_i L( v_i ) \text{.}\)

  \begin{equation*} \begin{array}{l} L( \sum_{i=0}^{0-1} \alpha_i v_i ) = \sum_{i=0}^{0-1} \alpha_i L( v_i ) \\ ~~~ \Leftrightarrow ~~~~ \lt \mbox{ arithmetic } \gt \\ L( \sum_{i=0}^{-1} \alpha_i v_i ) = \sum_{i=0}^{-1} \alpha_i L( v_i ) \\ ~~~ \Leftrightarrow ~~~~ \lt \mbox{ summation over empty range. Here } 0 \mbox{ equals the zero vector } \gt \\ 0 = 0 \\ ~~~ \Leftrightarrow ~~~~ \lt \mbox{ law of equivalence } \gt \\ \mbox{true} \end{array} \end{equation*}

• Inductive step: Assume the Inductive Hypothesis (I.H.):

  \begin{equation*} L( \sum_{i=0}^{k-1} \alpha_i v_i ) = \sum_{i=0}^{k-1} \alpha_i L( v_i ). \end{equation*}

  for \(k = N \) with \(N \ge 0 \text{.}\)

  Under this assumption we need to show that

  \begin{equation*} L( \sum_{i=0}^{k-1} \alpha_i v_i ) = \sum_{i=0}^{k-1} \alpha_i L( v_i ). \end{equation*}

  for \(k = N+ 1 \text{.}\)

  \begin{equation*} \begin{array}[t]{l} L( \sum_{i=0}^{(N+1)-1} \alpha_i v_i ) = \sum_{i=0}^{(N+1)-1} \alpha_i L( v_i ) \\ ~~~ \Leftrightarrow ~~~~ \lt \mbox{ arithmetic } \gt \\ L( \sum_{i=0}^{N} \alpha_i v_i ) = \sum_{i=0}^{N} \alpha_i L( v_i ) \\ ~~~ \Leftrightarrow ~~~~ \lt \mbox{ split off last term } \gt \\ L( \sum_{i=0}^{N-1} \alpha_i v_i + \alpha_N v_N ) = \sum_{i=0}^{N-1} \alpha_i L( v_i ) + \alpha_N L( v_N ) \\ ~~~ \Leftrightarrow ~~~~ \lt L \mbox{ is a linear transformation } \gt \\ L( \sum_{i=0}^{N-1} \alpha_i v_i ) + L( \alpha_N v_N ) = \sum_{i=0}^{N-1} \alpha_i L( v_i ) + \alpha_N L( v_N ) \\ ~~~ \Leftrightarrow ~~~~ \lt L \mbox{ is a linear transformation } \gt \\ L( \sum_{i=0}^{N-1} \alpha_i v_i ) + \alpha_N L( v_N ) = \sum_{i=0}^{N-1} \alpha_i L( v_i ) + \alpha_N L( v_N ) \\ ~~~ \Leftrightarrow ~~~~ \lt \mbox{ substract equal term from both sides } \gt \\ L( \sum_{i=0}^{N-1} \alpha_i v_i ) = \sum_{i=0}^{N-1} \alpha_i L( v_i ) \\ ~~~ \Leftrightarrow ~~~~ \lt \mbox{ I.H.} \\ \sum_{i=0}^{N-1} \alpha_i L( v_i ) = \sum_{i=0}^{N-1} \alpha_i L( v_i ) \\ ~~~ \Leftrightarrow ~~~~ \lt \mbox{ law of equivalence } \gt \\ \mbox{true} \end{array} \end{equation*}

  Either style of proof is acceptable as may be proofs that use more informal reasoning.

• By the Principle of Mathematical Induction, the result holds.

  This assertion is important, since it completes the reasoning. Alternatively, or in addition, you can state up front that you will use a proof by induction.

Either style of proof is acceptable. Some prefer even more informal reasoning. The important thing is that a correct, convincing argument is given.

Relevance

In linear algebra, we are typically interested in establishing results for all sizes of matrices or vectors. This often involves a proof by induction.

Resources

Simple proofs by induction, using the structured proof by induction demonstrated in the solution, can be found in Week 2 of LAFF.

Alternative solution

A dot product \(x^T y \) with vectors of size \(n\) requires \(n \) multiplies and \(n-1 \) adds for \(2n-1 \) flops. A matrix-vector multiplication with an \(m \times n \) matrix requires \(m \) dot products with vectors of size \(n \text{,}\) for a total of \(m ( 2n-1) = 2mn - m\) flops.

Resources

The cost of various linear algebra operations is discussed throughout LAFF.