Applied Linear Algebra - Packet 11

Packet 11

Matrices II: Theory of Linearity

Linearity and the meaning of matrix multiplication

Matrix times vector Matrix multiplication preserves linear combinations:

$$A({\lambda }_1𝐮+{\lambda }_2𝐯)={\lambda }_1(A𝐮)+{\lambda }_2(A𝐯).$$

This also means, of course, the preservation of scaling and (thus) of zero: $A(\lambda 𝐱)=\lambda (A𝐱)$, $A\mathrm{𝟎}=\mathrm{𝟎}$.

This fact about matrix actions is not merely a convenient property, but it is part of the very essence and definition of matrices. This fact alone completely determines the formulas for matrix multiplication and matrix actions on vectors, as we see next.

Matrix action on vectors determined by linearity

Suppose that $A$ acts upon vectors and preserves linear combinations. Since it acts on vectors, there is a well-defined image of every standard basis vector ${𝐞}_1,\dots ,{𝐞}_n$. Write ${𝐚}_i=A{𝐞}_i$ for these images. Note that nothing about matrix formulas is yet involved.

Now consider any vector $𝐱$. We are able to write $𝐱$ using components in the standard basis:

$$𝐱=x_1{𝐞}_1+\cdots +x_n{𝐞}_n,$$

and therefore linearity implies:

$$\begin{array}{cc}A𝐱& =A(x_1{𝐞}_1+\cdots +x_n{𝐞}_n)\\ & =x_1(A{𝐞}_1)+\cdots +x_n(A{𝐞}_n)\\ & =x_1{𝐚}_1+\cdots +x_n{𝐚}_n.\end{array}$$

Now recall the formula for matrix $A$ acting on vector $𝐱$: the output is the linear combination of the columns of $A$ using $x_i$ as the coefficients. So, if we write ${𝐚}_1,\dots ,{𝐚}_n$ into the columns of $A$, then $A𝐱$ according to our previous formulation ($x_i$ coefficients on combos of the columns of $A$) is precisely the matrix given by linearity, when the images ${𝐚}_i$ of basis vectors ${𝐱}_i$ are recorded in the matrix columns.

In Question 04-04 we proved that matrix multiplication, as given by the formulas in Packet 04 specifically in summation notation, does satisfy linearity:

Derivation of linearity of matrix multiplication

$$\begin{array}{cc}(A({\lambda }_1𝐮+{\lambda }_2𝐯){)}_i& =\sum _{j=1}^n{a}_{ij}({\lambda }_1{u}_j+{\lambda }_2{v}_j)\\ & =\sum _{j=1}^n{a}_{ij}{\lambda }_1{u}_j+a_{ij}{\lambda }_2{v}_j\\ & =\sum _{j=1}^n{\lambda }_1(a_{ij}{u}_j)+{\lambda }_2(a_{ij}{v}_j)\\ & ={\lambda }_1\sum _{j=1}^n{a}_{ij}{u}_j+{\lambda }_2\sum _{j=1}^n{a}_{ij}{v}_j\\ & ={\lambda }_1(A𝐮{)}_i+{\lambda }_2(A𝐯{)}_i\\ & =({\lambda }_1(A𝐮)+{\lambda }_2(A𝐯){)}_i\end{array}$$

This sequence shows that the $i^{\text{th}}$ row of the vector $A({\lambda }_1𝐮+{\lambda }_2𝐯)$ agrees with the $i^{\text{th}}$ row of the vector ${\lambda }_1(A𝐮)+{\lambda }_2(A𝐯)$. Since this is true for every row $i$, the vectors must be completely the same.

Question 11-01

Finding a matrix using linearity

What is the 2x2 matrix that sends $2{𝐞}_1-2{𝐞}_2$ to $\left(\begin{array}{c}-4\\ 2\end{array}\right)$ and $-3{𝐞}_2$ to $\left(\begin{array}{c}3\\ -6\end{array}\right)$?

(Hint: first determine where ${𝐞}_1$ and ${𝐞}_2$ are sent using linearity. Then: the matrix is given by using these images as column vectors ${𝐚}_1$ and ${𝐚}_2$.)

Matrix times matrix We already have a definition of matrix multiplication as the “composition of matrix action,” namely that $(AB)𝐱=A(B𝐱)$ for all vectors $𝐱$.

Since $A$ acts linearly and $B$ acts linearly, the above definition implies that $AB$ acts linearly:

$$\begin{array}{cc}(AB)({\lambda }_1𝐮+{\lambda }_2𝐯)& =A(B({\lambda }_1𝐮+{\lambda }_2𝐯))\\ & =A({\lambda }_1(B𝐮)+{\lambda }_2(B𝐯))\\ & ={\lambda }_1(A(B𝐮))+{\lambda }_2(A(B𝐯))\\ & ={\lambda }_1((AB)𝐮)+{\lambda }_2((AB)𝐯).\end{array}$$

Therefore, by our previous reasoning, we can represent the action of $AB$ using a matrix where the $i^{\text{th}}$ column of the matrix of $AB$ is the image of ${𝐞}_i$ under this composition action:

$${(AB)}_i=(AB){𝐞}_i=A(B{𝐞}_i)=A{𝐛}_i.$$

In other words, the columns of $AB$ must be the images of the columns of $B$ under the action of $A$.

