Advanced Linear Algebra: Are you ready?

Solution

\(L: \mathbb R^n \rightarrow \mathbb R^m \) is a linear transformation if and only if it satisfies the conditions

1. If \(\alpha \in \mathbb R \) and \(x \in \mathbb R^n \text{,}\) then \(L( \alpha x ) = \alpha L( x ) \text{.}\)

   In other words, scaling a vector first and then transforming yields the same result as transforming the vector first and then scaling.

2. If \(x,y \in \mathbb R^n \text{,}\) then \(L( x + y ) = L( x + y ) \text{.}\)

   In other words, adding two vectors first and then transforming yields the same result as transforming the vectors first and then adding.

We employ a proof by 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{ arithmetic } \gt \\ \sum_{i=0}^{0-1} \alpha_i L( v_i ) . \end{array} \end{equation*}

• Inductive step:

  The Inductive Hypothesis (I.H.) assumes

  \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{.}\) So, the Inductive Hypothesis is

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

  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{.}\) In other words, we need to show that

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

  Now,

  \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{ arithmetic } \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 \\ ~~~ \Leftrightarrow ~~~~ \lt \mbox{ a linear transformation maps the zero } \mbox{vector to the zero vector } \gt \\ 0 = 0 \\ ~~~ \Leftrightarrow ~~~~ \lt \mbox{ law of identity } \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{.}\) In other words, we need to show that

  \begin{equation*} L( \sum_{i=0}^{(N+1)-1} \alpha_i v_i ) = \sum_{i=0}^{(N+1)-1} \alpha_i L( v_i ). \end{equation*}
  Now,
  \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.} \gt \\ \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*}

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

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

Relevance

This question touches on a number of concepts in mathematics and linear algebra needed to master advanced topics. These include

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

• The summation quantifier. The summation quantifier allows us to specify summation over a variable number of elements in a set that has the summation operator defined on it.

• The zero vector. The zero vector is the vector of appropriate size of all zeroes. It is denoted by \(0 \text{,}\) where the size of the vector is usually deduced from context.

• Summation over the empty range. Summation over the empty range yields zero, which in the setting of this question means the zero vector.

Through the two solutions we provide you are also exposed to proof styles that we use throughout ALAFF. Rather than making proofs as succinct as possible, we try to provide all intermediate steps, with justifications.

Resources

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