Linear Algebra Done Wrong Preface 2 Systems of linear equations

Chapter 1 Basic Notions

1.1. Vector spaces

A vector space $V$ is a (non-empty) collection of objects, called vectors (denoted in this book by lowercase bold letters, like $\mathbf{v}$ ), along with two operations, addition of vectors and multiplication by a number (scalar)¹¹1We need some visual distinction between vectors and other objects, so in this book we use bold lowercase letters for vectors and regular lowercase letters for numbers (scalars). In some (more advanced) books Latin letters are reserved for vectors, while Greek letters are used for scalars; in even more advanced texts any letter can be used for anything and the reader must understand from the context what each symbol means. I think it is helpful, especially for a beginner to have some visual distinction between different objects, so a bold lowercase letters will always denote a vector. And on a blackboard an arrow (like in $\vec{v}$ ) is used to identify a vector., such that the results of both operations are always in $V$ , and the following 8 properties below (the so-called axioms of a vector space) hold:

The first 4 properties deal with the addition:

1.

Commutativity: $\displaystyle\mathbf{v}+\mathbf{w}=\mathbf{w}+\mathbf{v}$ for all $\mathbf{v},\mathbf{w}\in V$ ;
2.

Associativity: $\displaystyle(\mathbf{u}+\mathbf{v})+\mathbf{w}=\mathbf{u}+(\mathbf{v}+\mathbf% {w})$ for all $\mathbf{u},\mathbf{v},\mathbf{w}\in V$ ;
3.

Zero vector: there exists a special vector, denoted by $\mathbf{0}$ such that $\displaystyle\mathbf{v}+\mathbf{0}=\mathbf{v}$ for all $\mathbf{v}\in V$ ;
4.

Additive inverse: For every vector $\mathbf{v}\in V$ there exists a vector $\mathbf{w}\in V$ such that $\mathbf{v}+\mathbf{w}=\mathbf{0}$ . Such additive inverse is usually denoted as $-\mathbf{v}$ ;

The next two properties concern multiplication:
5.

Multiplicative identity: $1\mathbf{v}=\mathbf{v}$ for all $\mathbf{v}\in V$ ;
6.

Multiplicative associativity: $(\alpha\beta)\mathbf{v}=\alpha(\beta\mathbf{v})$ for all $\mathbf{v}\in V$ and all scalars $\alpha$ , $\beta$ ;

And finally, two distributive properties, which connect multiplication and addition:
7.

$\alpha(\mathbf{u}+\mathbf{v})=\alpha\mathbf{u}+\alpha\mathbf{v}$ for all $\mathbf{u},\mathbf{v}\in V$ and all scalars $\alpha$ ;
8.

$(\alpha+\beta)\mathbf{v}=\alpha\mathbf{v}+\beta\mathbf{v}$ for all $\mathbf{v}\in V$ and all scalars $\alpha$ , $\beta$ .

Remark.

The above properties seem hard to memorize, but it is not necessary. They are simply the familiar rules of algebraic manipulations with numbers, that you know from high school. The only new twist here is that you have to understand what operations you can apply to what objects. You can add vectors, and you can multiply a vector by a number (scalar). Of course, you can do with number all possible manipulations that you have learned before. But, you cannot multiply two vectors, or add a number to a vector.

Remark.

It is easy to prove that zero vector $\mathbf{0}$ is unique, and that given $\mathbf{v}\in V$ its additive inverse $-\mathbf{v}$ is also unique.

It is also not hard to show using properties 5, 6 and 8 that $\mathbf{0}=0\mathbf{v}$ for any $\mathbf{v}\in V$ , and that $-\mathbf{v}=(-1)\mathbf{v}$ . Note, that to do this one still needs to use other properties of a vector space in the proofs, in particular properties 3 and 4.

If the scalars are the usual real numbers, we call the space $V$ a real vector space. If the scalars are the complex numbers, i.e. if we can multiply vectors by complex numbers, we call the space $V$ a complex vector space.

Note, that any complex vector space is a real vector space as well (if we can multiply by complex numbers, we can multiply by real numbers), but not the other way around.

It is also possible to consider a situation when the scalars are elements of an arbitrary field²²2If you do not know what a field is, do not worry, since in this book we consider only the case of real and complex spaces. $\mathbb{F}$ . In this case we say that $V$ is a vector space over the field $\mathbb{F}$ . Although many of the constructions in the book (in particular, everything in Chapters 1–3) work for general fields, in this text we are considering only real and complex vector spaces.

If we do not specify the set of scalars, or use a letter $\mathbb{F}$ for it, then the results are true for both real and complex spaces. If we need to distinguish real and complex cases, we will explicitly say which case we are considering.

Note, that in the definition of a vector space over an arbitrary field, we require the set of scalars to be a field, so we can always divide (without a remainder) by a non-zero scalar. Thus, it is possible to consider vector space over rationals, but not over the integers.

1.1.1. Examples.

Example.

The space $\mathbb{R}^{n}$ consists of all columns of size $n$ ,

\mathbf{v}=\left(\begin{array}[]{c}v_{1}\\ {v}_{2}\\ \vdots\\ {v}_{n}\end{array}\right)

whose entries are real numbers. Addition and multiplication are defined entrywise, i.e.

\alpha\left(\begin{array}[]{c}v_{1}\\ {v}_{2}\\ \vdots\\ {v}_{n}\end{array}\right)=\left(\begin{array}[]{c}\alpha v_{1}\\ {\alpha v}_{2}\\ \vdots\\ {\alpha v}_{n}\end{array}\right),\qquad\left(\begin{array}[]{c}v_{1}\\ {v}_{2}\\ \vdots\\ {v}_{n}\end{array}\right)+\left(\begin{array}[]{c}w_{1}\\ {w}_{2}\\ \vdots\\ {w}_{n}\end{array}\right)=\left(\begin{array}[]{c}v_{1}+w_{1}\\ v_{2}+w_{2}\\ \vdots\\ v_{n}+w_{n}\end{array}\right)

Example.

The space $\mathbb{C}^{n}$ also consists of columns of size $n$ , only the entries now are complex numbers. Addition and multiplication are defined exactly as in the case of $\mathbb{R}^{n}$ , the only difference is that we can now multiply vectors by complex numbers, i.e. $\mathbb{C}^{n}$ is a complex vector space.

Many results in this text are true for both $\mathbb{R}^{n}$ and $\mathbb{C}^{n}$ . In such cases we will use notation $\mathbb{F}^{n}$ .

Example.

The space $M_{m\times n}$ (also denoted as $M_{m,n}$ ) of $m\times n$ matrices: the addition and multiplication by scalars are defined entrywise. If we allow only real entries (and so only multiplication only by reals), then we have a real vector space; if we allow complex entries and multiplication by complex numbers, we then have a complex vector space.

Formally, we have to distinguish between between real and complex cases, i.e. to write something like $M_{m,n}^{\mathbb{R}}$ or $M_{m,n}^{\mathbb{C}}$ . However, in most situations there is no difference between real and complex case, and there is no need to specify which case we are considering. If there is a difference we say explicitly which case we are considering.

Remark.

As we mentioned above, the axioms of a vector space are just the familiar rules of algebraic manipulations with (real or complex) numbers, so if we put scalars (numbers) for the vectors, all axioms will be satisfied. Thus, the set $\mathbb{R}$ of real numbers is a real vector space, and the set $\mathbb{C}$ of complex numbers is a complex vector space.

More importantly, since in the above examples all vector operations (addition and multiplication by a scalar) are performed entrywise, for these examples the axioms of a vector space are automatically satisfied because they are satisfied for scalars (can you see why?). So, we do not have to check the axioms, we get the fact that the above examples are indeed vector spaces for free!

The same can be applied to the next example, the coefficients of the polynomials play the role of entries there.

Example.

The space $\mathbb{P}_{n}$ of polynomials of degree at most $n$ , consists of all polynomials $p$ of form

p(t)=a_{0}+a_{1}t+a_{2}t^{2}+\ldots+a_{n}t^{n},

where $t$ is the independent variable. Note, that some, or even all, coefficients $a_{k}$ can be $0$ .

In the case of real coefficients $a_{k}$ we have a real vector space, complex coefficient give us a complex vector space. Again, we will specify whether we treating real or complex case only when it is essential; otherwise everything applies to both cases.

Question: What are zero vectors in each of the above examples?

1.1.2. Matrix notation

An $m\times n$ matrix is a rectangular array with $m$ rows and $n$ columns. Elements of the array are called entries of the matrix.

It is often convenient to denote matrix entries by indexed letters: the first index denotes the number of the row, where the entry is, and the second one is the number of the column. For example

(1.1.1)

A=(a_{j,k})_{j=1,}^{m,}\,{\vphantom{)}}_{k=1}^{n}=\left(\begin{array}[]{cccc}a% _{1,1}&a_{1,2}&\ldots&a_{1,n}\\ a_{2,1}&a_{2,2}&\ldots&a_{2,n}\\ \vdots&\vdots&&\vdots\\ a_{m,1}&a_{m,2}&\ldots&a_{m,n}\end{array}\right)

is a general way to write an $m\times n$ matrix.

Very often for a matrix $A$ the entry in row number $j$ and column number $k$ is denoted by $A_{j,k}$ or $(A)_{j,k}$ , and sometimes as in example (1.1.1) above the same letter but in lowercase is used for the matrix entries.

Given a matrix $A$ , its transpose (or transposed matrix) $A^{T}$ , is defined by transforming the rows of $A$ into the columns. For example

\left(\begin{array}[]{ccc}1&2&3\\ 4&5&6\end{array}\right)^{T}=\left(\begin{array}[]{cc}1&4\\ 2&5\\ 3&6\end{array}\right).

So, the columns of $A^{T}$ are the rows of $A$ and vice versa, the rows of $A^{T}$ are the columns of $A$ .

The formal definition is as follows: $(A^{T})_{j,k}=(A)_{k,j}$ meaning that the entry of $A^{T}$ in the row number $j$ and column number $k$ equals the entry of $A$ in the row number $k$ and column number $j$ .

The transpose of a matrix has a very nice interpretation in terms of linear transformations, namely it gives the so-called adjoint transformation. We will study this in detail later, but for now transposition will be just a useful formal operation.

One of the first uses of the transpose is that we can write a column vector $\mathbf{x}\in\mathbb{F}^{n}$ (recall that $\mathbb{F}$ is $\mathbb{R}$ or $\mathbb{C}$ ) as $\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})^{T}$ . If we put the column vertically, it will use significantly more space.

Exercises.

1.1.1.

Let $\mathbf{x}=(1,2,3)^{T}$ , $\mathbf{y}=(y_{1},y_{2},y_{3})^{T}$ , $\mathbf{z}=(4,2,1)^{T}$ . Compute $2\mathbf{x}$ , $3\mathbf{y}$ , $\mathbf{x}+2\mathbf{y}-3\mathbf{z}$ .

1.1.2.

Which of the following sets (with natural addition and multiplication by a scalar) are vector spaces. Justify your answer.

a)

The set of all continuous functions on the interval $[0,1]$ ;
b)

The set of all non-negative functions on the interval $[0,1]$ ;
c)

The set of all polynomials of degree exactly $n$ ;
d)

The set of all symmetric $n\times n$ matrices, i.e. the set of matrices $A=\{a_{j,k}\}_{j,k=1}^{n}$ such that $A^{T}=A$ .

1.1.3.

True or false:

a)

Every vector space contains a zero vector;
b)

A vector space can have more than one zero vector;
c)

An $m\times n$ matrix has $m$ rows and $n$ columns;
d)

If $f$ and $g$ are polynomials of degree $n$ , then $f+g$ is also a polynomial of degree $n$ ;
e)

If $f$ and $g$ are polynomials of degree at most $n$ , then $f+g$ is also a polynomial of degree at most $n$

1.1.4.

Prove that a zero vector $\mathbf{0}$ of a vector space $V$ is unique.

1.1.5.

What matrix is the zero vector of the space $M_{2\times 3}$ ?

1.1.6.

Prove that the additive inverse, defined in Axiom 4 of a vector space is unique.

1.1.7.

Prove that $0\mathbf{v}=\mathbf{0}$ for any vector $\mathbf{v}\in V$ .

1.1.8.

Prove that for any vector $\mathbf{v}$ its additive inverse $-\mathbf{v}$ is given by $(-1)\mathbf{v}$ .

1.2. Linear combinations, bases.

Let $V$ be a vector space, and let $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{p}\in V$ be a collection of vectors. A linear combination of vectors $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{p}$ is a sum of form

\alpha_{1}\mathbf{v}_{1}+\alpha_{2}\mathbf{v}_{2}+\ldots+\alpha_{p}\mathbf{v}_% {p}=\sum_{k=1}^{p}\alpha_{k}\mathbf{v}_{k}.