Linearity is fundamental

In summary: the idea of matrix product, and the formula for matrix product, come from the prescriptive hypothesis of linearity of matrix action. We can do many things in linear algebra by thinking and working in terms of linearity, instead of in terms of matrix formulas for actions and multiplications.

Question 11-02

Linearity and quadratic forms

Consider the function $f:{ℝ}^2\to ℝ$ given by $f\left(\begin{array}{c}x\\ y\end{array}\right)=xy$. Is this function linear? If not, is it linear in each variable separately?

Question 11-03

Dual vectors

Suppose $𝐯\in {ℝ}^n$ is some vector. Define a function $f_{𝐯}:{ℝ}^n\to ℝ$ by the formula $f_{𝐯}(𝐱)=𝐯\cdot 𝐱$. Is this function linear? If so, find a $1\times n$ matrix that represents the action of $f_{𝐯}$. This matrix is often called the dual vector of $𝐯$.

Exercise 11-01

Projection and inclusion

Suppose $p:{ℝ}^4\to {ℝ}^2$ and $i:{ℝ}^2\to {ℝ}^4$ are two linear mappings given by the formulas:

$$p:\left(\begin{array}{c}{u}_1\\ u_2\\ u_3\\ u_4\end{array}\right)\mapsto \left(\begin{array}{c}{u}_3\\ u_4\end{array}\right),i:\left(\begin{array}{c}{v}_1\\ v_2\end{array}\right)\mapsto \left(\begin{array}{c}{v}_1\\ v_2\\ 0\\ 0\end{array}\right).$$

• (a) Check that $p$ and $i$ (given by these formulas) are linear mappings.
• (b) Compute the matrices that correspond to $p$ and $i$.
• (c) Compute the matrix of the composition $i\circ p$ by evaluating the effect of this composite function upon the standard basis vectors ${𝐞}_1,\dots ,{𝐞}_4$.
• (d) Compute the same matrix by multiplying the matrix of $i$ and the matrix of $p$.
• (e) Repeat (c) and (d) for $p\circ i$. (This time you only need ${𝐞}_1,{𝐞}_2$.)

Change of basis

The previous section encourages us to think of linearity as fundamental, and the matrix formulas as secondary, derivable from linearity.

To be specific, the array of numbers that we have taken for granted as the “matrix columns” can be understood as “really” just the images ${𝐚}_i$ of the standard basis vectors ${𝐞}_i$. When a new vector is given to us in the form $x_1{𝐞}_1+\cdots +x_n{𝐞}_n$, then the action of $A$ on this vector is calculated using linearity as $x_1{𝐚}_1+\cdots +x_n{𝐚}_n$. By writing these ${𝐚}_i$ into the columns of a matrix, and putting the coefficients $(x_1,\dots ,x_n)$ into the columns of a vector, we arrive at the usual matrix-on-vector multiplication formula.

Most importantly: we do not need to know what the vectors ${𝐞}_i$ are to make sense of the rows and columns of the matrix $A$, provided we insist that the columns ${𝐚}_i$ are supposed to give the images of ${𝐞}_i$.

This fact allows us to generalize the idea of a matrix to the idea of a matrix in a basis. The coefficient columns of a matrix $A_{{ℬ}^{\prime }}$ in a basis ${ℬ}^{\prime }$ are simply the vector images of the members of the basis ${ℬ}^{\prime }$. Images of other vectors are calculated by writing them in terms of the basis ${ℬ}^{\prime }$ and then applying matrix-on-vector multiplication by $A_{{ℬ}^{\prime }}$.

Suppose we are given a specific basis ${ℬ}^{\prime }=\{{𝐟}_1,\dots ,{𝐟}_n\}$ for the space ${ℝ}^n$ that may not be the standard basis. Recall what this means: (a) that ${ℬ}^{\prime }$ is independent, and (b) that the span of ${ℬ}^{\prime }$ is all of ${ℝ}^n$. (Note: we use the prime notation because we would write $ℬ=\{{𝐞}_1,\dots ,{𝐞}_n\}$, with no prime, for the standard basis.)

Using (a) and (b), every vector $𝐱$ can be written with unique coefficients as a linear combination:

$$𝐱={\nu }_1{𝐟}_1+\cdots +{\nu }_n{𝐟}_n.$$

Now suppose we have some image vectors ${𝐠}_1,\dots ,{𝐠}_n$, meaning that $A_{{ℬ}^{\prime }}:{𝐟}_i\mapsto {𝐠}_i$ for all $i$, and let us define the matrix $A_{ℬ}^{\prime }$ using this knowledge. By linearity we calculate:

$$\begin{array}{cc}{A}_{{ℬ}^{\prime }}(𝐱)& ={\nu }_1{A}_{{ℬ}^{\prime }}({𝐟}_1)+\cdots +{\nu }_n{A}_{{ℬ}^{\prime }}({𝐟}_n)\\ & ={\nu }_1{𝐠}_1+\cdots +{\nu }_n{𝐠}_n.\end{array}$$