Definition 1.2.1.

A system of vectors $\mathbf{v}_{1},\mathbf{v}_{2},\ldots\mathbf{v}_{n}\in V$ is called a basis (for the vector space $V$ ) if any vector $\mathbf{v}\in V$ admits a unique representation as a linear combination

\mathbf{v}=\alpha_{1}\mathbf{v}_{1}+\alpha_{2}\mathbf{v}_{2}+\ldots+\alpha_{n}% \mathbf{v}_{n}=\sum_{k=1}^{n}\alpha_{k}\mathbf{v}_{k}.

The coefficients $\alpha_{1},\alpha_{2},\ldots,\alpha_{n}$ are called coordinates of the vector $\mathbf{v}$ (in the basis, or with respect to the basis $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ ).

Another way to say that $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ is a basis is to say that for any possible choice of the right side $\mathbf{v}$ , the equation $x_{1}\mathbf{v}_{1}+x_{2}\mathbf{v}_{2}+\ldots+x_{n}\mathbf{v}_{n}=\mathbf{v}$ (with unknowns $x_{k}$ ) has a unique solution.

Before discussing any properties of bases³³3the plural for the “basis” is bases, the same as the plural for “base”, let us give a few examples, showing that such objects exist, and that it makes sense to study them.

Example 1.2.2.

In the first example the space $V$ is $\mathbb{F}^{n}$ , where $\mathbb{F}$ is either $\mathbb{R}$ or $\mathbb{C}$ . Consider vectors

\mathbf{e}_{1}=\left(\begin{array}[]{c}1\\ 0\\ 0\\ \vdots\\ 0\end{array}\right),\quad\mathbf{e}_{2}=\left(\begin{array}[]{c}0\\ 1\\ 0\\ \vdots\\ 0\end{array}\right),\quad\mathbf{e}_{3}=\left(\begin{array}[]{c}0\\ 0\\ 1\\ \vdots\\ 0\end{array}\right),\ldots,\quad\mathbf{e}_{n}=\left(\begin{array}[]{c}0\\ 0\\ 0\\ \vdots\\ 1\end{array}\right),\quad

(the vector $\mathbf{e}_{k}$ has all entries $0$ except the entry number $k$ , which is $1$ ). The system of vectors $\mathbf{e}_{1},\mathbf{e}_{2},\ldots,\mathbf{e}_{n}$ is a basis in $\mathbb{F}^{n}$ . Indeed, any vector

\mathbf{v}=\left(\begin{array}[]{c}x_{1}\\ {x}_{2}\\ \vdots\\ {x}_{n}\end{array}\right)\in\mathbb{F}^{n}

can be represented as the linear combination

\mathbf{v}=x_{1}\mathbf{e}_{1}+x_{2}\mathbf{e}_{2}+\ldots+x_{n}\mathbf{e}_{n}=% \sum_{k=1}^{n}x_{k}\mathbf{e}_{k}

and this representation is unique. The system $\mathbf{e}_{1},\mathbf{e}_{2},\ldots,\mathbf{e}_{n}\in\mathbb{F}^{n}$ is called the standard basis in $\mathbb{F}^{n}$ .

Example 1.2.3.

In this example the space is the space $\mathbb{P}_{n}$ of the polynomials of degree at most $n$ . Consider vectors (polynomials) $\mathbf{e}_{0},\mathbf{e}_{1},\mathbf{e}_{2},\ldots,\mathbf{e}_{n}\in\mathbb{P% }_{n}$ defined by

\mathbf{e}_{0}:=1,\quad\mathbf{e}_{1}:=t,\quad\mathbf{e}_{2}:=t^{2},\quad% \mathbf{e}_{3}:=t^{3},\quad\ldots,\quad\mathbf{e}_{n}:=t^{n}.

Clearly, any polynomial $p$ , $p(t)=a_{0}+a_{1}t+a_{2}t^{2}+\ldots+a_{n}t^{n}$ admits a unique representation

p=a_{0}\mathbf{e}_{0}+a_{1}\mathbf{e}_{1}+\ldots+a_{n}\mathbf{e}_{n}.

So the system $\mathbf{e}_{0},\mathbf{e}_{1},\mathbf{e}_{2},\ldots,\mathbf{e}_{n}\in\mathbb{P% }_{n}$ is a basis in $\mathbb{P}_{n}$ . We will call it the standard basis in $\mathbb{P}_{n}$ .

Remark 1.2.4.

If a vector space $V$ has a basis $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ , then any vector $\mathbf{v}$ is uniquely defined by its coefficients in the decomposition $\mathbf{v}=\sum_{k=1}^{n}\alpha_{k}\mathbf{v}_{k}$ . So, if we stack the coefficients $\alpha_{k}$ in a column, we can operate with them as if they were column vectors, i.e. as with elements of $\mathbb{F}^{n}$ (again here $\mathbb{F}$ is either $\mathbb{R}$ or $\mathbb{C}$ , but everything also works for an abstract field $\mathbb{F}$ ).

Namely, if $\mathbf{v}=\sum_{k=1}^{n}\alpha_{k}\mathbf{v}_{k}$ and $\mathbf{w}=\sum_{k=1}^{n}\beta_{k}\mathbf{v}_{k}$ , then

\mathbf{v}+\mathbf{w}=\sum_{k=1}^{n}\alpha_{k}\mathbf{v}_{k}+\sum_{k=1}^{n}% \beta_{k}\mathbf{v}_{k}=\sum_{k=1}^{n}(\alpha_{k}+\beta_{k})\mathbf{v}_{k},

i.e. to get the column of coordinates of the sum one just need to add the columns of coordinates of the summands. Similarly, to get the coordinates of $\alpha\mathbf{v}$ we need simply to multiply the column of coordinates of $\mathbf{v}$ by $\alpha$ .

This is a very important remark, that will be used throughout the book. It allows us to translate any statement about the standard column space $\mathbb{F}^{n}$ to a vector space $V$ with a basis $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$

1.2.1. Generating and linearly independent systems

The definition of a basis says that any vector admits a unique representation as a linear combination. This statement is in fact two statements, namely that the representation exists and that it is unique. Let us analyze these two statements separately.

If we only consider the existence we get the following notion

Definition 1.2.5.

A system of vectors $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{p}\in V$ is called a generating system (also a spanning system, or a complete system) in $V$ if any vector $\mathbf{v}\in V$ admits representation as a linear combination

\mathbf{v}=\alpha_{1}\mathbf{v}_{1}+\alpha_{2}\mathbf{v}_{2}+\ldots+\alpha_{p}% \mathbf{v}_{p}=\sum_{k=1}^{p}\alpha_{k}\mathbf{v}_{k}.

The only difference from the definition of a basis is that we do not assume that the representation above is unique.

The words generating, spanning and complete here are synonyms. I personally prefer the term complete, because of my operator theory background. Generating and spanning are more often used in linear algebra textbooks.

Clearly, any basis is a generating (complete) system. Also, if we have a basis, say $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ , and we add to it several vectors, say $\mathbf{v}_{n+1},\ldots,\mathbf{v}_{p}$ , then the new system will be a generating (complete) system. Indeed, we can represent any vector as a linear combination of the vectors $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ , and just ignore the new ones (by putting corresponding coefficients $\alpha_{k}=0$ ).

Now, let us turn our attention to the uniqueness. We do not want to worry about existence, so let us consider the zero vector $\mathbf{0}$ , which always admits a representation as a linear combination.

Definition.

A linear combination $\alpha_{1}\mathbf{v}_{1}+\alpha_{2}\mathbf{v}_{2}+\ldots+\alpha_{p}\mathbf{v}_% {p}$ is called trivial if $\alpha_{k}=0$ $\forall k$ .

A trivial linear combination is always (for all choices of vectors $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{p}$ ) equal to $\mathbf{0}$ , and that is probably the reason for the name.

Definition.

A system of vectors $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{p}\in V$ is called linearly independent if only the trivial linear combination ( $\sum_{k=1}^{p}\alpha_{k}\mathbf{v}_{k}$ with $\alpha_{k}=0$ $\forall k$ ) of vectors $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{p}$ equals $\mathbf{0}$ .

In other words, the system $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{p}$ is linearly independent iff the equation $x_{1}\mathbf{v}_{1}+x_{2}\mathbf{v}_{2}+\ldots+x_{p}\mathbf{v}_{p}=\mathbf{0}$ (with unknowns $x_{k}$ ) has only trivial solution $x_{1}=x_{2}=\ldots=x_{p}=0$ .

If a system is not linearly independent, it is called linearly dependent. By negating the definition of linear independence, we get the following

Definition.

A system of vectors $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{p}$ is called linearly dependent if $\mathbf{0}$ can be represented as a nontrivial linear combination, $\mathbf{0}=\sum_{k=1}^{p}\alpha_{k}\mathbf{v}_{k}$ . Non-trivial here means that at least one of the coefficient $\alpha_{k}$ is non-zero. This can be (and usually is) written as $\sum_{k=1}^{p}|\alpha_{k}|\neq 0$ .

So, restating the definition we can say, that a system is linearly dependent if and only if there exist scalars $\alpha_{1},\alpha_{2},\ldots,\alpha_{p}$ , $\sum_{k=1}^{p}|\alpha_{k}|\neq 0$ such that

\sum_{k=1}^{p}\alpha_{k}\mathbf{v}_{k}=\mathbf{0}.

An alternative definition (in terms of equations) is that a system $\mathbf{v}_{1},\linebreak\mathbf{v}_{2},\ldots,\mathbf{v}_{p}$ is linearly dependent iff the equation

x_{1}\mathbf{v}_{1}+x_{2}\mathbf{v}_{2}+\ldots+x_{p}\mathbf{v}_{p}=\mathbf{0}

(with unknowns $x_{k}$ ) has a non-trivial solution. Non-trivial, once again means that at least one of $x_{k}$ is different from $0$ , and it can be written as $\sum_{k=1}^{p}|x_{k}|\neq 0$ .

The following proposition gives an alternative description of linearly dependent systems.

Proposition 1.2.6.

A system of vectors $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{p}\in V$ is linearly dependent if and only if one of the vectors $\mathbf{v}_{k}$ can be represented as a linear combination of the other vectors,

(1.2.1)

\mathbf{v}_{k}=\sum_{\begin{subarray}{c}j=1\\ j\neq k\end{subarray}}^{p}\beta_{j}\mathbf{v}_{j}.

Proof.

Suppose the system $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{p}$ is linearly dependent. Then there exist scalars $\alpha_{k}$ , $\sum_{k=1}^{p}|\alpha_{k}|\neq 0$ such that

\alpha_{1}\mathbf{v}_{1}+\alpha_{2}\mathbf{v}_{2}+\ldots+\alpha_{p}\mathbf{v}_% {p}=\mathbf{0}.

Let $k$ be the index such that $\alpha_{k}\neq 0$ . Then, moving all terms except $\alpha_{k}\mathbf{v}_{k}$ to the right side we get

\alpha_{k}\mathbf{v}_{k}=-\sum_{\begin{subarray}{c}j=1\\ j\neq k\end{subarray}}^{p}\alpha_{j}\mathbf{v}_{j}.

Dividing both sides by $\alpha_{k}$ we get (1.2.1) with $\beta_{j}=-\alpha_{j}/\alpha_{k}$ .

On the other hand, if (1.2.1) holds, $\mathbf{0}$ can be represented as a non-trivial linear combination

\mathbf{v}_{k}-\sum_{\begin{subarray}{c}j=1\\ j\neq k\end{subarray}}^{p}\beta_{j}\mathbf{v}_{j}=\mathbf{0}.

∎

Obviously, any basis is a linearly independent system. Indeed, if a system $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ is a basis, $\mathbf{0}$ admits a unique representation

\mathbf{0}=\alpha_{1}\mathbf{v}_{1}+\alpha_{2}\mathbf{v}_{2}+\ldots+\alpha_{n}% \mathbf{v}_{n}=\sum_{k=1}^{n}\alpha_{k}\mathbf{v}_{k}.

Since the trivial linear combination always gives $\mathbf{0}$ , the trivial linear combination must be the only one giving $\mathbf{0}$ .

So, as we already discussed, if a system is a basis it is a complete (generating) and linearly independent system. The following proposition shows that the converse implication is also true.

Proposition 1.2.7.

A system of vectors $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}\in V$ is a basis if and only if it is linearly independent and complete (generating).

Proof.

We already know that a basis is always linearly independent and complete, so in one direction the proposition is already proved.

Let us prove the other direction. Suppose a system $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ is linearly independent and complete. Take an arbitrary vector $\mathbf{v}\in V$ . Since the system $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ is linearly complete (generating), $\mathbf{v}$ can be represented as

\mathbf{v}=\alpha_{1}\mathbf{v}_{1}+\alpha_{2}\mathbf{v}_{2}+\ldots+\alpha_{n}% \mathbf{v}_{n}=\sum_{k=1}^{n}\alpha_{k}\mathbf{v}_{k}.

We only need to show that this representation is unique.

Suppose $\mathbf{v}$ admits another representation

\mathbf{v}=\sum_{k=1}^{n}\widetilde{\alpha}_{k}\mathbf{v}_{k}.

Then

\sum_{k=1}^{n}(\alpha_{k}-\widetilde{\alpha}_{k})\mathbf{v}_{k}=\sum_{k=1}^{n}% \alpha_{k}\mathbf{v}_{k}-\sum_{k=1}^{n}\widetilde{\alpha}_{k}\mathbf{v}_{k}=% \mathbf{v}-\mathbf{v}=\mathbf{0}.

Since the system is linearly independent, $\alpha_{k}-\widetilde{\alpha}_{k}=0$ $\forall k$ , and thus the representation $\mathbf{v}=\alpha_{1}\mathbf{v}_{1}+\alpha_{2}\mathbf{v}_{2}+\ldots+\alpha_{n}% \mathbf{v}_{n}$ is unique. ∎

Remark.

In many textbooks a basis is defined as a complete and linearly independent system (by Proposition 1.2.7 this definition is equivalent to ours). Although this definition is more common than one presented in this text, I prefer the latter. It emphasizes the main property of a basis, namely that any vector admits a unique representation as a linear combination.

Proposition 1.2.8.

Any (finite) generating system contains a basis.

Proof.

Suppose $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{p}\in V$ is a generating (complete) set. If it is linearly independent, it is a basis, and we are done.

Suppose it is not linearly independent, i.e. it is linearly dependent. Then there exists a vector $\mathbf{v}_{k}$ which can be represented as a linear combination of the vectors $\mathbf{v}_{j}$ , $j\neq k$ .

Since $\mathbf{v}_{k}$ can be represented as a linear combination of vectors $\mathbf{v}_{j}$ , $j\neq k$ , any linear combination of vectors $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{p}$ can be represented as a linear combination of the same vectors without $\mathbf{v}_{k}$ (i.e. the vectors $\mathbf{v}_{j}$ , $1\leq j\leq p$ , $j\neq k$ ). So, if we delete the vector $\mathbf{v}_{k}$ , the new system will still be a complete one.

If the new system is linearly independent, we are done. If not, we repeat the procedure.

Repeating this procedure finitely many times we arrive to a linearly independent and complete system, because otherwise we delete all vectors and end up with an empty set.

So, any finite complete (generating) set contains a complete linearly independent subset, i.e. a basis. ∎

Exercises.

1.2.1.

Find a basis in the space of $3\times 2$ matrices $M_{3\times 2}$ .

1.2.2.

True or false:

a)

Any set containing a zero vector is linearly dependent
b)

A basis must contain $\mathbf{0}$ ;
c)

subsets of linearly dependent sets are linearly dependent;
d)

subsets of linearly independent sets are linearly independent;
e)

If $\alpha_{1}\mathbf{v}_{1}+\alpha_{2}\mathbf{v}_{2}+\ldots+\alpha_{n}\mathbf{v}_% {n}=\mathbf{0}$ then all scalars $\alpha_{k}$ are zero;

1.2.3.

Recall, that a matrix is called symmetric if $A^{T}=A$ . Write down a basis in the space of symmetric $2\times 2$ matrices (there are many possible answers). How many elements are in the basis?

1.2.4.

Write down a basis for the space of

a)

$3\times 3$ symmetric matrices;
b)

$n\times n$ symmetric matrices;
c)

$n\times n$ antisymmetric ( $A^{T}=-A$ ) matrices;

1.2.5.

Let a system of vectors $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{r}$ be linearly independent but not generating. Show that it is possible to find a vector $\mathbf{v}_{r+1}$ such that the system $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{r},\mathbf{v}_{r+1}$ is linearly independent. Hint: Take for $\mathbf{v}_{r+1}$ any vector that cannot be represented as a linear combination $\sum_{k=1}^{r}\alpha_{k}\mathbf{v}_{k}$ and show that the system $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{r},\mathbf{v}_{r+1}$ is linearly independent.

1.2.6.

Is it possible that vectors $\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3}$ are linearly dependent, but the vectors $\mathbf{w}_{1}=\mathbf{v}_{1}+\mathbf{v}_{2}$ , $\mathbf{w}_{2}=\mathbf{v}_{2}+\mathbf{v}_{3}$ and $\mathbf{w}_{3}=\mathbf{v}_{3}+\mathbf{v}_{1}$ are linearly independent?

1.3. Linear Transformations. Matrix–vector multiplication

A transformation $T$ from a set $X$ to a set $Y$ is a rule that for each argument (input) $x\in X$ assigns a value (output) $y=T(x)\in Y$ .

The set $X$ is called the domain of $T$ , and the set $Y$ is called the target space or codomain of $T$ .

We write $T:X\to Y$ to say that $T$ is a transformation with the domain $X$ and the target space $Y$ .

The words “transformation”, “transform”, “mapping”, “map”, “operator”, “function” all denote the same object.

Definition.

Let $V$ , $W$ be vector spaces (over the same field $\mathbb{F}$ ). A transformation $T:V\to W$ is called linear if

1.

$T(\mathbf{u}+\mathbf{v})=T(\mathbf{u})+T(\mathbf{v})$ $\forall\mathbf{u},\mathbf{v}\in V$ ;
2.

$T(\alpha\mathbf{v})=\alpha T(\mathbf{v})$ for all $\mathbf{v}\in V$ and for all scalars $\alpha\in\mathbb{F}$ .

Properties 1 and 2 together are equivalent to the following one:

T(\alpha\mathbf{u}+\beta\mathbf{v})=\alpha T(\mathbf{u})+\beta T(\mathbf{v})

for all $\mathbf{u},\mathbf{v}\in V$ and for all scalars $\alpha,\beta$ .

1.3.1. Examples.

You dealt with linear transformation before, may be without even suspecting it, as the examples below show.

Example.

Differentiation: Let $V=\mathbb{P}_{n}$ (the set of polynomials of degree at most $n$ ), $W=\mathbb{P}_{n-1}$ , and let $T:\mathbb{P}_{n}\to\mathbb{P}_{n-1}$ be the differentiation operator,

T(p):=p^{\prime}\qquad\forall p\in\mathbb{P}_{n}.

Since $(f+g)^{\prime}=f^{\prime}+g^{\prime}$ and $(\alpha f)^{\prime}=\alpha f^{\prime}$ , this is a linear transformation.

Example.

Rotation: in this example $V=W=\mathbb{R}^{2}$ (the usual coordinate plane), and a transformation $T_{\gamma}:\mathbb{R}^{2}\to\mathbb{R}^{2}$ takes a vector in $\mathbb{R}^{2}$ and rotates it counterclockwise by $\gamma$ radians see Fig. 1.1 below. Since $T_{\gamma}$ rotates the plane as a whole, it rotates as a whole the parallelogram used to define a sum of two vectors (parallelogram law). Therefore the property 1 of linear transformation holds. It is also easy to see that the property 2 is also true.

Example.

Reflection: in this example again $V=W=\mathbb{R}^{2}$ , and the transformation $T:\mathbb{R}^{2}\to\mathbb{R}^{2}$ is the reflection in the first coordinate axis. It can also be shown geometrically, that this transformation is linear, but we will use another way to show that.

Namely, it is easy to write a formula for $T$ ,

T\Big{(}\left(\begin{array}[]{c}x_{1}\\ x_{2}\end{array}\right)\Big{)}=\left(\begin{array}[]{c}x_{1}\\ -x_{2}\end{array}\right)

and from this formula it is easy to check that the transformation is linear.

Example.

Let us investigate linear transformations $T:\mathbb{R}\to\mathbb{R}$ . Any such transformation is given by the formula

T(x)=ax\qquad\text{where }a=T(1).

Indeed,

T(x)=T(x\times 1)=xT(1)=xa=ax.

So, any linear transformation of $\mathbb{R}$ is just a multiplication by a constant.

1.3.2. Linear transformations $\mathbb{F}^{n}\to\mathbb{F}^{m}$ . Matrix–column multiplication.

It turns out that a linear transformation $T:\mathbb{F}^{n}\to\mathbb{F}^{m}$ also can be represented as a multiplication, not by a scalar, but by a matrix.

Let us see how. Let $T:\mathbb{F}^{n}\to\mathbb{F}^{m}$ be a linear transformation. What information do we need to compute $T(\mathbf{x})$ for all vectors $\mathbf{x}\in\mathbb{F}^{n}$ ? My claim is that it is sufficient to know how $T$ acts on the standard basis $\mathbf{e}_{1},\mathbf{e}_{2},\ldots,\mathbf{e}_{n}$ of $\mathbb{F}^{n}$ . Namely, it is sufficient to know $n$ vectors in $\mathbb{F}^{m}$ (i.e. the vectors of size $m$ ),

\mathbf{a}_{1}:=T(\mathbf{e}_{1}),\quad\mathbf{a}_{2}:=T(\mathbf{e}_{2}),\quad% \ldots\ ,\quad\mathbf{a}_{n}:=T(\mathbf{e}_{n}).

Indeed, let

\mathbf{x}=\left(\begin{array}[]{c}x_{1}\\ {x}_{2}\\ \vdots\\ {x}_{n}\end{array}\right).

Then $\mathbf{x}=x_{1}\mathbf{e}_{1}+x_{2}\mathbf{e}_{2}+\ldots+x_{n}\mathbf{e}_{n}=% \sum_{k=1}^{n}x_{k}\mathbf{e}_{k}$ and

T(\mathbf{x})=T(\sum_{k=1}^{n}x_{k}\mathbf{e}_{k})=\sum_{k=1}^{n}T(x_{k}% \mathbf{e}_{k})=\sum_{k=1}^{n}x_{k}T(\mathbf{e}_{k})=\sum_{k=1}^{n}x_{k}% \mathbf{a}_{k}.

So, if we join the vectors (columns) $\mathbf{a}_{1},\mathbf{a}_{2},\ldots,\mathbf{a}_{n}$ together in a matrix $A=\left[\mathbf{a}_{1},\mathbf{a}_{2},\ldots,\mathbf{a}_{n}\right]$ ( $\mathbf{a}_{k}$ being the $k$ th column of $A$ , $k=1,2,\ldots,n$ ), this matrix contains all the information about $T$ .

Let us show how one should define the product of a matrix and a vector (column) to represent the transformation $T$ as a product, $T(\mathbf{x})=A\mathbf{x}$ . Let

A=\left(\begin{array}[]{cccc}a_{1,1}&a_{1,2}&\ldots&a_{1,n}\\ a_{2,1}&a_{2,2}&\ldots&a_{2,n}\\ \vdots&\vdots&&\vdots\\ a_{m,1}&a_{m,2}&\ldots&a_{m,n}\end{array}\right).

Recall, that the column number $k$ of $A$ is the vector $\mathbf{a}_{k}$ , i.e.

\mathbf{a}_{k}=\left(\begin{array}[]{c}a_{1,k}\\ a_{2,k}\\ \vdots\\ a_{m,k}\end{array}\right).

Then if we want $A\mathbf{x}=T(\mathbf{x})$ we get

A\mathbf{x}=\sum_{k=1}^{n}x_{k}\mathbf{a}_{k}=x_{1}\left(\begin{array}[]{c}a_{% 1,1}\\ a_{2,1}\\ \vdots\\ a_{m,1}\end{array}\right)+x_{2}\left(\begin{array}[]{c}a_{1,2}\\ a_{2,2}\\ \vdots\\ a_{m,2}\end{array}\right)+\ldots+x_{n}\left(\begin{array}[]{c}a_{1,n}\\ a_{2,n}\\ \vdots\\ a_{m,n}\end{array}\right).

So, the matrix–vector multiplication should be performed by the following column by coordinate rule:

multiply each column of the matrix by the corresponding coordinate of the vector.

Example.

\left(\begin{array}[]{ccc}1&2&3\\ 3&2&1\end{array}\right)\left(\begin{array}[]{c}1\\ 2\\ 3\end{array}\right)=1\left(\begin{array}[]{c}1\\ 3\end{array}\right)+2\left(\begin{array}[]{c}2\\ 2\end{array}\right)+3\left(\begin{array}[]{c}3\\ 1\end{array}\right)=\left(\begin{array}[]{c}14\\ 10\end{array}\right).

The “column by coordinate” rule is very well adapted for parallel computing. It will be also very important in different theoretical constructions later.

However, when doing computations manually, it is more convenient to compute the result one entry at a time. This can be expressed as the following row by column rule:

To get the entry number $k$ of the result, one need to multiply row number $k$ of the matrix by the vector, that is, if $A\mathbf{x}=\mathbf{y}$ , then $y_{k}=\sum_{j=1}^{n}a_{k,j}x_{j}$ , $k=1,2,\ldots m$ ;

here $x_{j}$ and $y_{k}$ are coordinates of the vectors $\mathbf{x}$ and $\mathbf{y}$ respectively, and $a_{j,k}$ are the entries of the matrix $A$ .

Example.

\left(\begin{array}[]{ccc}1&2&3\\ 4&5&6\end{array}\right)\left(\begin{array}[]{c}1\\ 2\\ 3\end{array}\right)=\left(\begin{array}[]{c}1\cdot 1+2\cdot 2+3\cdot 3\\ 4\cdot 1+5\cdot 2+6\cdot 3\end{array}\right)=\left(\begin{array}[]{c}14\\ 32\end{array}\right)

1.3.3. Linear transformations and generating sets.

As we discussed above, linear transformation $T$ (acting from $\mathbb{F}^{n}$ to $\mathbb{F}^{m}$ ) is completely defined by its values on the standard basis in $\mathbb{F}^{n}$ .

The fact that we consider the standard basis is not essential, one can consider any basis, even any generating (spanning) set. Namely,

A linear transformation $T:V\to W$ is completely defined by its values on a generating set (in particular by its values on a basis).

So, if $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ is a generating set (in particular, if it is a basis) in $V$ , and $T$ and $T_{1}$ are linear transformations $T,T_{1}:V\to W$ such that

T\mathbf{v}_{k}=T_{1}\mathbf{v}_{k},\qquad k=1,2,\ldots,n

then $T=T_{1}$ .

The proof of this statement is trivial and left as an exercise.

1.3.4. Conclusions.

•

To get the matrix of a linear transformation $T:\mathbb{F}^{n}\to\mathbb{F}^{m}$ one needs to join the vectors $\mathbf{a}_{k}=T\mathbf{e}_{k}$ (where $\mathbf{e}_{1},\mathbf{e}_{2},\ldots,\mathbf{e}_{n}$ is the standard basis in $\mathbb{F}^{n}$ ) into a matrix: $k$ th column of the matrix is $\mathbf{a}_{k}$ , $k=1,2,\ldots,n$ .
•

If the matrix $A$ of the linear transformation $T$ is known, then $T(\mathbf{x})$ can be found by the matrix–vector multiplication, $T(\mathbf{x})=A\mathbf{x}$ . To perform matrix–vector multiplication one can use either “column by coordinate” or “row by column” rule.

The latter seems more appropriate for manual computations. The former is well adapted for parallel computers, and will be used in different theoretical constructions.

For a linear transformation $T:\mathbb{F}^{n}\to\mathbb{F}^{m}$ , its matrix is usually denoted as $[T]$ . However, very often people do not distinguish between a linear transformation and its matrix, and use the same symbol for both. When it does not lead to confusion, we will also use the same symbol for a transformation and its matrix.

Since a linear transformation is essentially a multiplication, the notation $T\mathbf{v}$ is often used instead of $T(\mathbf{v})$ . We will also use this notation. Note that the usual order of algebraic operations apply, i.e. $T\mathbf{v}+\mathbf{u}$ means $T(\mathbf{v})+\mathbf{u}$ , not $T(\mathbf{v}+\mathbf{u})$ .

Remark.

In the matrix–vector multiplication $A\mathbf{x}$ the number of columns of the matrix $A$ matrix must coincide with the size of the vector $\mathbf{x}$ , i.e. a vector in $\mathbb{F}^{n}$ can only be multiplied by an $m\times n$ matrix.

It makes sense, since an $m\times n$ matrix defines a linear transformation $\mathbb{F}^{n}\to\mathbb{F}^{m}$ , so vector $\mathbf{x}$ must belong to $\mathbb{F}^{n}$ .

The easiest way to remember this is to remember that if performing multiplication you run out of some elements faster, then the multiplication is not defined. For example, if using the “row by column” rule you run out of row entries, but still have some unused entries in the vector, the multiplication is not defined. It is also not defined if you run out of vector’s entries, but still have unused entries in the row.

Remark.

One does not have to restrict himself to the case of $\mathbb{F}^{n}$ with standard basis: everything described in this section works for transformation between arbitrary vector spaces as long as there is a basis in the domain and in the target space. Of course, if one changes a basis, the matrix of the linear transformation will be different. This will be discussed later in Section 2.8 of Chapter 2.

Exercises.

1.3.1.

Multiply:

a)

$\displaystyle\left(\begin{array}[]{ccc}1&2&3\\ 4&5&6\end{array}\right)\left(\begin{array}[]{c}1\\ 3\\ 2\end{array}\right)$ ;
b)

$\displaystyle\left(\begin{array}[]{cc}1&2\\ 0&1\\ 2&0\end{array}\right)\left(\begin{array}[]{c}1\\ 3\end{array}\right)$ ;
c)

$\displaystyle\left(\begin{array}[]{cccc}1&2&0&0\\ 0&1&2&0\\ 0&0&1&2\\ 0&0&0&1\end{array}\right)\left(\begin{array}[]{c}1\\ 2\\ 3\\ 4\end{array}\right)$ ;
d)

$\displaystyle\left(\begin{array}[]{ccc}1&2&0\\ 0&1&2\\ 0&0&1\\ 0&0&0\end{array}\right)\left(\begin{array}[]{c}1\\ 2\\ 3\\ 4\end{array}\right)$ .

1.3.2.

Let a linear transformation in $\mathbb{R}^{2}$ be the reflection in the line $x_{1}=x_{2}$ . Find its matrix.

1.3.3.

For each linear transformation below find it matrix

a)

$T:\mathbb{R}^{2}\to\mathbb{R}^{3}$ defined by $T(x,y)^{T}=(x+2y,2x-5y,7y)^{T}$ ;
b)

$T:\mathbb{R}^{4}\to\mathbb{R}^{3}$ defined by $T(x_{1},x_{2},x_{3},x_{4})^{T}=(x_{1}+x_{2}+x_{3}+x_{4},x_{2}-x_{4},x_{1}+3x_{% 2}+6x_{4})^{T}$ ;
c)

$T:\mathbb{P}_{n}\to\mathbb{P}_{n}$ , $Tf(t)=f^{\prime}(t)$ (find the matrix with respect to the standard basis $1,t,t^{2},\ldots,t^{n}$ );
d)

$T:\mathbb{P}_{n}\to\mathbb{P}_{n}$ , $Tf(t)=2f(t)+3f^{\prime}(t)-4f^{\prime\prime}(t)$ (again with respect to the standard basis $1,t,t^{2},\ldots,t^{n}$ ).

1.3.4.

Find $3\times 3$ matrices representing the transformations of $\mathbb{R}^{3}$ which:

a)

project every vector onto $x$ - $y$ plane;
b)

reflect every vector through $x$ - $y$ plane;
c)

rotate the $x$ - $y$ plane through $30^{\circ}$ , leaving $z$ -axis alone.

1.3.5.

Let $A$ be a linear transformation. If $\mathbf{z}$ is the center of the straight interval $[\mathbf{x},\mathbf{y}]$ , show that $A\mathbf{z}$ is the center of the interval $[A\mathbf{x},A\mathbf{y}]$ . Hint: What does it mean that $\mathbf{z}$ is the center of the interval $[\mathbf{x},\mathbf{y}]$ ?

1.3.6.

The set $\mathbb{C}$ of complex numbers can be canonically identified with the space $\mathbb{R}^{2}$ by treating each $z=x+iy\in\mathbb{C}$ as a column $(x,y)^{T}\in\mathbb{R}^{2}$ .

a)

Treating $\mathbb{C}$ as a complex vector space, show that the multiplication by $\alpha=a+ib\in\mathbb{C}$ is a linear transformation in $\mathbb{C}$ . What is its matrix?
b)

Treating $\mathbb{C}$ as the real vector space $\mathbb{R}^{2}$ show that the multiplication by $\alpha=a+ib$ defines a linear transformation there. What is its matrix?
c)

Define $T(x+iy)=2x-y+i(x-3y)$ . Show that this transformation is not a linear transformation in the complex vectors space $\mathbb{C}$ , but if we treat $\mathbb{C}$ as the real vector space $\mathbb{R}^{2}$ then it is a linear transformation there (i.e. that $T$ is a real linear but not a complex linear transformation).

Find the matrix of the real linear transformation $T$ .

1.3.7.

Show that any linear transformation in $\mathbb{C}$ (treated as a complex vector space) is a multiplication by $\alpha\in\mathbb{C}$ .

1.4. Linear transformations as a vector space

What operations can we perform with linear transformations? We can always multiply a linear transformation for a scalar, i.e. if we have a linear transformation $T:V\to W$ and a scalar $\alpha$ we can define a new transformation $\alpha T$ by

(\alpha T)\mathbf{v}=\alpha(T\mathbf{v})\qquad\forall\mathbf{v}\in V.

It is easy to check that $\alpha T$ is also a linear transformation:

	$\displaystyle(\alpha T)(\alpha_{1}\mathbf{v}_{1}+\alpha_{2}\mathbf{v}_{2})$	$\displaystyle=\alpha(T(\alpha_{1}\mathbf{v}_{1}+\alpha_{2}\mathbf{v}_{2}))% \qquad\text{by the definition of }\alpha T$
		$\displaystyle=\alpha(\alpha_{1}T\mathbf{v}_{1}+\alpha_{2}T\mathbf{v}_{2})% \qquad\text{by the linearity of }T$
		$\displaystyle=\alpha_{1}\alpha T\mathbf{v}_{1}+\alpha_{2}\alpha T\mathbf{v}_{2}$
		$\displaystyle=\alpha_{1}(\alpha T)\mathbf{v}_{1}+\alpha_{2}(\alpha T)\mathbf{v% }_{2}$

If $T_{1}$ and $T_{2}$ are linear transformations with the same domain and target space ( $T_{1}:V\to W$ and $T_{2}:V\to W$ , or in short $T_{1},T_{2}:V\to W$ ), then we can add these transformations, i.e. define a new transformation $T=(T_{1}+T_{2}):V\to W$ by

(T_{1}+T_{2})\mathbf{v}=T_{1}\mathbf{v}+T_{2}\mathbf{v}\qquad\forall\mathbf{v}% \in V.

It is easy to check that the transformation $T_{1}+T_{2}$ is a linear one, one just needs to repeat the above reasoning for the linearity of $\alpha T$ .

So, if we fix vector spaces $V$ and $W$ and consider the collection of all linear transformations from $V$ to $W$ (let us denote it by $\mathcal{L}(V,W)$ ), we can define 2 operations on $\mathcal{L}(V,W)$ : multiplication by a scalar and addition. It can be easily shown that these operations satisfy the axioms of a vector space, defined in Section 1.1.

This should come as no surprise for the reader, since axioms of a vector space essentially mean that operation on vectors follow standard rules of algebra. And the operations on linear transformations are defined as to satisfy these rules!

As an illustration, let us write down a formal proof of the first distributive law (axiom 7) of a vector space. We want to show that $\alpha(T_{1}+T_{2})=\alpha T_{1}+\alpha T_{2}$ . For any $\mathbf{v}\in V$

$\displaystyle\alpha(T_{1}+T_{2})\mathbf{v}$	$\displaystyle=\alpha((T_{1}+T_{2})\mathbf{v})\qquad$	by the definition of multiplication
	$\displaystyle=\alpha(T_{1}\mathbf{v}+T_{2}\mathbf{v})$	by the definition of the sum
	$\displaystyle=\alpha T_{1}\mathbf{v}+\alpha T_{2}\mathbf{v}$	$\displaystyle\text{by Axiom 7 for }W$
	$\displaystyle=(\alpha T_{1}+\alpha T_{2})\mathbf{v}$	by the definition of the sum

So indeed $\alpha(T_{1}+T_{2})=\alpha T_{1}+\alpha T_{2}$ .

Remark.

Linear operations (addition and multiplication by a scalar) on linear transformations $T:\mathbb{F}^{n}\to\mathbb{F}^{m}$ correspond to the respective operations on their matrices. Since we know that the set of $m\times n$ matrices is a vector space, this immediately implies that $\mathcal{L}(\mathbb{F}^{n},\mathbb{F}^{m})$ is a vector space.

We presented the abstract proof above, first of all because it work for general spaces, for example, for spaces without a basis, where we cannot work with coordinates. Secondly, the reasonings similar to the abstract one presented here, are used in many places, so the reader will benefit from understanding it.

And as the reader gains some mathematical sophistication, he/she will see that this abstract reasoning is indeed a very simple one, that can be performed almost automatically.

1.5. Composition of linear transformations and matrix multiplication.