This is just like the formulation of the action of $A$ on $𝐱$ using the basis vectors ${𝐞}_i$ and their images ${𝐚}_i$ under $A$. So, we define the matrix $A_{{ℬ}^{\prime }}$ as having column vectors ${𝐠}_i$. This matrix is given in the basis ${ℬ}^{\prime }$ in the sense that when a given vector $𝐱$ is written with coefficients ${\nu }_1,\dots ,{\nu }_n$, the action of $A_{{ℬ}^{\prime }}$ on $𝐱$ is computed using the usual matrix-on-vector multiplication formula, but with the coefficients in $A_{{ℬ}^{\prime }}$ made of the column vectors ${𝐠}_1,\dots ,{𝐠}_n$ and the coefficients $\left(\begin{array}{c}{\nu }_1\\ ⋮\\ {\nu }_n\end{array}\right)$ for $𝐱$.

It can be helpful when writing the array $\left(\begin{array}{c}{\nu }_1\\ ⋮\\ {\nu }_n\end{array}\right)$ of coefficients of $𝐱$ to use the notation ${[𝐱]}_{{ℬ}^{\prime }}$. This notation refers to the array of numbers ${\nu }_1,\dots {\nu }_n$ that are used to write $𝐱$ as a linear combination ${\nu }_1{𝐟}_1+\cdots +{\nu }_n{𝐟}_n$ of the vectors ${𝐟}_i$ that constitute the basis ${ℬ}^{\prime }$. The brackets suggest the specific array in some non-standard basis, and of course ${ℬ}^{\prime }$ specifies that basis.

Note: some writers also use brackets for matrices in a specified basis, for example writing ${[A]}_{{ℬ}^{\prime }}$. Going even further, some authors distinguish the matrix itself (which presupposes a basis) from the underlying linear transformation that determines it (using the presupposed basis to interpret its coefficients). In our notation, we only put brackets on vectors. The symbols $A$ and $A_{{ℬ}^{\prime }}$ stand for distinct concrete matrices, but the visual relation between them serves as a reminder that $A_{{ℬ}^{\prime }}$ performs the same action as $A$ when vector components are rewritten using the basis ${ℬ}^{\prime }$.

Example

Matrix written in ${ℬ}^{\prime }$ acting on vector written in ${ℬ}^{\prime }$

Problem: The set of vectors

$${ℬ}^{\prime }=\{{𝐟}_1=\left(\begin{array}{c}1\\ -1\end{array}\right),{𝐟}_2=\left(\begin{array}{c}1\\ 1\end{array}\right)\}$$

is a basis of ${ℝ}^2$. (These vectors are independent and there are two of them, so they span all of ${ℝ}^2$.)

Consider the matrix $A=\left(\begin{array}{cc}-2& 2\\ 0& 1\end{array}\right)$ and the vector $𝐱=\left(\begin{array}{c}2\\ 4\end{array}\right)$. Compute the array ${[𝐱]}_{{ℬ}^{\prime }}$ that represents $𝐱$ in the new basis ${ℬ}^{\prime }$, and then compute $A_{{ℬ}^{\prime }}$. Calculate the image $A𝐱$ and compare this to the image $A_{{ℬ}^{\prime }}{[𝐱]}_{{ℬ}^{\prime }}$. They should agree!

Solution: First we find ${[𝐱]}_{{ℬ}^{\prime }}$. We must solve the system

$${\nu }_1\left(\begin{array}{c}1\\ -1\end{array}\right)+{\nu }_2\left(\begin{array}{c}1\\ 1\end{array}\right)=\left(\begin{array}{c}2\\ 4\end{array}\right)\text{so:}\begin{array}{cc}{\nu }_1+{\nu }_2& =2,\\ -{\nu }_1+{\nu }_2& =4.\end{array}$$

The solution is ${\nu }_2=3,{\nu }_1=-1$. Therefore ${[𝐱]}_{{ℬ}^{\prime }}=\left(\begin{array}{c}-1\\ 3\end{array}\right)$.

Next we seek $A_{{ℬ}^{\prime }}$. The columns of $A_{{ℬ}^{\prime }}$ are given by the images under $A$ of the items ${𝐟}_1$ and ${𝐟}_2$. So we compute:

$$A{𝐟}_1=\left(\begin{array}{cc}-2& 2\\ 0& 1\end{array}\right)\left(\begin{array}{c}1\\ -1\end{array}\right)=\left(\begin{array}{c}-4\\ -1\end{array}\right),A{𝐟}_2=\left(\begin{array}{cc}-2& 2\\ 0& 1\end{array}\right)\left(\begin{array}{c}1\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right).$$

Therefore we have $A_{{ℬ}^{\prime }}=\left(\begin{array}{cc}-4& 0\\ -1& 1\end{array}\right)$. This matrix sends ${𝐟}_1={\left(\begin{array}{c}1\\ 0\end{array}\right)}_{{ℬ}^{\prime }}$ to the vector $\left(\begin{array}{c}-4\\ -1\end{array}\right)$ and it sends ${𝐟}_2={\left(\begin{array}{c}0\\ 1\end{array}\right)}_{{ℬ}^{\prime }}$ to the vector $\left(\begin{array}{c}0\\ 1\end{array}\right)$.

Finally, observe on the one hand that

$$A_{{ℬ}^{\prime }}{[𝐱]}_{{ℬ}^{\prime }}=\left(\begin{array}{cc}-4& 0\\ -1& 1\end{array}\right)\left(\begin{array}{c}-1\\ 3\end{array}\right)=\left(\begin{array}{c}4\\ 4\end{array}\right),$$