1.5.1. Definition of the matrix multiplication.

Knowing matrix–vector multiplication, one can easily guess what is the natural way to define the product $AB$ of two matrices: Let us multiply by $A$ each column of $B$ (matrix-vector multiplication) and join the resulting column-vectors into a matrix. Formally,

if $\mathbf{b}_{1},\mathbf{b}_{2},\ldots,\mathbf{b}_{r}$ are the columns of $B$ , then $A\mathbf{b}_{1},A\mathbf{b}_{2},\ldots,A\mathbf{b}_{r}$ are the columns of the matrix $AB$ .

Recalling the row by column rule for the matrix–vector multiplication we get the following row by column rule for the matrices

the entry $(AB)_{j,k}$ (the entry in the row $j$ and column $k$ ) of the product $AB$ is defined by $(AB)_{j,k}=(\text{row \#}j\text{\ of }A)\cdot(\text{column \#}k\text{\ of }B)\qquad\qquad$

Formally it can be rewritten as

(AB)_{j,k}=\sum_{l}a_{j,l}b_{l,k},

if $a_{j,k}$ and $b_{j,k}$ are entries of the matrices $A$ and $B$ respectively.

I intentionally did not speak about sizes of the matrices $A$ and $B$ , but if we recall the row by column rule for the matrix–vector multiplication, we can see that in order for the multiplication to be defined, the size of a row of $A$ should be equal to the size of a column of $B$ .

In other words the product $AB$ is defined if and only if $A$ is an $m\times n$ and $B$ is $n\times r$ matrix.

1.5.2. Motivation: composition of linear transformations.

One can ask yourself here: Why are we using such a complicated rule of multiplication? Why don’t we just multiply matrices entrywise?

And the answer is, that the multiplication, as it is defined above, arises naturally from the composition of linear transformations.

Suppose we have two linear transformations, $T_{1}:\mathbb{F}^{n}\to\mathbb{F}^{m}$ and $T_{2}:\mathbb{F}^{r}\to\mathbb{F}^{n}$ . Define the composition $T=T_{1}\circ T_{2}$ of the transformations $T_{1}$ , $T_{2}$ as

T(\mathbf{x})=T_{1}(T_{2}(\mathbf{x}))\qquad\forall\mathbf{x}\in\mathbb{F}^{r}.

Note that $T_{2}(\mathbf{x})\in\mathbb{F}^{n}$ . Since $T_{1}:\mathbb{F}^{n}\to\mathbb{F}^{m}$ , the expression $T_{1}(T_{2}(\mathbf{x}))$ is well defined and the result belongs to $\mathbb{F}^{m}$ . So, $T:\mathbb{F}^{r}\to\mathbb{F}^{m}$ .

It is easy to show that $T$ is a linear transformation (exercise), so it is defined by an $m\times r$ matrix. How one can find this matrix, knowing the matrices of $T_{1}$ and $T_{2}$ ?

Remark.

We will usually identify a linear transformation and its matrix, but in the next few paragraphs we will distinguish them

Let $A$ be the matrix of $T_{1}$ and $B$ be the matrix of $T_{2}$ . As we discussed in the previous section, the columns of $T$ are vectors $T(\mathbf{e}_{1}),T(\mathbf{e}_{2}),\ldots,T(\mathbf{e}_{r})$ , where $\mathbf{e}_{1},\mathbf{e}_{2},\ldots,\mathbf{e}_{r}$ is the standard basis in $\mathbb{F}^{r}$ . For $k=1,2,\ldots,r$ we have

T(\mathbf{e}_{k})=T_{1}(T_{2}(\mathbf{e}_{k}))=T_{1}(B\mathbf{e}_{k})=T_{1}(% \mathbf{b}_{k})=A\mathbf{b}_{k}

(operators $T_{2}$ and $T_{1}$ are simply the multiplication by $B$ and $A$ respectively).

So, the columns of the matrix of $T$ are $A\mathbf{b}_{1},A\mathbf{b}_{2},\ldots,A\mathbf{b}_{r}$ , and that is exactly how the matrix $AB$ was defined!

Let us return to identifying again a linear transformation with its matrix. Since the matrix multiplication agrees with the composition, we can (and will) write $T_{1}T_{2}$ instead of $T_{1}\circ T_{2}$ and $T_{1}T_{2}\mathbf{x}$ instead of $T_{1}(T_{2}(\mathbf{x}))$ .

Remark.

Note that in the composition $T_{1}T_{2}$ the transformation $T_{2}$ is applied first! The way to remember this is to see that in $T_{1}T_{2}\mathbf{x}$ the transformation $T_{2}$ meets $\mathbf{x}$ first.

Remark.

There is another way of checking the dimensions of matrices in a product, different from the row by column rule: for a composition $T_{1}T_{2}$ to be defined it is necessary that $T_{2}\mathbf{x}$ belongs to the domain of $T_{1}$ . If $T_{2}$ acts from some space, say $\mathbb{F}^{r}$ to $\mathbb{F}^{n}$ , then $T_{1}$ must act from $\mathbb{F}^{n}$ to some space, say $\mathbb{F}^{m}$ . So, in order for $T_{1}T_{2}$ to be defined the matrices of $T_{1}$ and $T_{2}$ should be of sizes $m\times n$ and $n\times r$ respectively—the same condition as obtained from the row by column rule.

Example.

Let $T:\mathbb{R}^{2}\to\mathbb{R}^{2}$ be the reflection in the line $x_{1}=3x_{2}$ . It is a linear transformation, so let us find its matrix. To find the matrix, we need to compute $T\mathbf{e}_{1}$ and $T\mathbf{e}_{2}$ . However, the direct computation of $T\mathbf{e}_{1}$ and $T\mathbf{e}_{2}$ involves significantly more trigonometry than a sane person is willing to remember.

An easier way to find the matrix of $T$ is to represent it as a composition of simple linear transformation. Namely, let $\gamma$ be the angle between the $x_{1}$ axis and the line $x_{1}=3x_{2}$ , and let $T_{0}$ be the reflection in the $x_{1}$ -axis. Then to get the reflection $T$ we can first rotate the plane by the angle $-\gamma$ , moving the line $x_{1}=3x_{2}$ to the $x_{1}$ -axis, then reflect everything in the $x_{1}$ axis, and then rotate the plane by $\gamma$ , taking everything back. Formally it can be written as

T=R_{\gamma}T_{0}R_{-\gamma}

(note the order of terms!), where $R_{\gamma}$ is the rotation by $\gamma$ . The matrix of $T_{0}$ is easy to compute,

T_{0}=\left(\begin{array}[]{cc}1&0\\ 0&-1\end{array}\right),

the rotation matrices are known

	$\displaystyle R_{\gamma}$	$\displaystyle=\left(\begin{array}[]{cc}\cos\gamma&-\sin\gamma\\ \sin\gamma&\cos\gamma\end{array}\right),$
	$\displaystyle R_{-\gamma}$	$\displaystyle=\left(\begin{array}[]{cc}\cos(-\gamma)&-\sin(-\gamma)\\ \sin(-\gamma)&\cos(-\gamma)\end{array}\right)=\left(\begin{array}[]{cc}\cos% \gamma&\sin\gamma\\ -\sin\gamma&\cos\gamma\end{array}\right)$

To compute $\sin\gamma$ and $\cos\gamma$ take a vector in the line $x_{1}=3x_{2}$ , say a vector $(3,1)^{T}$ . Then

\cos\gamma=\frac{\text{first coordinate}}{\text{length}}=\frac{3}{\sqrt{3^{2}+% 1^{2}}}=\frac{3}{\sqrt{10}}

and similarly

\sin\gamma=\frac{\text{second coordinate}}{\text{length}}=\frac{1}{\sqrt{3^{2}% +1^{2}}}=\frac{1}{\sqrt{10}}

Gathering everything together we get

	$\displaystyle T=R_{\gamma}T_{0}R_{-\gamma}$	$\displaystyle=\frac{1}{\sqrt{10}}\left(\begin{array}[]{cc}3&-1\\ 1&3\end{array}\right)\left(\begin{array}[]{cc}1&0\\ 0&-1\end{array}\right)\frac{1}{\sqrt{10}}\left(\begin{array}[]{cc}3&1\\ -1&3\end{array}\right)$
		$\displaystyle=\frac{1}{{10}}\left(\begin{array}[]{cc}3&-1\\ 1&3\end{array}\right)\left(\begin{array}[]{cc}1&0\\ 0&-1\end{array}\right)\left(\begin{array}[]{cc}3&1\\ -1&3\end{array}\right)$

It remains only to perform matrix multiplication here to get the final result. ∎

1.5.3. Properties of matrix multiplication.

Matrix multiplication enjoys a lot of properties, familiar to us from high school algebra:

1.

Associativity: $A(BC)=(AB)C$ , provided that either left or right side is well defined; we therefore can (and will) simply write $ABC$ in this case.
2.

Distributivity: $A(B+C)=AB+AC$ , $(A+B)C=AC+BC$ , provided either left or right side of each equation is well defined.
3.

One can take scalar multiplies out: $A(\alpha B)=(\alpha A)B=\alpha(AB)=\alpha AB$ .

These properties are easy to prove. One should prove the corresponding properties for linear transformations, and they almost trivially follow from the definitions. The properties of linear transformations then imply the properties for the matrix multiplication.

The new twist here is that the commutativity fails:

matrix multiplication is non-commutative, i.e. generally for matrices $AB\neq BA$ .

One can see easily it would be unreasonable to expect the commutativity of matrix multiplication. Indeed, let $A$ and $B$ be matrices of sizes $m\times n$ and $n\times r$ respectively. Then the product $AB$ is well defined, but if $m\neq r$ , $BA$ is not defined.

Even when both products are well defined, for example, when $A$ and $B$ are $n\times n$ (square) matrices, the multiplication is still non-commutative. If we just pick the matrices $A$ and $B$ at random, the chances are that $AB\neq BA$ : we have to be very lucky to get $AB=BA$ .

1.5.4. Transposed matrices and multiplication.

Given a matrix $A$ , its transpose (or transposed matrix) $A^{T}$ is defined by transforming the rows of $A$ into the columns. For example

\left(\begin{array}[]{ccc}1&2&3\\ 4&5&6\end{array}\right)^{T}=\left(\begin{array}[]{cc}1&4\\ 2&5\\ 3&6\end{array}\right).

So, the columns of $A^{T}$ are the rows of $A$ and vice versa, the rows of $A^{T}$ are the columns of $A$ .

One of the first uses of the transpose is that we can write a column vector $\mathbf{x}\in\mathbb{F}^{n}$ as $\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})^{T}$ . If we put the column vertically, it will use significantly more space.

A simple analysis of the row by columns rule shows that

(AB)^{T}=B^{T}A^{T},

i.e. when you take the transpose of the product, you change the order of the terms.

1.5.5. Trace and matrix multiplication

For a square ( $n\times n$ ) matrix $A=(a_{j,k})$ its trace (denoted by $\operatorname{trace}A$ ) is the sum of the diagonal entries

\operatorname{trace}A=\sum_{k=1}^{n}a_{k,k}.

Theorem 1.5.1.

Let $A$ and $B$ be matrices of size $m\times n$ and $n\times m$ respectively (so the both products $AB$ and $BA$ are well defined). Then

\operatorname{trace}(AB)=\operatorname{trace}(BA)

We leave the proof of this theorem as an exercise, see Problem 1.5.6 below. There are essentially two ways of proving this theorem. One is to compute the diagonal entries of $AB$ and of $BA$ and compare their sums. This method requires some proficiency in manipulating sums in $\sum$ notation.

If you are not comfortable with algebraic manipulations, there is another way. We can consider two linear transformations, $T$ and $T_{1}$ , acting from $M_{n\times m}$ to $\mathbb{F}=\mathbb{F}^{1}$ defined by

T(X)=\operatorname{trace}(AX),\qquad T_{1}(X)=\operatorname{trace}(XA)

To prove the theorem it is sufficient to show that $T=T_{1}$ ; the equality for $X=B$ gives the theorem.

Since a linear transformation is completely defined by its values on a generating system, we need just to check the equality on some simple matrices, for example on matrices $X_{j,k}$ , which has all entries 0 except the entry $1$ in the intersection of $j$ th column and $k$ th row.

Exercises.

1.5.1.

Let

A=\left(\begin{array}[]{cc}1&2\\ 3&1\end{array}\right),\ B=\left(\begin{array}[]{ccc}1&0&2\\ 3&1&-2\end{array}\right),\ C=\left(\begin{array}[]{ccc}1&-2&3\\ -2&1&-1\end{array}\right),\ D=\left(\begin{array}[]{c}-2\\ 2\\ 1\end{array}\right)

a)