while on the other hand

$$A𝐱=\left(\begin{array}{cc}-2& 2\\ 0& 1\end{array}\right)\left(\begin{array}{c}2\\ 4\end{array}\right)=\left(\begin{array}{c}-4+8\\ 0+4\end{array}\right)=\left(\begin{array}{c}4\\ 4\end{array}\right).$$

Therefore $A_{{ℬ}^{\prime }}{[𝐱]}_{{ℬ}^{\prime }}=A𝐱$ as the problem statement had anticipated.

In this example, the output $A_{{ℬ}^{\prime }}{[𝐱]}_{{ℬ}^{\prime }}=\left(\begin{array}{c}4\\ 4\end{array}\right)$ was written as a vector in the standard basis. This means it equals $4{𝐞}_1+4{𝐞}_2$. However, if we are given the input $𝐱$ in terms of the new basis ${ℬ}^{\prime }$ as $-{𝐟}_1+3{𝐟}_2$, then we may wish to represent the output also in terms of this basis; in other words we may want $[A_{{ℬ}^{\prime }}[𝐱{]}_{{ℬ}^{\prime }}{]}_{{ℬ}^{\prime }}$. In a sense, the matrix $A_{{ℬ}^{\prime }}$ has been adjusted to use the basis ${ℬ}^{\prime }$ on the input side only, but we may want a matrix that also uses the basis ${ℬ}^{\prime }$ on the output side as well.

Such a matrix would be denoted by ${}_{{ℬ}^{\prime }}{A}_{{ℬ}^{\prime }}$. This matrix operates on vectors ${[𝐱]}_{{ℬ}^{\prime }}$ that are given in terms of ${ℬ}^{\prime }$ and it produces vectors ${[𝐲]}_{{ℬ}^{\prime }}$ that are also given in terms of ${ℬ}^{\prime }$. To study ${}_{{ℬ}^{\prime }}{A}_{{ℬ}^{\prime }}$ more effectively we introduce a new concept, the matrix of a change of basis.

Matrix of change of basis

Consider the problem of finding ${\nu }_1,\dots ,{\nu }_n$, the coefficients such that $𝐱={\nu }_1{𝐟}_1+\cdots +{\nu }_n{𝐟}_n$ for some given $𝐱$. Let us write ${}_{ℬ}{T}_{{ℬ}^{\prime }}=\left(\begin{array}{cccc}{𝐟}_1& {𝐟}_2& \dots & {𝐟}_n\end{array}\right)$ for the matrix with column vectors ${𝐟}_1,\dots ,{𝐟}_n$, and called it the “transfer matrix” from basis ${ℬ}^{\prime }$, or ${}_{ℬ}{T}_{{ℬ}^{\prime }}$ for short.

Notice specifically that ${}_{ℬ}{T}_{{ℬ}^{\prime }}$ accepts the input vector $\left(\begin{array}{c}{\nu }_1\\ ⋮\\ {\nu }_n\end{array}\right)$ and (using matrix-on-vector multiplication) returns the output vector $𝐱={\phantom{}}_{ℬ}{T}_{{ℬ}^{\prime }}\left(\begin{array}{c}{\nu }_1\\ ⋮\\ {\nu }_n\end{array}\right)$ given in the standard basis. Therefore, in order to find $\left(\begin{array}{c}{\nu }_1\\ ⋮\\ {\nu }_n\end{array}\right)$, we simply need to invert ${}_{ℬ}{T}_{{ℬ}^{\prime }}$ and multiply its inverse by $𝐱$:

$$\left(\begin{array}{c}{\nu }_1\\ ⋮\\ {\nu }_n\end{array}\right)={\phantom{}}_{ℬ}{T}_{{ℬ}^{\prime }}^{-1}\left(\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right).$$

Now, because ${}_{ℬ}{T}_{{ℬ}^{\prime }}^{-1}$ changes a vector from basis $ℬ$ into a vector in basis ${ℬ}^{\prime }$, it is also fair to write:

$${}_{{ℬ}^{\prime }}{T}_{ℬ}{=}_{ℬ}{T}_{{ℬ}^{\prime }}^{-1}.$$

Using transfer or change of basis matrices, we can compute $A_{{ℬ}^{\prime }}$ just by taking a matrix product:

$$A_{{ℬ}^{\prime }}=A\cdot {\phantom{}}_{ℬ}{T}_{{ℬ}^{\prime }}.$$

The operation ${}_{ℬ}{T}_{{ℬ}^{\prime }}$ converts vectors from basis ${ℬ}^{\prime }$ into vectors in basis $ℬ$, and then we multiply those vectors by $A$. The result is the same as first computing the matrix of $A$ in the basis ${ℬ}^{\prime }$, obtaining $A_{{ℬ}^{\prime }}$, and acting by this matrix.

Finally, if we wish to put the outputs of $A_{{ℬ}^{\prime }}$ back into the basis ${ℬ}^{\prime }$, we just apply another transfer matrix:

$${}_{{ℬ}^{\prime }}{A}_{{ℬ}^{\prime }}={\phantom{}}_{{ℬ}^{\prime }}{T}_{ℬ}\cdot A_{{ℬ}^{\prime }}={\phantom{}}_{{ℬ}^{\prime }}{T}_{ℬ}\cdot A\cdot {\phantom{}}_{ℬ}{T}_{{ℬ}^{\prime }}.$$

Example

Finding ${}_{{ℬ}^{\prime }}{A}_{{ℬ}^{\prime }}$ using ‘change of basis’ transfer matrices

Problem: Find the transfer matrix of the example in the previous section and use it to calculate ${}_{{ℬ}^{\prime }}{A}_{{ℬ}^{\prime }}$.

Solution: We know that

$${}_{ℬ}{T}_{{ℬ}^{\prime }}=\left(\begin{array}{cc}{𝐟}_1& {𝐟}_2\end{array}\right)=\left(\begin{array}{cc}1& 1\\ -1& 1\end{array}\right).$$

Notice that the matrix $A_{{ℬ}^{\prime }}$ found in the example is quickly computed as the matrix product:

$$A_{{ℬ}^{\prime }}=A\cdot {\phantom{}}_{ℬ}{T}_{{ℬ}^{\prime }}=\left(\begin{array}{cc}-2& 2\\ 0& 1\end{array}\right)\left(\begin{array}{cc}1& 1\\ -1& 1\end{array}\right)=\left(\begin{array}{cc}-4& 0\\ -1& 1\end{array}\right).$$

To find the matrix ${}_{{ℬ}^{\prime }}{A}_{{ℬ}^{\prime }}$, we compute the inverse using the usual 2x2 formula for inverses:

$${}_{{ℬ}^{\prime }}{T}_{ℬ}={\phantom{}}_{ℬ}{T}_{{ℬ}^{\prime }}^{-1}={\left(\begin{array}{cc}1& 1\\ -1& 1\end{array}\right)}^{-1}=\left(\begin{array}{cc}1/2& -1/2\\ 1/2& 1/2\end{array}\right).$$

Then we can calculate ${}_{{ℬ}^{\prime }}{A}_{{ℬ}^{\prime }}$ by taking the product:

$${}_{{ℬ}^{\prime }}{A}_{{ℬ}^{\prime }}={\phantom{}}_{{ℬ}^{\prime }}{T}_{ℬ}\cdot A_{{ℬ}^{\prime }}=\left(\begin{array}{cc}1/2& -1/2\\ 1/2& 1/2\end{array}\right)\left(\begin{array}{cc}-4& 0\\ -1& 1\end{array}\right)=\left(\begin{array}{cc}\frac{-3}{2}& \frac{-1}{2}\\ \frac{-5}{2}& \frac{1}{2}\end{array}\right).$$

Example

Directly computing change of basis matrix using row reduction

Consider the following two bases:

$$ℬ=\{{𝐛}_1=\left(\begin{array}{c}7\\ 5\end{array}\right),{𝐛}_2=\left(\begin{array}{c}-3\\ -1\end{array}\right)\},𝒞=\{{𝐜}_1=\left(\begin{array}{c}1\\ -5\end{array}\right),{𝐜}_2=\left(\begin{array}{c}-2\\ 2\end{array}\right)\}.$$

Problem: Find the transfer matrices ${}_{ℬ}{T}_{𝒞}$ and ${}_{𝒞}{T}_{ℬ}$ representing change of basis.

Solution: We only need to find one, since the other will be determined as the inverse of the first. Let us start with ${}_{ℬ}{T}_{𝒞}$.

Let $B=\left(\begin{array}{cc}{𝐛}_1& {𝐛}_2\end{array}\right)$ and $C=\left(\begin{array}{cc}{𝐜}_1& {𝐜}_2\end{array}\right)$. Now suppose we have found a matrix $X$ such that $BX=C$. Then $X$ is in fact the transfer matrix ${}_{ℬ}{T}_{𝒞}$. Why? Observe that by definition, ${}_{ℬ}{T}_{𝒞}\left(\begin{array}{c}1\\ 0\end{array}\right)={[{𝐜}_1]}_{ℬ}=\left(\begin{array}{c}x\\ y\end{array}\right)$ where $x{𝐛}_1+y{𝐛}_2={𝐜}_1$, and similarly ${}_{ℬ}{T}_{𝒞}\left(\begin{array}{c}0\\ 1\end{array}\right)={[{𝐜}_2]}_{ℬ}=\left(\begin{array}{c}z\\ w\end{array}\right)$ where $z{𝐛}_1+w{𝐛}_2={𝐜}_2$. But these two equations precisely combine to the matrix equation $BX=C$, where $X=\left(\begin{array}{cc}x& z\\ y& w\end{array}\right)$.

So, we solve the equation $BX=C$ using row reduction on the augmented matrix $\left(\begin{array}{c}B|C\end{array}\right)$:

$$\begin{array}{cc}\left(\begin{array}{cc}B& C\end{array}\right)& =\left(\begin{array}{cccc}7& -3& 1& -2\\ 5& -1& -5& 2\end{array}\right)\\ & \sim \left(\begin{array}{cccc}7& -3& 1& -2\\ 0& 8/7& -40/7& 24/7\end{array}\right)\\ & \sim \left(\begin{array}{cccc}1& -3/7& 1/7& -2/7\\ 0& 1& -5& 3\end{array}\right)\\ & \sim \left(\begin{array}{cccc}1& 0& -2& 1\\ 0& 1& -5& 3\end{array}\right).\end{array}$$