Mark all the products that are defined, and give the dimensions of the result: $AB$ , $BA$ , $ABC$ , $ABD$ , $BC$ , $BC^{T}$ , $B^{T}C$ , $DC$ , $D^{T}C^{T}$ .
b)

Compute $AB$ , $A(3B+C)$ , $B^{T}A$ , $A(BD)$ , $(AB)D$ .

1.5.2.

Let $T_{\gamma}$ be the matrix of rotation by $\gamma$ in $\mathbb{R}^{2}$ . Check by matrix multiplication that $T_{\gamma}T_{-\gamma}=T_{-\gamma}T_{\gamma}=I$

1.5.3.

Multiply two rotation matrices $T_{\alpha}$ and $T_{\beta}$ (it is a rare case when the multiplication is commutative, i.e. $T_{\alpha}T_{\beta}=T_{\beta}T_{\alpha}$ , so the order is not essential). Deduce formulas for $\sin(\alpha+\beta)$ and $\cos(\alpha+\beta)$ from here.

1.5.4.

Find the matrix of the orthogonal projection in $\mathbb{R}^{2}$ onto the line $x_{1}=-2x_{2}$ . Hint: What is the matrix of the projection onto the coordinate axis $x_{1}$ ?

1.5.5.

Find linear transformations $A,B:\mathbb{R}^{2}\to\mathbb{R}^{2}$ such that $AB=\mathbf{0}$ but $BA\neq\mathbf{0}$ .

1.5.6.

Prove Theorem 1.5.1, i.e. prove that $\operatorname{trace}(AB)=\operatorname{trace}(BA)$ .

1.5.7.

Construct a non-zero matrix $A$ such that $A^{2}=\mathbf{0}$ .

1.5.8.

Find the matrix of the reflection through the line $y=-2x/3$ . Perform all the multiplications.

1.6. Invertible transformations and matrices. Isomorphisms

1.6.1. Identity transformation and identity matrix.

Among all linear transformations, there is a special one, the identity transformation (operator) $I$ , $I\mathbf{x}=\mathbf{x}$ , $\forall\mathbf{x}$ .

To be precise, there are infinitely many identity transformations: for any vector space $V$ , there is the identity transformation $I=I_{{}_{\scriptstyle V}}:V\to V$ , $I_{{}_{\scriptstyle V}}\mathbf{x}=\mathbf{x}$ , $\forall\mathbf{x}\in V$ . However, when it is does not lead to the confusion we will use the same symbol $I$ for all identity operators (transformations). We will use the notation $I_{{}_{\scriptstyle V}}$ only we want to emphasize in what space the transformation is acting.

Clearly, if $I:\mathbb{F}^{n}\to\mathbb{F}^{n}$ is the identity transformation in $\mathbb{F}^{n}$ , its matrix is the $n\times n$ matrix

I=I_{n}=\left(\begin{array}[]{cccc}1&0&\ldots&0\\ 0&1&\ldots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\ldots&1\end{array}\right)

( $1$ on the main diagonal and $0$ everywhere else). When we want to emphasize the size of the matrix, we use the notation $I_{n}$ ; otherwise we just use $I$ .

Remark.

Often, the symbol $E$ is used in Linear Algebra textbooks for the identity matrix. I prefer $I$ , since it is used in operator theory.

Clearly, for an arbitrary linear transformation $A$ , the equalities

AI=A,\qquad IA=A

hold (whenever the product is defined).

1.6.2. Invertible transformations.

Definition.

Let $A:V\to W$ be a linear transformation. We say that the transformation $A$ is left invertible if there exist a linear transformation $B:W\to V$ such that

BA=I\qquad(I=I_{{}_{\scriptstyle V}}\text{ here}).

The transformation $A$ is called right invertible if there exists a linear transformation $C:W\to V$ such that

AC=I\qquad(\text{here }I=I_{{}_{\scriptstyle W}}).

The transformations $B$ and $C$ are called left and right inverses of $A$ . Note, that we did not assume the uniqueness of $B$ or $C$ here, and generally left and right inverses are not unique.

Definition.

A linear transformation $A:V\to W$ is called invertible if it is both right and left invertible.

Theorem 1.6.1.

If a linear transformation $A:V\to W$ is invertible, then its left and right inverses $B$ and $C$ are unique and coincide.

Corollary.

A transformation $A:V\to W$ is invertible if and only if there exists a unique linear transformation (denoted $A^{-1}$ ), $A^{-1}:W\to V$ such that

(1.6.1)

\displaystyle A^{-1}A=I_{{}_{\scriptstyle V}},\qquad AA^{-1}=I_{{}_{% \scriptstyle W}}.

The transformation $A^{-1}$ is called the inverse of $A$ .

Remark.

Very often existence of thew transformation $A^{-1}$ satisfying (1.6.1) is used as the definition of an invertible transformation.

Proof of Theorem 1.6.1.

Let $BA=I$ and $AC=I$ . Then

BAC=B(AC)=BI=B.

On the other hand

BAC=(BA)C=IC=C,

and therefore $B=C$ .

Suppose for some transformation $B_{1}$ we have $B_{1}A=I$ . Repeating the above reasoning with $B_{1}$ instead of $B$ we get $B_{1}=C$ . Therefore the left inverse $B$ is unique. The uniqueness of $C$ is proved similarly. ∎

Definition.

A matrix is called invertible (resp. left invertible, right invertible) if the corresponding linear transformation is invertible (resp. left invertible, right invertible).

Theorem 1.6.1 asserts that a matrix $A$ is invertible if there exists a unique matrix $A^{-1}$ such that $A^{-1}A=I$ , $AA^{-1}=I$ . The matrix $A^{-1}$ is called (surprise) the inverse of $A$ .

Examples.

1.

The identity transformation (matrix) is invertible, $I^{-1}=I$ ;
2.

The rotation $R_{\gamma}$

$R_{\gamma}=\left(\begin{array}[]{cc}\cos\gamma&-\sin\gamma\\ \sin\gamma&\cos\gamma\end{array}\right)$

is invertible, and the inverse is given by $(R_{\gamma})^{-1}=R_{-\gamma}$ . This equality is clear from the geometric description of $R_{\gamma}$ , and it also can be checked by the matrix multiplication;
3.

The column $(1,1)^{T}$ is left invertible but not right invertible. One of the possible left inverses in the row $(1/2,1/2)$ .

To show that this matrix is not right invertible, we just notice that there are more than one left inverse. Exercise: describe all left inverses of this matrix.
4.

The row $(1,1)$ is right invertible, but not left invertible. The column $(1/2,1/2)^{T}$ is a possible right inverse.

Remark 1.6.2.

An invertible matrix must be square ( $n\times n$ ). Moreover, if a square matrix $A$ has either left or right inverse, it is invertible. So, it is sufficient to check only one of the identities $AA^{-1}=I$ , $A^{-1}A=I$ .

This fact will be proved later. Until we prove this fact, we will not use it. I presented it here only to prevent the reader from trying wrong directions.

Properties of the inverse transformation.

Theorem 1.6.3 (Inverse of the product).

If linear transformations $A$ and $B$ are invertible (and such that the product $AB$ is defined), then the product $AB$ is invertible and

(AB)^{-1}=B^{-1}A^{-1};

note the change of the order!

Proof.

Direct computation shows:

(AB)(B^{-1}A^{-1})=A(BB^{-1})A^{-1}=AIA^{-1}=AA^{-1}=I

and similarly

(B^{-1}A^{-1})(AB)=B^{-1}(A^{-1}A)B=B^{-1}IB=B^{-1}B=I

∎

Remark 1.6.4.

The invertibility of the product $AB$ does not imply the invertibility of the factors $A$ and $B$ (can you think of an example?). However, if one of the factors (either $A$ or $B$ ) and the product $AB$ are invertible, then the second factor is also invertible.

We leave the proof of this fact as an exercise.

Theorem 1.6.5 (Inverse of $A^{T}$ ).

If a matrix $A$ is invertible, then $A^{T}$ is also invertible and

(A^{T})^{-1}=(A^{-1})^{T}

Proof.

Using $(AB)^{T}=B^{T}A^{T}$ we get

(A^{-1})^{T}A^{T}=(AA^{-1})^{T}=I^{T}=I,

and similarly

A^{T}(A^{-1})^{T}=(A^{-1}A)^{T}=I^{T}=I.

∎

And finally, if $A$ is invertible, then $A^{-1}$ is also invertible, $(A^{-1})^{-1}=A$ .

So, let us summarize the main properties of the inverse:

1.

If $A$ is invertible, then $A^{-1}$ is also invertible, $(A^{-1})^{-1}=A$ ;
2.

If $A$ and $B$ are invertible and the product $AB$ is defined, then $AB$ is invertible and $(AB)^{-1}=B^{-1}A^{-1}$ .
3.

If $A$ is invertible, then $A^{T}$ is also invertible and $(A^{T})^{-1}=(A^{-1})^{T}$ .

1.6.3. Isomorphism. Isomorphic spaces.

An invertible linear transformation $A:V\to W$ is called an isomorphism. We did not introduce anything new here, it is just another name for the object we already studied.

Two vector spaces $V$ and $W$ are called isomorphic (denoted $V\cong W$ ) if there is an isomorphism $A:V\to W$ .

Isomorphic spaces can be considered as different representation of the same space, meaning that all properties and constructions involving vector space operations are preserved under isomorphism.

The theorem below illustrates this statement.

Theorem 1.6.6.

Let $A:V\to W$ be an isomorphism, and let $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ be a basis in $V$ . Then the system $A\mathbf{v}_{1},A\mathbf{v}_{2},\ldots,A\mathbf{v}_{n}$ is a basis in $W$ .

We leave the proof of the theorem as an exercise.

Remark.

In the above theorem one can replace “basis” by “linearly independent”, or “generating”, or “linearly dependent”—all these properties are preserved under isomorphisms.

Remark.

If $A$ is an isomorphism, then so is $A^{-1}$ . Therefore in the above theorem we can state that $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ is a basis if and only if $A\mathbf{v}_{1},A\mathbf{v}_{2},\linebreak\ldots,A\mathbf{v}_{n}$ is a basis.

The converse to the Theorem 1.6.6 is also true

Theorem 1.6.7.

Let $A:V\to W$ be a linear map,and let $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ and $\mathbf{w}_{1},\mathbf{w}_{2},\ldots,\mathbf{w}_{n}$ be bases in $V$ and $W$ respectively. If $A\mathbf{v}_{k}=\mathbf{w}_{k}$ , $k=1,2,\ldots,n$ , then $A$ is an isomorphism.

Proof.

Define the inverse transformation $A^{-1}$ by $A^{-1}\mathbf{w}_{k}=\mathbf{v}_{k}$ , $k=1,\linebreak 2,\ldots,n$ (as we know, a linear transformation is defined by its values on a basis). ∎

Examples

1.

Let $A:\mathbb{F}^{n+1}\to\mathbb{P}_{n}^{\mathbb{F}}$ ( $\mathbb{P}_{n}^{\mathbb{F}}$ is the set of polynomials $\sum_{k=0}^{n}a_{k}t^{k}$ , $a_{k}\in\mathbb{F}$ of degree at most $n$ ) is defined by

$A\mathbf{e}_{1}=1,\ A\mathbf{e}_{2}=t,\ldots,A\mathbf{e}_{n}=t^{n-1},\ A% \mathbf{e}_{n+1}=t^{n}$

By Theorem 1.6.7 $A$ is an isomorphism, so $\mathbb{P}_{n}^{\mathbb{F}}\cong\mathbb{F}^{n+1}$ .
2.

Let $V$ be a vector space (over $\mathbb{F}$ ) with a basis $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ . Define transformation $A:\mathbb{F}^{n}\to V$ by

$A\mathbf{e}_{k}=\mathbf{v}_{k},\qquad k=1,2,\ldots,n,$

where $\mathbf{e}_{1},\mathbf{e}_{2},\ldots,\mathbf{e}_{n}$ is the standard basis in $\mathbb{F}^{n}$ . Again by Theorem 1.6.7 $A$ is an isomorphism, so $V\cong\mathbb{F}^{n}$ .
3.

The space $M_{2\times 3}^{\mathbb{F}}$ of $2\times 3$ matrices with entries in $\mathbb{F}$ is isomorphic to $\mathbb{F}^{6}$ ;
4.

More generally, $M_{m\times n}^{\mathbb{F}}\cong\mathbb{F}^{m\cdot n}$

Remark.

Any real vector space with a basis is isomorphic to $\mathbb{R}^{n}$ (for some $n$ ). Similarly, any complex vector space with a basis is isomorphic to $\mathbb{C}^{n}$ .

1.6.4. Invertibility and equations.

Theorem 1.6.8.

Let $A:X\to Y$ be a linear transformation. Then $A$ is invertible if and only if for any right side $\mathbf{b}\in Y$ the equation