It follows that ${}_{ℬ}{T}_{𝒞}=X=\left(\begin{array}{cc}-2& 1\\ -5& 3\end{array}\right)$. By computing the inverse ${}_{𝒞}{T}_{ℬ}={\phantom{}}_{ℬ}{T}_{𝒞}^{-1}$ using the $2\times 2$ formula, we have ${}_{𝒞}{T}_{ℬ}=\left(\begin{array}{cc}-3& 1\\ -5& 2\end{array}\right)$.

Exercise 11-02

Change of basis using row reduction

Find the change of basis transfer matrices between the following two bases:

$$ℬ=\{{𝐛}_1=\left(\begin{array}{c}-6\\ -1\end{array}\right),{𝐛}_2=\left(\begin{array}{c}2\\ 0\end{array}\right)\},𝒞=\{{𝐜}_1=\left(\begin{array}{c}2\\ -1\end{array}\right),{𝐜}_2=\left(\begin{array}{c}6\\ -2\end{array}\right)\}.$$

Exercise 11-03

Changing basis without knowing vectors

Assume that $ℬ=\{{𝐛}_1,{𝐛}_2,{𝐛}_3\}$ and $𝒞=\{{𝐜}_1,{𝐜}_2,{𝐜}_3\}$ are bases of ${ℝ}^3$, and that

$$\begin{array}{cc}{𝐛}_1& =4{𝐜}_1-{𝐜}_2\\ {𝐛}_2& =-{𝐜}_1+{𝐜}_2+{𝐜}_3\\ {𝐛}_3& ={𝐜}_2-2{𝐜}_3.\end{array}$$

Find the change of basis transfer matrix ${}_{𝒞}{T}_{ℬ}$, and also compute ${[𝐱]}_{𝒞}$ for the vector $𝐱=3{𝐛}_1+4{𝐛}_2+{𝐛}_3$.

Image, kernel, transpose, rank

Definitions Suppose that $A:{ℝ}^n\to {ℝ}^m$ is a matrix giving a linear transformation. (Notice that we don’t assume $n=m$.) In this section we introduce three important subspaces that are derived from $A$. These three subspaces are defined and may be referred to and used every time we have a matrix $A$ representing a linear transformation.

• The image of $A$ written $\mathrm{Im}(A)$, also called the column space or range, is the span of the columns of $A$, which is equivalent to the set of all possible outputs $𝐲=A𝐱$ for any $𝐱\in {ℝ}^n$.
• The kernel of $A$ written $\mathrm{Ker}(A)$, also called the null space and written $\mathrm{Nul}(A)$, is the set of inputs that $A$ sends to $\mathrm{𝟎}$, i.e. the set of $𝐱\in {ℝ}^n$ such that $A𝐱=\mathrm{𝟎}$.
• The co-kernel of $A$ written $\mathrm{CoKer}(A)$, also called the row space of $A$, is the span of the row vectors of $A$, which is equivalent to the image of the transpose $A^{𝖳}$. It is also equivalent to the full orthogonal complement of the kernel $\mathrm{Ker}(A)$.

For the last one, we need to define the transpose of any matrix $A$, written as $A^{𝖳}$, as the matrix which reflects $A$ across the main diagonal, swapping the roles of rows and columns.

Be aware that if $𝐯$ is a normal column vector, then its transpose ${𝐯}^{𝖳}$ is a row vector. Another way to view this: every normal column vector $𝐯\in {ℝ}^n$ is actually a $n\times 1$ matrix, while its transpose row vector ${𝐯}^{𝖳}$ is a $1\times n$ matrix.

Exercise 11-04

Transpose has ‘reversing property’

Show that ${(AB)}^{𝖳}=B^{𝖳}{A}^{𝖳}$.

Hint: You should use the summation notation for matrix products: ${(AB)}_{ij}={\sum }_{k=1}^n{a}_{i\ell }{b}_{\ell j}.$

More about co-kernels The meaning of image and kernel is clear from these definitions, but the meaning of co-kernel is less so.

If $A$ is an $m\times n$ matrix with entries $(a_{ij})$, then the row vectors of $A$ are just its rows $(a_{i1},\dots ,a_{in})$ for each $i=1,\dots ,m$. These are $1\times n$ matrices. We will use the notation ${𝐚}^1,\dots ,{𝐚}^m$ for the row vectors.

By taking transposes, we can convert these row vectors into ordinary vectors ${{𝐚}^i}^{𝖳}$. Notice that the $i^{\text{th}}$ row vector of $A$ equals the $i^{\text{th}}$ column vector of the transpose $A^{𝖳}$.

Now consider the connection between row vectors and dot products. A row vector ${𝐚}^i$, being an $1\times n$ matrix, acts upon a $n\times 1$ column vector and returns a $1\times 1$ vector, which is to say a scalar. This action is given by the formula:

$${𝐚}^i𝐱=\left(\begin{array}{ccc}{a}_{i1}& \dots & a_{in}\end{array}\right)\left(\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right)=a_{i1}{x}_1+\cdots +a_{in}{x}_n.$$

This formula is the same as taking the dot product ${{𝐚}^i}^{𝖳}\cdot 𝐱$.