A\mathbf{x}=\mathbf{b}

has a unique solution $\mathbf{x}\in X$ .

Proof.

Suppose $A$ is invertible. Then $\mathbf{x}=A^{-1}\mathbf{b}$ solves the equation $A\mathbf{x}=\mathbf{b}$ . To show that the solution is unique, suppose that for some other vector $\mathbf{x}_{1}\in X$

A\mathbf{x}_{1}=\mathbf{b}

Multiplying this identity by $A^{-1}$ from the left we get

A^{-1}A\mathbf{x}_{1}=A^{-1}\mathbf{b},

and therefore $\mathbf{x}_{1}=A^{-1}\mathbf{b}=\mathbf{x}$ . Note that both identities, $AA^{-1}=I$ and $A^{-1}A=I$ were used here.

Let us now suppose that the equation $A\mathbf{x}=\mathbf{b}$ has a unique solution $\mathbf{x}$ for any $\mathbf{b}\in Y$ . Let us use symbol $\mathbf{y}$ instead of $\mathbf{b}$ . We know that given $\mathbf{y}\in Y$ the equation

A\mathbf{x}=\mathbf{y}

has a unique solution $\mathbf{x}\in X$ . Let us call this solution $B(\mathbf{y})$ .

Note that $B(\mathbf{y})$ is defined for all $\mathbf{y}\in Y$ , so we defined a transformation $B:Y\to X$ .

Let us check that $B$ is a linear transformation. We need to show that $B(\alpha\mathbf{y}_{1}+\beta\mathbf{y}_{2})=\alpha B(\mathbf{y}_{1})+\beta B(% \mathbf{y}_{2})$ . Let $\mathbf{x}_{k}:=B(\mathbf{y}_{k})$ , $k=1,2$ , i.e. $A\mathbf{x}_{k}=\mathbf{y}_{k}$ , $k=1,2$ . Then

A(\alpha\mathbf{x}_{1}+\beta\mathbf{x}_{2})=\alpha A\mathbf{x}_{1}+\beta A% \mathbf{x}_{2}=\alpha\mathbf{y}_{1}+\beta\mathbf{y}_{2},

which means

B(\alpha\mathbf{y}_{1}+\beta\mathbf{y}_{2})=\alpha B(\mathbf{y}_{1})+\beta B(% \mathbf{y}_{2}).

And finally, let us show that $B$ is indeed the inverse of $A$ . Take $\mathbf{x}\in X$ and let $\mathbf{y}=A\mathbf{x}$ , so by the definition of $B$ we have $\mathbf{x}=B\mathbf{y}$ . Then for all $\mathbf{x}\in X$

BA\mathbf{x}=B\mathbf{y}=\mathbf{x},

so $BA=I$ . Similarly, for arbitrary $\mathbf{y}\in Y$ let $\mathbf{x}=B\mathbf{y}$ , so $\mathbf{y}=A\mathbf{x}$ . Then for all $\mathbf{y}\in Y$

AB\mathbf{y}=A\mathbf{x}=\mathbf{y}

so $AB=I$ . ∎

Recalling the definition of a basis we get the following corollary of Theorems 1.6.6 and 1.6.7.

Corollary 1.6.9.

An $m\times n$ matrix is invertible if and only if its columns form a basis in $\mathbb{F}^{m}$ .

Exercises.

1.6.1.

Prove, that if $A:V\to W$ is an isomorphism (i.e. an invertible linear transformation) and $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{n}$ is a basis in $V$ , then $A\mathbf{v}_{1},A\mathbf{v}_{2},\ldots,A\mathbf{v}_{n}$ is a basis in $W$ .

1.6.2.

Find all right inverses to the $1\times 2$ matrix (row) $A=(1,1)$ . Conclude from here that the row $A$ is not left invertible.

1.6.3.

Find all left inverses of the column $(1,2,3)^{T}$

1.6.4.

Is the column $(1,2,3)^{T}$ right invertible? Justify

1.6.5.

Find two matrices $A$ and $B$ that $AB$ is invertible, but $A$ and $B$ are not. Hint: square matrices $A$ and $B$ would not work. Remark: It is easy to construct such $A$ and $B$ in the case when $AB$ is a $1\times 1$ matrix (a scalar). But can you get $2\times 2$ matrix $AB$ ? $3\times 3$ ? $n\times n$ ?

1.6.6.

Suppose the product $AB$ is invertible. Show that $A$ is right invertible and $B$ is left invertible. Hint: you can just write formulas for right and left inverses.

1.6.7.

Let $A$ and $AB$ be invertible (assuming that the product $AB$ is well defined). Prove that $B$ is invertible.

1.6.8.

Let $A$ be $n\times n$ matrix. Prove that if $A^{2}=\mathbf{0}$ then $A$ is not invertible

1.6.9.

Suppose $AB=\mathbf{0}$ for some non-zero matrix $B$ . Can $A$ be invertible? Justify.

1.6.10.

Write matrices of the linear transformations $T_{1}$ and $T_{2}$ in $\mathbb{F}^{5}$ , defined as follows: $T_{1}$ interchanges the coordinates $x_{2}$ and $x_{4}$ of the vector $\mathbf{x}$ , and $T_{2}$ just adds to the coordinate $x_{2}$ $a$ times the coordinate $x_{4}$ , and does not change other coordinates, i.e.

T_{1}\left(\begin{array}[]{c}x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ x_{5}\end{array}\right)=\left(\begin{array}[]{c}x_{1}\\ x_{4}\\ x_{3}\\ x_{2}\\ x_{5}\end{array}\right),\qquad T_{2}\left(\begin{array}[]{c}x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ x_{5}\end{array}\right)=\left(\begin{array}[]{c}x_{1}\\ x_{2}+ax_{4}\\ x_{3}\\ x_{4}\\ x_{5}\end{array}\right);

here $a$ is some fixed number.

Show that $T_{1}$ and $T_{2}$ are invertible transformations, and write the matrices of the inverses. Hint: it may be simpler, if you first describe the inverse transformation, and then find its matrix, rather than trying to guess (or compute) the inverses of the matrices $T_{1}$ , $T_{2}$ .

1.6.11.

Find the matrix of the rotation in $\mathbb{R}^{3}$ through the angle $\alpha$ around the vector $(1,2,3)^{T}$ . We assume that the rotation is counterclockwise if we sit at the tip of the vector and looking at the origin.

You can present the answer as a product of several matrices: you don’t have to perform the multiplication.

1.6.12.

Give examples of matrices (say $2\times 2$ ) such that:

a)

$A+B$ is not invertible although both $A$ and $B$ are invertible;
b)

$A+B$ is invertible although both $A$ and $B$ are not invertible;
c)

All of $A$ , $B$ and $A+B$ are invertible

1.6.13.

Let $A$ be an invertible symmetric ( $A^{T}=A$ ) matrix. Is the inverse of $A$ symmetric? Justify.

1.7. Subspaces.

A subspace of a vector space $V$ is a non-empty subset $V_{0}\subset V$ of $V$ which is closed under the vector addition and multiplication by scalars, i.e.

1.

If $\mathbf{v}\in V_{0}$ then $\alpha\mathbf{v}\in V_{0}$ for all scalars $\alpha$ ;
2.

For any $\mathbf{u},\mathbf{v}\in V_{0}$ the sum $\mathbf{u}+\mathbf{v}\in V_{0}$ ;

Again, the conditions 1 and 2 can be replaced by the following one:

\alpha\mathbf{u}+\beta\mathbf{v}\in V_{0}\qquad\text{for all }\mathbf{u},% \mathbf{v}\in V_{0},\ \text{and for all scalars }\alpha,\beta.

Note, that a subspace $V_{0}\subset V$ with the operations (vector addition and multiplication by scalars) inherited from $V$ , is a vector space. Indeed, since $V$ is non-empty, it contain at least $1$ vector $\mathbf{v}$ and since $\mathbf{0}=0\mathbf{v}$ , the above condition 1. imples that the zero vector $\mathbf{0}$ is in $V$ . Also, for any $\mathbf{v}\in V$ its additive inverse $-\mathbf{v}$ in given by $-\mathbf{v}=(-1)\mathbf{v}$ , so again by property 1. $-\mathbf{v}\in V$ . The rest of the axiom of the vector space are satisfied because all operations are inherited from the vector space $V$ . The only thing that could possibly go wrong, is that the result of some operation does not belong to $V_{0}$ . But the definition of a subspace prohibits this!

Now let us consider some examples:

1.

Trivial subspaces of a space $V$ , namely $V$ itself and $\{\mathbf{0}\}$ (the subspace consisting only of zero vector). Note, that the empty set $\varnothing$ is not a vector space, since it does not contain a zero vector, so it is not a subspace.

With each linear transformation $A:V\to W$ we can associate the following two subspaces:

2.

The null space, or kernel of $A$ , which is denoted as $\operatorname{Null}A$ or $\operatorname{Ker}A$ and consists of all vectors $\mathbf{v}\in V$ such that $A\mathbf{v}=\mathbf{0}$
3.

The range $\operatorname{Ran}A$ is defined as the set of all vectors $\mathbf{w}\in W$ which can be represented as $\mathbf{w}=A\mathbf{v}$ for some $\mathbf{v}\in V$ .

If $A$ is a matrix, i.e. $A:\mathbb{F}^{m}\to\mathbb{F}^{n}$ , then recalling column by coordinate rule of the matrix–vector multiplication, we can see that any vector $\mathbf{w}\in\operatorname{Ran}A$ can be represented as a linear combination of columns of the matrix $A$ . That explains why the term column space (and notation $\operatorname{Col}A$ ) is often used for the range of the matrix. So, for a matrix $A$ , the notation $\operatorname{Col}A$ is often used instead of $\operatorname{Ran}A$ .

And now the last example.

4.

Given a system of vectors $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{r}\in V$ its linear span (sometimes called simply span) $\mathcal{L}\{\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{r}\}$ is the collection of all vectors $\mathbf{v}\in V$ that can be represented as a linear combination $\mathbf{v}=\alpha_{1}\mathbf{v}_{1}+\alpha_{2}\mathbf{v}_{2}+\ldots+\alpha_{r}% \mathbf{v}_{r}$ of vectors $\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{r}$ . The notation $\operatorname{span}\{\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{r}\}$ is also used instead of $\mathcal{L}\{\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{r}\}$

It is easy to check that in all of these examples we indeed have subspaces. We leave this an an exercise for the reader. Some of the statements will be proved later in the text.

Exercises.

1.7.1.

Let $X$ and $Y$ be subspaces of a vector space $V$ . Prove that $X\cap Y$ is a subspace of $V$ .

1.7.2.

Let $V$ be a vector space. For $X,Y\subset V$ the sum $X+Y$ is the collection of all vectors $\mathbf{v}$ which can be represented as $\mathbf{v}=\mathbf{x}+\mathbf{y}$ , $\mathbf{x}\in X$ , $\mathbf{y}\in Y$ . Show that if $X$ and $Y$ are subspaces of $V$ , then $X+Y$ is also a subspace.

1.7.3.

Let $X$ be a subspace of a vector space $V$ , and let $\mathbf{v}\in V$ , $\mathbf{v}\notin X$ . Prove that if $\mathbf{x}\in X$ then $\mathbf{x}+\mathbf{v}\notin X$ .

1.7.4.

Let $X$ and $Y$ be subspaces of a vector space $V$ . Using the previous exercise, show that $X\cup Y$ is a subspace if and only if $X\subset Y$ or $Y\subset X$ .

1.7.5.

What is the smallest subspace of the space of $4\times 4$ matrices which contains all upper triangular matrices ( $a_{j,k}=0$ for all $j>k$ ), and all symmetric matrices ( $A=A^{T}$ )? What is the largest subspace contained in both of those subspaces?

1.8. Application to computer graphics.

In this section we give some ideas of how linear algebra is used in computer graphics. We will not go into the details, but just explain some ideas. In particular we explain why manipulation with $3$ dimensional images are reduced to multiplications of $4\times 4$ matrices.

1.8.1. $2$ -dimensional manipulation.

The $x$ - $y$ plane (more precisely, a rectangle there) is a good model of a computer monitor. Any object on a monitor is represented as a collection of pixels, each pixel is assigned a specific color. Position of each pixel is determined by the column and row, which play role of $x$ and $y$ coordinates on the plane. So a rectangle on a plane with $x$ - $y$ coordinates is a good model for a computer screen: and a graphical object is just a collection of points.

Remark.

There are two types of graphical objects: bitmap objects, where every pixel of an object is described, and vector object, where we describe only critical points, and graphic engine connects them to reconstruct the object. A (digital) photo is a good example of a bitmap object: every pixel of it is described. Bitmap object can contain a lot of points, so manipulations with bitmaps require a lot of computing power. Anybody who has edited digital photos in a bitmap manipulation program, like Adobe Photoshop, knows that one needs quite a powerful computer, and even with modern and powerful computers manipulations can take some time.

That is the reason that most of the objects, appearing on a computer screen are vector ones: the computer only needs to memorize critical points. For example, to describe a polygon, one needs only to give the coordinates of its vertices, and which vertex is connected with which. Of course, not all objects on a computer screen can be represented as polygons, some, like letters, have curved smooth boundaries. But there are standard methods allowing one to draw smooth curves through a collection of points, for example Bezier splines, used in PostScript and Adobe PDF (and in many other formats).

Anyhow, this is the subject of a completely different book, and we will not discuss it here. For us a graphical object will be a collection of points (either wireframe model, or bitmap) and we would like to show how one can perform some manipulations with such objects.

The simplest transformation is a translation (shift), where each point (vector) $\mathbf{v}$ is translated by $\mathbf{a}$ , i.e. the vector $\mathbf{v}$ is replaced by $\mathbf{v}+\mathbf{a}$ (notation $\mathbf{v}\mapsto\mathbf{v}+\mathbf{a}$ is used for this). Vector addition is very well adapted to computers, so the translation is easy to implement.

Note, that the translation is not a linear transformation (if $\mathbf{a}\neq\mathbf{0}$ ): while it preserves the straight lines, it does not preserve $\mathbf{0}$ .

All other transformation used in computer graphics are linear. The first one that comes to mind is rotation. The rotation by $\gamma$ around the origin $\mathbf{0}$ is given by the multiplication by the rotation matrix $R_{\gamma}$ we discussed above,

R_{\gamma}=\left(\begin{array}[]{cc}\cos\gamma&-\sin\gamma\\ \sin\gamma&\cos\gamma\end{array}\right).

If we want to rotate around a point $\mathbf{a}$ , we first need to translate the picture by $-\mathbf{a}$ , moving the point $\mathbf{a}$ to $\mathbf{0}$ , then rotate around $\mathbf{0}$ (multiply by $R_{\gamma}$ ) and then translate everything back by $\mathbf{a}$ .

Another very useful transformation is scaling, given by a matrix

\left(\begin{array}[]{cc}a&0\\ 0&b\end{array}\right),

$a,b\geq 0$ . If $a=b$ it is uniform scaling which enlarges (reduces) an object, preserving its shape. If $a\neq b$ then $x$ and $y$ coordinates scale differently; the object becomes “taller” or “wider”.

Another often used transformation is reflection: for example the matrix

\left(\begin{array}[]{cc}1&0\\ 0&-1\end{array}\right),

defines the reflection through $x$ -axis.

We will show later in the book, that any linear transformation in $\mathbb{R}^{2}$ can be represented either as a composition of scaling rotations and reflections. However it is sometimes convenient to consider some different transformations, like the shear transformation, given by the matrix

\left(\begin{array}[]{cc}1&\tan\varphi\\ 0&1\end{array}\right).

This transformation makes all objects slanted, the horizontal lines remain horizontal, but vertical lines go to the slanted lines at the angle $\varphi$ to the vertical ones.

1.8.2. $3$ -dimensional graphics

Three-dimensional graphics is more complicated. First we need to be able to manipulate $3$ -dimensional objects, and then we need to represent it on $2$ -dimensional plane (monitor).

The manipulations with $3$ -dimensional objects is pretty straightforward, we have the same basic transformations: translation, reflection through a plane, scaling, rotation. Matrices of these transformations are very similar to the matrices of their $2\times 2$ counterparts. For example the matrices

\left(\begin{array}[]{ccc}1&0&0\\ 0&1&0\\ 0&0&-1\end{array}\right),\qquad\left(\begin{array}[]{ccc}a&0&0\\ 0&b&0\\ 0&0&c\end{array}\right),\qquad\left(\begin{array}[]{ccc}\cos\gamma&-\sin\gamma% &0\\ \sin\gamma&\cos\gamma&0\\ 0&0&1\end{array}\right)

represent respectively reflection through $x$ - $y$ plane, scaling, and rotation around $z$ -axis.

Note, that the above rotation is essentially $2$ -dimensional transformation, it does not change $z$ coordinate. Similarly, one can write matrices for the other 2 elementary rotations around $x$ and around $y$ axes. It will be shown later that a rotation around an arbitrary axis can be represented as a composition of elementary rotations.

So, we know how to manipulate $3$ -dimensional objects. Let us now discuss how to represent such objects on a $2$ -dimensional plane. The simplest way is to project it to a plane, say to the $x$ - $y$ plane. To perform such projection one just needs to replace $z$ coordinate by $0$ , the matrix of this projection is

\left(\begin{array}[]{ccc}1&0&0\\ 0&1&0\\ 0&0&0\end{array}\right).

Such method is often used in technical illustrations. Rotating an object and projecting it is equivalent to looking at it from different points. However, this method does not give a very realistic picture, because it does not take into account the perspective, the fact that the objects that are further away look smaller.

To get a more realistic picture one needs to use the so-called perspective projection. To define a perspective projection one needs to pick a point (the center of projection or the focal point) and a plane to project onto. Then each point in $\mathbb{R}^{3}$ is projected into a point on the plane such that the point, its image and the center of the projection lie on the same line, see Fig. 1.2.

This is exactly how a camera works, and it is a reasonable first approximation of how our eyes work.

Let us get a formula for the projection. Assume that the focal point is $(0,0,d)^{T}$ and that we are projecting onto $x$ - $y$ plane, see Fig. 1.3 a). Consider a point $\mathbf{v}=(x,y,z)^{T}$ , and let $\mathbf{v}^{*}=(x^{*},y^{*},0)^{T}$ be its projection. Analyzing similar triangles see Fig. 1.3 b), we get that

\frac{x^{*}}{d}=\frac{x}{d-z},

x^{*}=\frac{xd}{d-z}=\frac{x}{1-z/d},

and similarly

y^{*}=\frac{y}{1-z/d}.

Note, that this formula also works if $z>d$ and if $z<0$ : you can draw the corresponding similar triangles to check it.

Thus the perspective projection maps a point $(x,y,z)^{T}$ to the point $\left(\frac{x}{1-z/d},\frac{y}{1-z/d},0\right)^{T}$ .

This transformation is definitely not linear (because of $z$ in the denominator). However it is still possible to represent it as a linear transformation. To do this let us introduce the so-called homogeneous coordinates.

In the homogeneous coordinates, every point in $\mathbb{R}^{3}$ is represented by $4$ coordinates, the last, $4$ th coordinate playing role of the scaling coefficient. Thus, to get usual $3$ -dimensional coordinates of the vector $\mathbf{v}=(x,y,z)^{T}$ from its homogeneous coordinates $(x_{1},x_{2},x_{3},x_{4})^{T}$ one needs to divide all entries by the last coordinate $x_{4}$ and take the first 3 coordinates ⁴⁴4If we multiply homogeneous coordinates of a point in $\mathbb{R}^{3}$ by a non-zero scalar, we do not change the point. In other words, in homogeneous coordinates a point in $\mathbb{R}^{3}$ is represented by a line through $\mathbf{0}$ in $\mathbb{R}^{4}$ . (if $x_{4}=0$ this recipe does not work, so we assume that the case $x_{4}=0$ corresponds to the point at infinity).

Thus in homogeneous coordinates the vector $\mathbf{v}^{*}$ can be represented as $(x,y,0,1-z/d)^{T}$ , so in homogeneous coordinates the perspective projection is a linear transformation:

\left(\begin{array}[]{c}x\\ y\\ 0\\ 1-z/d\end{array}\right)=\left(\begin{array}[]{cccccccccc}1&0&0&0\\ 0&1&0&0\\ 0&0&0&0\\ 0&0&-1/d&1\end{array}\right)\left(\begin{array}[]{c}x\\ y\\ z\\ 1\end{array}\right).

Note that in the homogeneous coordinates the translation is also a linear transformation:

\left(\begin{array}[]{c}x+a_{1}\\ y+a_{2}\\ z+a_{3}\\ 1\end{array}\right)=\left(\begin{array}[]{cccccccccc}1&0&0&a_{1}\\ 0&1&0&a_{2}\\ 0&0&1&a_{3}\\ 0&0&0&1\end{array}\right)\left(\begin{array}[]{c}x\\ y\\ z\\ 1\end{array}\right).

But what happen if the center of projection is not a point $(0,0,d)^{T}$ but some arbitrary point $(d_{1},d_{2},d_{3})^{T}$ . Then we first need to apply the translation by $-(d_{1},d_{2},0)^{T}$ to move the center to $(0,0,d_{3})^{T}$ while preserving the $x$ - $y$ plane, apply the projection, and then move everything back translating it by $(d_{1},d_{2},0)^{T}$ . Similarly, if the plane we project to is not $x$ - $y$ plane, we move it to the $x$ - $y$ plane by using rotations and translations, and so on.

All these operations are just multiplications by $4\times 4$ matrices. That explains why modern graphic cards have $4\times 4$ matrix operations embedded in the processor.

Of course, here we only touched the mathematics behind $3$ -dimensional graphics, there is much more. For example, how to determine which parts of the object are visible and which are hidden, how to make realistic lighting, shades, etc.

Exercises.

1.8.1.

What vector in $\mathbb{R}^{3}$ has homogeneous coordinates $(10,20,30,5)$ ?

1.8.2.

Show that a rotation through $\gamma$ can be represented as a composition of two shear-and-scale transformations

T_{1}=\left(\begin{array}[]{cc}1&0\\ \sin\gamma&\cos\gamma\end{array}\right),\qquad T_{2}=\left(\begin{array}[]{cc}% \sec\gamma&-\tan\gamma\\ 0&1\end{array}\right).

In what order the transformations should be taken?

1.8.3.

Multiplication of a 2-vector by an arbitrary $2\times 2$ matrix usually requires $4$ multiplications.

Suppose a $2\times 1000$ matrix $D$ contains coordinates of $1000$ points in $\mathbb{R}^{2}$ . How many multiplications are required to transform these points using 2 arbitrary $2\times 2$ matrices $A$ and $B$ . Compare 2 possibilities, $A(BD)$ and $(AB)D$ .

1.8.4.

Write $4\times 4$ matrix performing perspective projection to $x$ - $y$ plane with center $(d_{1},d_{2},d_{3})^{T}$ .

1.8.5.

A transformation $T$ in $\mathbb{R}^{3}$ is a rotation about the line $y=x+3$ in the $x$ - $y$ plane through an angle $\gamma$ . Write a $4\times 4$ matrix corresponding to this transformation.

You can leave the result as a product of matrices.

Chapter 1 Basic Notions

1.1. Vector spaces

Remark.

Remark.

1.1.1. Examples.

Example.

Example.

Example.

Remark.

Example.

1.1.2. Matrix notation

Exercises.

1.1.1.

1.1.2.

1.1.3.

1.1.4.

1.1.5.

1.1.6.

1.1.7.

1.1.8.

1.2. Linear combinations, bases.

Definition 1.2.1.

Example 1.2.2.

Example 1.2.3.

Remark 1.2.4.

1.2.1. Generating and linearly independent systems

Definition 1.2.5.

Definition.

Definition.

Definition.

Proposition 1.2.6.

Proof.

Proposition 1.2.7.

Proof.

Remark.

Proposition 1.2.8.

Proof.

Exercises.

1.2.1.

1.2.2.

1.2.3.

1.2.4.

1.2.5.

1.2.6.

1.3. Linear Transformations. Matrix–vector multiplication

Definition.

1.3.1. Examples.

Example.

Example.

Example.

Example.

1.3.2. Linear transformations 𝔽n→𝔽m\mathbb{F}^{n}\to\mathbb{F}^{m}. Matrix–column multiplication.

Example.

Example.

1.3.3. Linear transformations and generating sets.

1.3.4. Conclusions.

Remark.

Remark.

Exercises.

1.3.1.

1.3.2.

1.3.3.

1.3.4.

1.3.5.

1.3.6.

1.3.7.

1.4. Linear transformations as a vector space

Remark.

1.5. Composition of linear transformations and matrix multiplication.

1.5.1. Definition of the matrix multiplication.

1.5.2. Motivation: composition of linear transformations.

Remark.

Remark.

Remark.

Example.

1.5.3. Properties of matrix multiplication.

1.5.4. Transposed matrices and multiplication.

1.5.5. Trace and matrix multiplication

Theorem 1.5.1.

Exercises.

1.3.2. Linear transformations $\mathbb{F}^{n}\to\mathbb{F}^{m}$ . Matrix–column multiplication.

Theorem 1.6.5 (Inverse of $A^{T}$ ).

1.8.1. $2$ -dimensional manipulation.

1.8.2. $3$ -dimensional graphics