By generalizing this to every row of the matrix $A$, and recalling that the multiplication $A𝐱$ gives a vector each row of which is the corresponding row of $A$ dotted with $𝐱$, we obtain the general fact that $A𝐱=\mathrm{𝟎}$ if and only if $𝐱$ is perpendicular to each of the row vectors transposed into ordinary vectors ${{𝐚}^i}^{𝖳}$:

$$A𝐱=\mathrm{𝟎}⟺{{𝐚}^i}^{𝖳}\cdot 𝐱=0\text{ for all }i=1,\dots ,n.$$

Co-kernel is the orthogonal complement of the kernel

The co-kernel of $A$ is precisely the subspace of (transposes of) vectors in ${ℝ}^n$ which are perpendicular to the kernel of $A$.

Derivation

We know that every $𝐱\in \mathrm{Ker}(A)$ is perpendicular to every (transposed) row vector of $A$. This implies that $𝐱$ is perpendicular to every vector in the span of the (transposed) row vectors of $A$. In other words, every $𝐱\in \mathrm{Ker}(A)$ is perpendicular to everything in the co-kernel of $A$.

It remains only to show that if a vector is perpendicular to every $𝐱\in \mathrm{Ker}(A)$, then the vector must be in $\mathrm{CoKer}(A)$, which is to say it must be a linear combination of (tranposed) row vectors of $A$.

Suppose that $𝐯$ is not a linear combination of the (transposed) row vectors of $A$. Then (imitating the Gram-Schmidt process) define $𝐯={𝐯}_{⟂}+{𝐯}_{\parallel }$ where ${𝐯}_{\parallel }={\mathrm{proj}}_{\text{co-kernel of }A}(𝐯)$. Then ${𝐯}_{⟂}$ is perpendicular to all rows of $A$ and thus it belongs to $\mathrm{Ker}(A)$. Furthermore, we know that ${𝐯}_{⟂}\cdot {𝐯}_{\parallel }=0$. Thus, ${𝐯}_{⟂}\cdot 𝐯={𝐯}_{⟂}\cdot {𝐯}_{⟂}\ne 0$. (We know ${𝐯}_{⟂}\ne 0$ because $𝐯$ is not in $\mathrm{CoKer}(A)$.) In conclusion, our vector $𝐯$ is not perpendicular to the specific vector ${𝐯}_{⟂}\in \mathrm{Ker}(A)$.

Reversing the logic (i.e. taking the contrapositive), we have shown that if a vector is perpendicular to every $𝐱\in \mathrm{Ker}(A)$, then it must lie in $\mathrm{CoKer}(A)$.

Co-kernel is image of transpose

Observe that $\mathrm{Im}(A^{𝖳})$ is the same as (the transpose of) $\mathrm{CoKer}(A)$:

The image of $A^{𝖳}$ is another name for the column space of $A^{𝖳}$, and columns of $A^{𝖳}$ are the same data as rows of $A$, just transposed.

Rank The rank of a matrix $A$ is defined to be the dimension of the image of $A$. This number is the same as the number of independent columns of $A$. There are two fundamental theorems about the rank of a matrix which relate this number to the dimensions of the other natural subspaces derived from $A$.

Rank-Rank Theorem

The rank of a matrix $A$ equals the rank of its transpose $A^{𝖳}$:

$$\mathrm{rank}A=\dim \mathrm{Im}(A)=\dim \mathrm{Im}(A^{𝖳})=\mathrm{rank}{A}^{𝖳}$$

Observe that $\mathrm{Im}(A^{𝖳})$ is the (transpose of the) row space of $A$. So the theorem says that the row space and the column space of $A$ always have the same number of independent vectors.

You can remember the reason for this theorem with the mnemonic:

Pivots give the independent columns and the independent rows.

Rank-Nullity Theorem

For any matrix $A:{ℝ}^n\to {ℝ}^m$, we have:

$$\dim \mathrm{Im}(A)+\dim \mathrm{Ker}(A)=n.$$

To remember this theorem, observe that ‘nullity’ refers to the dimension of the null space. To remember the reason for this theorem, we have another mnemonic:

Each of the $n$ columns is either a pivot or a free variable.

The mnemonics for these theorems point the way towards their proofs.

• For matrices in RREF, both theorems are obvious from the mnemonics. (Check this!)
• For matrices not in RREF, the key facts are:
  • (i) that row reduction is performed by left-multiplying $A$ by an invertible matrix $Q$ representing a composite sequence of invertible row operations (row-adds, row-scales, row-swaps), and
  • (ii) that the dimension of the image of $QA$ is equal to the dimension of the image of $A$ whenever $Q$ is an invertible matrix.
  • (iii) that the row space of a matrix $A$ is equal to the row space of the matrix $QA$ when $Q$ is a row reduction matrix, as in (ii).

Invertible matrices preserve subspaces

The second fact (ii) is actually much more general: multiplying by an invertible matrix preserves the dimensions of all subspaces.

This fact is not hard to prove, because invertible matrices send independent / dependent vectors to independent / dependent vectors, and thus bases to bases, and thus dimensions to dimensions.

In order to make use of these theorems, you should simply compute the RREF of a matrix and count the numbers of pivots and free variables.

Problems due 3 Apr 2024 by 12:00pm

Problem 11-01

Linearity

Suppose that ${𝐮}_1,\dots ,{𝐮}_k\in {ℝ}^n$ are vectors and that $A$ represents some linear transformation acting on ${ℝ}^n$.

• (a) Suppose we know that ${𝐮}_1,\dots ,{𝐮}_k$ are independent. Do we automatically know that $A{𝐮}_1,\dots ,A{𝐮}_k$ are independent? (Justify your answer. If false, a counterexample suffices; if true, an argument is required.)
• (b) Suppose we know that ${𝐮}_1,\dots ,{𝐮}_k$ are dependent. Do we automatically know that $A{𝐮}_1,\dots ,A{𝐮}_k$ are dependent? (Justify your answer. If false, a counterexample suffices; if true, an argument is required.)
• (c) If $\overrightarrow{\ell }(t)$ parametrizes a line passing through the origin, do we automatically know that $A\overrightarrow{\ell }$ is also a line passing through the origin? What if we know that $A$ is invertible?
• (d) If $\overrightarrow{\ell }(t)$ parametrizes a line not passing through the origin, do we automatically know that $A\overrightarrow{\ell }$ is also a line not passing through the origin? What if we know that $A$ is invertible?

Problem 11-02

Changing bases

• (a) Suppose that $ℬ=\{{𝐛}_1,{𝐛}_2,{𝐛}_3\}$ and $𝒞=\{{𝐜}_1,{𝐜}_2,{𝐜}_3\}$ are bases of $V$. Suppose that $A=\left(\begin{array}{ccc}{[{𝐜}_1]}_{ℬ}& {[{𝐜}_2]}_{ℬ}& {[{𝐜}_3]}_{ℬ}\end{array}\right)$ is the matrix with column vectors equal to ${𝐜}_1,{𝐜}_2,{𝐜}_3$ when written in the basis $ℬ$. Which of the following is satisfied by $A$? (i) $A{[𝐱]}_{ℬ}={[𝐱]}_{𝒞}$ or (ii) $A{[𝐱]}_{𝒞}={[𝐱]}_{ℬ}$. (You must justify your answer.)
• (b) Find the change of coordinates transfer matrices ${}_{𝒞}{T}_{ℬ}$ and ${}_{ℬ}{T}_{𝒞}$ between the following two bases of ${ℝ}^2$: $$ℬ=\{{𝐛}_1=\left(\begin{array}{c}-1\\ 8\end{array}\right),{𝐛}_2=\left(\begin{array}{c}1\\ -5\end{array}\right)\},𝒞=\{{𝐜}_1=\left(\begin{array}{c}1\\ 4\end{array}\right),{𝐜}_2=\left(\begin{array}{c}1\\ 1\end{array}\right)\}.$$
• (c) Assume that $ℬ=\{{𝐛}_1,{𝐛}_2,{𝐛}_3\}$ and $𝒞=\{{𝐜}_1,{𝐜}_2,{𝐜}_3\}$ are bases of $V$, and that \begin{align*} ParseError: Expected & or \\ or \cr or \end at end of input: \begin{align*}

\mathbf{b}_1&= 2\mathbf{c}_1-\mathbf{c}_2+\mathbf{c}_3\ \mathbf{b}_2&= 3\mathbf{c}_2+\mathbf{c}_3\ \mathbf{b}_3&= -3\mathbf{c}_1+2\mathbf{c}_3.\ \end{align*}

Find the change of basis transfer matrix $_\mathcal{C}T_\mathcal{B}$, and also compute $[\mathbf{x}]_\mathcal{C}$ for the vector $\mathbf{x}=\mathbf{b}_1-2\mathbf{b}_2+2\mathbf{b}_3$. ParseError: Can't use function '$' in math mode at position 42: …ransfer matrix $̲_\mathcal{C}T_\…

Problem 11-03

Rank-Rank and Rank-Nullity counting practice

Answer the following questions using the Rank-Rank and Rank-Nullity theorems. It may help to work with imaginary matrices in RREF and think about the pivots.

• (a) Suppose $A$ is $3\times 8$ with $\mathrm{rank}A=2$. What is $\dim \mathrm{Ker}(A)$ and $\dim \mathrm{CoKer}(A)$?
• (b) Suppose $A$ is $7\times 3$ with $\mathrm{rank}A=3$. What is $\dim \mathrm{Ker}(A)$ and $\dim \mathrm{CoKer}(A)$?
• (c) Suppose $A$ is $9\times 5$ with $\dim \mathrm{Ker}(A)=2$. What is $\mathrm{rank}A$ and $\dim \mathrm{CoKer}(A)$?

Problem 11-04

Bases and dimensions from row reduction

Row reduce the following matrix $A$ in order to find a basis for the row space $\mathrm{Im}(A^{𝖳})$, and another basis for the column space $\mathrm{Im}(A)$, and a third basis for the kernel $\mathrm{Ker}(A)$. By counting basis elements to determine dimensions, verify the two theorems of the section of the packet about rank.

$$A=\left(\begin{array}{ccccc}-2& -5& 8& 0& -17\\ 1& 3& -5& 1& 5\\ 3& 11& -19& 7& 1\\ 1& 7& -13& 5& -3\end{array}\right)$$

(Hint: for $\mathrm{Im}(A)$, you should determine which columns of $QA$ have pivots; the same columns of $A$ will then be independent vectors! This happens because row reduction $Q$ preserves independence / dependence relations among the column vectors of $A$.)