Vector Spaces

References:

• What isn't a vector space?, Mathematics Stack Exchange.
• Things that are/aren't vector spaces, Dept. of Mathematics and Statistics,University of New Mexico.
• Vector Spaces, physics.miami.edu.
• Vector space, Wikipedia.

A vector is an element of a vector space. A vector space, also known as a linear space, $V$, is a set which has addition and scalar multiplication defined for it and satisfies the following for any vectors $\overrightarrow{u}$, $\overrightarrow{v}$, and $\overrightarrow{w}$ and scalars $c$ and $d$:

Functions Spaces

First let's properly define a function. If $X$ and $Y$ are sets and we have $x\in X$ and $y\in Y$, we can form a set $F$ that consists of ordered pairs $(x_i,y_j)$. If it is the case that $(x_1,y_1)\in F\cap (x_1,y_2)\in F⟹y_1==y_2$, then $F$ is a function and we write $y=F(x)$. This is called being "single valued", i.e., each input to the function is unambiguous. Note, $F(x)$ is not a function, it is the value returned by the function: $F$ is the function that defines the mapping from elements in $X$ (the domain) to the elements in $Y$ (the range).

One example of a vector space is the set of real-valued functions of a real variable, defined on the domain $[a\le x\le b]$. I.e., we're talking about $\{f_1,f_2,\dots ,f_n\}$ where each $f_i$ is a function. In other words, $f_i:\mathbb{R}\to \mathbb{R}$ with the aforementioned restriction on the domain.

We've said that a vector is any element in a vector space, but usually we thing of this in terms of, say, $[x,y]\in {\mathbb{R}}^2$. We can also however, given the above, think of functions as vectors: the function-as-a-vector being the "vector" of ordered pairs that make up the mapping between domain and range. So in this case the set of function is still like a set of vectors and with scalar multiplication and vector addition defined appropriately the rules for a vector space still hold!

What Isn't A Vector Space

It sounded a lot like everything was a vector space to me! So I did a quick bit of googling and found the paper "Things that are/aren't vector spaces". It does a really good example of showing how in maths we might build up a model of something and expect it to behave "normally" (i.e., obeys the vector space axioms), but in fact doesn't, in which case it becomes a lot harder to reason about them. This is why vectors spaces are nice... we can reason about them using logic and operations we are very familiar with and feel intuitive.

Linear Combinations

A linear combination of vectors is one that only uses the addition and scalar multiplication of those variables. So, given two vectors, $\overrightarrow{a}$ and $\overrightarrow{b}$ the following are linear combinations: $$\begin{gathered} 0\overrightarrow{a}+0\overrightarrow{b} \\ 5\overrightarrow{a}-2.5\overrightarrow{b} \\ -123\overrightarrow{a}+\pi \overrightarrow{b} \end{gathered}$$ This can be generalise to say that for any set of vectors $\{\overrightarrow{v_1},\overrightarrow{v_2},\dots ,\overrightarrow{v_n}\}\text{ for }\overrightarrow{v_1},\overrightarrow{v_2},\dots ,\overrightarrow{v_n}\in {\mathbb{R}}^m$ that a linear combination of those vectors is $c_1\overrightarrow{v_1}+c_2\overrightarrow{v_2}+\cdots +c_n\overrightarrow{v_n}\text{ for }{c}_i\in \mathbb{R}$.

Spans

The set of all linear combinations of a set of vectors $\{\overrightarrow{v_1},\overrightarrow{v_2},\dots ,\overrightarrow{v_n}\}$ is called the span of those vectors: $$\mathrm{span}(\overrightarrow{v_1},\overrightarrow{v_2},\dots ,\overrightarrow{v_n})=\{c_1\overrightarrow{v_1}+c_2\overrightarrow{v_2}+\cdots +c_n\overrightarrow{v_n}|c_i\in \mathbb{R}\}$$ The span can also be refered to as the generating set of vectors for a subspace.

In the graph to the right there are two vectors $\overrightarrow{a}$ and $\overrightarrow{b}$. The dotted blue lines show all the possible scalings of the vectors. The vectors span those lines. The green lines show two particular scalings of $\overrightarrow{a}$ added to all the possible scalings of $\overrightarrow{b}$. One can use this to imagine that if we added all the possible scalings of $\overrightarrow{a}$ to all the possible scalings of $\overrightarrow{b}$ we would reach every coordinate in ${\mathbb{R}}^2$. Thus, we can say that the set of vectors $\{\overrightarrow{a},\overrightarrow{b}\}$ spans ${\mathbb{R}}^2$, or $\mathrm{span}(\overrightarrow{a},\overrightarrow{b})={\mathbb{R}}^2$.

From this we may be tempted to say that any set of two, 2d, vectors spans ${\mathbb{R}}^2$ but we would be wrong. Take for example $\overrightarrow{a}$ and $\overrightarrow{b}=-\alpha \overrightarrow{a}$. These two variables are co-linear. Because they span the same line, no combination of them can ever move off that line. Therefore they do not span ${\mathbb{R}}^2$.

Lets write the above out a little more thoroughly... $$\overrightarrow{a}=\left[\begin{array}{c}{a}_1\\ a_2\end{array}\right],\overrightarrow{b}=\left[\begin{array}{c}-\alpha a_1\\ -\alpha a_2\end{array}\right]$$ The span of these vectors is, by our above definition: $$\mathrm{span}(\overrightarrow{a},\overrightarrow{b})=\{c_1\left[\begin{array}{c}{a}_1\\ a_2\end{array}\right]+c_2\left[\begin{array}{c}-\alpha a_1\\ -\alpha a_2\end{array}\right]\mid c_i\in \mathbb{R}\}$$ Which we can re-write as: $$\begin{array}{rl}\mathrm{span}(\overrightarrow{a},\overrightarrow{b})& =\{c_1\left[\begin{array}{c}{a}_1\\ a_2\end{array}\right]-\alpha c_2\left[\begin{array}{c}{a}_1\\ a_2\end{array}\right]\mid c_i\in \mathbb{R}\}\\ & =\{(c_1-\alpha c_2)\left[\begin{array}{c}{a}_1\\ a_2\end{array}\right]\mid c_i\in \mathbb{R}\}\end{array}$$ ... which we can clearly see is just the set of all scaled vectors of $\overrightarrow{a}$. Plainly, any co-linear set of 2d vectors will not span ${\mathbb{R}}^2$.

Linear Independence

We saw above that the set of vectors $\{\overrightarrow{a},-\alpha \overrightarrow{a}\}$ are co-linear and thus did not span ${\mathbb{R}}^2$. The reason for this is that they are linealy dependent, which means that one or more vectors in the set are just linear combinations of other vectors in the set.

For example, the set of vectors $\{[1,0],[0,1],[2,3]\}$ spans ${\mathbb{R}}^2$, but $[2,3]$ is redundant because we can remove it from the set of vectors and still have a set that spans ${\mathbb{R}}^2$. In other words, it adds no new information or directionality to our set.

A set of vectors will be said to be linearly dependent when: $$c_1\overrightarrow{v_1}+\cdots +c_n\overrightarrow{v_n}=\overrightarrow{0}\mid \mathrm{\exists }\{c_i\mid c_i\ne 0\}$$ Thus a set of vectors is linearly independent when the following is met: $$c_1\overrightarrow{v_1}+\cdots +c_n\overrightarrow{v_n}=\overrightarrow{0}\mid \mathrm{\forall }\{c_i\mid c_i=0\}$$ Sure, this is a definition, but why does this mean that the set is linearly dependent?

Think of vectors in a ${\mathbb{R}}^2$. For any two vectors that are not co-linear, there is no combination of those two vectors that can get you back to the origin unless they are both scaled by zero. The image to the left is trying to demonstrate that. If we scale $\overrightarrow{a}$, no matter how small we make that scaling, we cannot find a scaling of $\overrightarrow{b}$ that when added to $\overrightarrow{a}$ will get us back to the origin. Thus we cannot find a linear combination $c_a{v}_a+c_b{v}_b=\overrightarrow{0}$ where $c_a$ and/or $c_b$ does not equal zero.

This shows that neither vector is a linear combination of the other, because if it where, we could use a non-zero scaling of one, added to the other, to get us back to the origin.

We can also show that two vectors are linearly independent when their dot product is zero. This is covered in a latter section.

Another way of thinking about LI is that there is only one solution to the equation $A\overrightarrow{x}=\overrightarrow{0}$.

Linear Subspace

If $V$ is a set of vectors in ${\mathbb{R}}^n$, then $V$ is a subspace of ${\mathbb{R}}^n$ if and only if:

1. $V$ contains the zero vector: $\overrightarrow{0}\in V$
2. $V$ is closed under scalar multiplication: $\overrightarrow{x}\in V,\alpha \in \mathbb{R}⟹\alpha \overrightarrow{x}\in V$
3. $V$ is closed under addition: $\overrightarrow{a}\in V,\overrightarrow{b}\in V⟹\overrightarrow{a}+\overrightarrow{b}\in V$

What these rules mean is that, using linear operations, you can't do anything to "break" out of the subspace using vectors from that subspace. Hence "closed".

Surprising, at least for me, was that the zero vector is actually a subspace of ${\mathbb{R}}^n$ because the set $\{\overrightarrow{0}\}$ obeys all of the above rules.

A very useful thing is that a span is always a valid subspace. Take, for example, $V=\mathrm{span}(v_1,v_2,v_3)$. We can show that it is a valid subspace by checking that it objects the above 3 rules.

First, does it contain the zero vector? Recall that a span is the set of all linear combinations of the span vectors. So we know that the following linear combination is valid, and hence the span contains the zero vector. $$0{\overrightarrow{v}}_1+0{\overrightarrow{v}}_2+0{\overrightarrow{v}}_3=\overrightarrow{0}$$ Second, is it closed under scalar multiplication? Because the span is the set of all linear combinations, for any set of scalars $\{a_1,a_2,a_3\}$... $$a_1{\overrightarrow{v}}_1+a_2{\overrightarrow{v}}_2+a_3{\overrightarrow{v}}_3=\overrightarrow{x}$$ ... must also be in the subspace, by definition of a subspace!

Third, is it closed under vector addition? Well, yes, the same argument as made above would apply.

Interestingly, using the same method as above, we can see that even something trivial, like the $\mathrm{span}([a_1,a_2])$, which is just a line, is a subspace of ${\mathbb{R}}^2$.

It can also be shown that any subspace basis will have the same number of elements. We say that the dimension of a subspace is the number of elements in a basis for the subspace. So, for example, if we had a basis for our subspace consisting of 13 vectors, the dimension of the subspace would be lucky 13.

Basis Of A Subspace

Recall, $$V=\mathrm{span}({\overrightarrow{v}}_1,\dots ,{\overrightarrow{v}}_n)$$ $V$ is a subspace of ${\mathbb{R}}^n$ (where each vector ${\overrightarrow{v}}_i\in {\mathbb{R}}^n$). We also know that a span is the set of all possible linear combinations of these vectors.

If we choose a subset of $V$, $S$, where all the vectors in $S$ are linearly independent, an we can write any vector in $V$ as a linear combination of vectors in $S$, then we say that $S$ is a basis for $V$.

$S$ acts as a "minimal" set of vectors required to span $V$. I.e., if you added any other vector to $S$ it is superfluous, because it would be a linear combination of the vectors already in $S$. You don't add any new information.

Put more formally: Let $V$ be a subspace of ${\mathbb{R}}^n$. A subset ${\overrightarrow{v}}_1,{\overrightarrow{v}}_2,\dots ,{\overrightarrow{v}}_k$ is a basis for $V$ iff the following are true:

1. The vectors ${\overrightarrow{v}}_1,{\overrightarrow{v}}_2,\dots ,{\overrightarrow{v}}_k$ span $V$, and
2. They are linearly independent.

A subspace can have an infinite number of basis, but there are standard basis. For example in ${\mathbb{R}}^2$ the standard basis is $\{[1,0],[0,1]\}$. The rule of invariance of dimension states that two bases for a subspace contain the same number of vectors. The number of elements in the basis for a subspace is called the subspace's dimension, denoted as $\dim (W)$, where $W$ is the subspace.

Thus, we can say that every subspace $W$ of ${\mathbb{R}}^n$ has a basis and $\dim (W)\le n$.

A basis is a good thing because we can break down any element in the space that the basis defines into a linear combination of basic building blocks, i.e. the basis vectors.

To find a basis use the following method:

1. Form a matrix where the j^th column vector is the j^th vector $w_j$.
2. Reduce the matrix to row-echelon form.
3. Tak the column vectors that contain a pivot and these are the basis vectors.

TODO discuss the canonical vectors in R2 and R3. $[1,0]$, $[0,1]$... but we could also have $[1,0]$, $[1,1]$.

TODO unique coefficients. implied by the linear independence

TODO most important basis are orthogonal and orthonormal.

Orthonormal are good because we can find the coefficient in the new basis easily: ${\alpha }_k={\overrightarrow{w}}_k\dot{x}$

The Dot Product

Vector Transposes And The Dot Product

Dot Product With Matrix Vector Product

Unit Length Vectors

Orthogonal Vectors and Linear Independence

Figure 1

Orthogonal vectors are vectors that are perpendicular to each other. In a standard 2D or 3D graph, this means that they are at right angles to each other and we can visualise them as seen in Figure 1: $\overrightarrow{x}$ is at 90 degrees to both $\overrightarrow{y}$ and $\overrightarrow{z}$. $\overrightarrow{y}$ is at 90 degrees to $\overrightarrow{x}$ and $\overrightarrow{z}$, and $\overrightarrow{z}$ is at 90 degrees to $\overrightarrow{y}$ and $\overrightarrow{z}$.

In any set of any vectors, $[\overrightarrow{a_1},...,\overrightarrow{a_n}]$, the vectors will be linearly independent if every vector in the set is orthogonal to every other vector in the set. Note, however that whilst an orthogonal set is L.I., a L.I. set is not necessarily an orthogonal set. Take the following example: $$\overrightarrow{a}=\left[\begin{array}{c}1\\ 1\end{array}\right],\overrightarrow{b}=\left[\begin{array}{c}1\\ 1\end{array}\right]$$ The vectors $\overrightarrow{a}$ and $\overrightarrow{b}$ are L.I. because nethier can be represented as a linear combination of the other. They are not however orthogonal.

So, how do we tell if one vector is orthogonal to another? The answer is the dot product which is defined as follows. $$x\cdot y=\sum _1^n{x}_i{y}_i$$

We know when two vectors are orthogonal when their dot product is zero: $x\cdot y=0⟹$ x and y are orthogonal. You can scale either or both vectors and their dot product will still be zero!

But why is this the case? Lets imagine any two arbitrary vectors, each on the circumference of a unit circle (so we know that they have the same length and are therefore a proper rotation of a vector around the center of the circle). This is shown in figure 2. From the figure, we know the following:

Figure 2

$$\begin{array}{rlrl}{x}_1& =r\cos {\theta }_1& y_1& =r\sin {\theta }_1\\ x_2& =r\cos ({\theta }_1+{\theta }_n)& y_2& =r\sin ({\theta }_1+{\theta }_n)\end{array}$$ The vector $x_2$ is the vector $x_1$ rotated by ${\theta }_n$ degrees. We can use the following trig identities: $$\begin{array}{rl}\sin (a\pm b)& =\sin (a)\cos (b)\pm \cos (a)\sin (b)\\ \cos (a\pm b)& =\cos (a)\cos (b)\mp \sin (a)\sin (b)\end{array}$$ Substitute these into the formulas above, we get the following. $$\begin{array}{rl}{x}_2& =r\cos {\theta }_1\cos {\theta }_n-r\sin {\theta }_1\sin {\theta }_n\\ y_2& =r\sin {\theta }_1\cos {\theta }_n+r\cos {\theta }_1\sin {\theta }_n\end{array}$$ Which means that... $$\begin{array}{rl}{x}_2& =x_1\cos {\theta }_n-y_1\sin {\theta }_n\\ y_2& =y_1\cos {\theta }_n+x_1\sin {\theta }_n\end{array}$$ For a 90 degree rotation ${\theta }_n={90}^{\circ }$ we know that $\cos {\theta }_n=0$ and $\sin {\theta }_n=1$. Substiuting these values into the above equations we can clearly see that... $$\begin{array}{rl}{x}_2& =-y_1\\ y_2& =x_1\end{array}$$ Therefore, any vector in 2D space that is $[a,b]$ will become $[-b,a]$ and therefore the dot product becomes $-ab+ab=0$. And voilà, we know know why the dot product of two orthogonal 2D vectors is zero. I'm happy to take it on faith that this extrapolates into n dimensions :)

Another way of looking at this is to consider the law of cosines: $C^2=A^2+B^2-2AB\cos (c)$:

Here $A$ and $V$ represent the magnitude of the vectors $\overrightarrow{x}$, $\Vert \overrightarrow{x}\Vert$, and $\overrightarrow{y}$, $\Vert \overrightarrow{y}\Vert$. $C$ represents the magnitude of the vector $\Vert \overrightarrow{x}-\overrightarrow{y}\Vert$. Thus, we have this:

I.e., $\Vert \overrightarrow{x}-\overrightarrow{y}{\Vert }^2=\Vert \overrightarrow{x}{\Vert }^2+\Vert \overrightarrow{y}{\Vert }^2-2\Vert \overrightarrow{x}\Vert \Vert \overrightarrow{y}\Vert \cos ({\theta }_c)$.

When the angle between the vectors is 90 degrees, $\cos (90)=0$ and so that part of the equation disappears to give us $\Vert \overrightarrow{x}-\overrightarrow{y}{\Vert }^2=\Vert \overrightarrow{x}{\Vert }^2+\Vert \overrightarrow{y}{\Vert }^2$. Now... $$\begin{gathered} \Vert \overrightarrow{x}-\overrightarrow{y}{\Vert }^2=\Vert \overrightarrow{x}{\Vert }^2+\Vert \overrightarrow{y}{\Vert }^2 \\ \therefore \Vert \overrightarrow{x}{\Vert }^2+\Vert \overrightarrow{y}{\Vert }^2-\Vert \overrightarrow{x}-\overrightarrow{y}{\Vert }^2=0 \end{gathered}$$ Recall that $\Vert \overrightarrow{v}\Vert =\sqrt{v_1^2+v_2^2+...+v_n^2}$ and that therefore $\Vert \overrightarrow{v}{\Vert }^2=v_1^2+v_2^2+...+v_n^2$ .

Based, on this we can say that... $$\begin{array}{rl}\Vert \overrightarrow{x}-\overrightarrow{y}{\Vert }^2& =(x_1-y_1{)}^2+(x_2-y_2{)}^2+...+(x_n-y_n{)}^2\\ & =x_1^2-2x_1{y}_1+y_1^2+x_2^2-2x_2{y}_2+y_2^2+...+x_n^2-2x_n{y}_n+y_n^2\end{array}$$ Now, all of the $x_i^2$ and $y_i^2$ terms above will be cancelled out by the $\Vert \overrightarrow{x}{\Vert }^2$ and $\Vert \overrightarrow{y}{\Vert }^2$ terms, leaving us with... $$\Vert \overrightarrow{x}{\Vert }^2+\Vert \overrightarrow{y}{\Vert }^2-\Vert \overrightarrow{x}-\overrightarrow{y}{\Vert }^2=2x_1{y}_1+2x_2{y}_2+...+2x_n{y}_n=0$$ Which is just twice the dot product when the vectors are at 90 degrees - or just the dot product because we can divide through by 2.

Properties

Khan Academy has great articles. This is another good reference from MIT.

Scalar Multiplication

1. Associative: $(cd)A=c(dA)$
2. Distributive: $c(A+B)=cA+cB$ and $(c+d)A=cA+dA$
3. Identity: $1A=A$
4. Zero: $0A=O$
5. Closure: $cA$ is a matrix of the same dimensions as $A$.

Note that scalar multiplication is not commutative: $cA\ne Ac$!

Matrix Addition

1. Commutative: $A+B=B+A$
2. Associative: $A+(B+C)=(A+B)+C$
3. Zero: For any matrix $A$, there is a unique matrix $O$ such that $A+O=A$
4. Inverse: $\mathrm{\forall }A,\mathrm{\exists }!-A\mid A+(-A)=O$
5. Closure: $A+B$, is a matrix of the same dimensions as $A$ and $B$.

Matrix Multiplication

1. Associative: $(AB)C=A(BC)$
2. Distributive: $A(B+C)=AB+AC$
3. Identity: $IA=A$
4. Zero: $OA=O$
5. Inverse: Only if $A$ is a square matrix, then $A^{-1}$ is its inverse and $A{A}^{-1}=A^{-1}A=I$. Note that not all matrices are invertible.
6. Dimension: If $A$ is an $m\times n$ matrix and $B$ is an $n\times k$ matrix then $AB$ is an $m\times k$ matrix.

Note that matrix multiplication is not commutative: $AB\ne BA$!

Be careful: the equation $AB=0$ does not necessarily mean that $A=0$ or $B=0$ and for a general matrix $A$, $AB=AC\nRightarrow B=C$, unless $A$ is invertible.

Matrix Transpose

1. Associative:$(rA{)}^T=r{A}^T,r\in \mathbb{R}$
2. Distributive (into addition): $(A+B{)}^T=A^T+B^T$
3. Distributive (into mult): $(AB{)}^T=B^T{A}^T◂\text{Note the reversal of terms}$
   Generalises to $(ABC{)}^T=C^T{B}^T{A}^T$
4. Identity: $I^T=I$
5. Inverse: $(A^T{)}^T=A$
6. Name?: $(A^T{)}^{-1}=(A^{-1}{)}^T$
7. Name?: $(A\overrightarrow{x}{)}^T={\overrightarrow{x}}^T{A}^T◂\text{Note the reversal of terms}$
8. Name?: $\mathrm{rank}(A)=\mathrm{rank}(A^T)$
9. If columns of $A$ are LI then columns of $A^{T}A$ are LI. $A^{T}A$ is square and also invertible.

Matrix Inverse

1. Associative (self with inverse): $A{A}^{-1}=A^{-1}A=I$
2. Distributive (into scalar mult): $(rA{)}^{-1}=r^{-1}{A}^{-1},r\ne 0$
3. Distributive (into mult): $(AB{)}^{-1}=B^{-1}{A}^{-1}◂\text{Note the reversal of terms}$
4. Identity: $I^{-1}=I$
5. Name?: $(A^{-1}{)}^{-1}=A$
6. Name?: $(A^T{)}^{-1}=(A^{-1}{)}^T$

Matricies, Simultaneous Linear Equations And Reduced Row Echelon Form

References:

• Lecture 18: The Rank of a Matrix and Consistency of Linear Systems, Ohio University.
• Types of Solution Sets.
• Row Echelon Form and Number of Solutions.

The set of linear equations: $$a_{11}{x}_1+a_{12}{x}_2+...+a_{1n}{x}_n=b_1$$ $$a_{21}{x}_1+a_{22}{x}_2+...+a_{2n}{x}_n=b_2$$ $$...$$ $$a_{m1}{x}_1+a_{m2}{x}_2+...+a_{mn}{x}_n=b_m$$ Can be represented in matrix form: $$\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right]=\left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right]$$ Any vector $\overrightarrow{x}$, where $A\overrightarrow{x}=\overrightarrow{b}$, is a solution to the set of simultaneous linear equations. How can we solve this from the matrix. We create an augmented or patitioned matrix: $$\left[\begin{array}{ccccc}1a_{11}& a_{12}& \cdots & a_{1n}& b_1\\ a_{21}& a_{22}& \cdots & a_{2n}& b_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}& b_m\end{array}\right]$$ Next this matrix must be converted to row echelon form. This is where each row has the same or less zeros to the left than the row below. For example, the following matrix is in row echelon form: $$\left[\begin{array}{cccc}1& 2& 3& 4\\ 0& 1& 2& 3\\ 0& 0& 0& 1\\ 0& 0& 0& 2\end{array}\right]$$ But, this next one is not: $$\left[\begin{array}{cccc}1& 2& 3& 4\\ 0& 0& 0& 1\\ 0& 0& 0& 2\\ 0& 1& 2& 3\end{array}\right]$$ We go from a matrix to the equivalent in row-echelon form using elementary row operations:

1. Row interchange: $R_i\leftrightarrow R_j$
2. Row scaling: $R_i\to k{R}_i$
3. Row addition: $R_i\to R_i+k{R}_j$

In row echelon form:

1. All rows containing only zeros appear below rows with nonzero entries, and
2. The first nonzero entry in any row appears in a column to the right of the first nonzero entry in any preceding row.

The first non zero entry in a row is called the pivot for that row.

And woop, woop, even more important than echelon form is reduced row-echelon form (rref). This is when:

1. If a row has all zeros then it is below all rows with a non-zero entry.
2. The left most entry in each row is 1 - it is called the pivot.
3. The left most non-zero entry in each row is the only non-zero in that column.
4. Each row has more zeros to the left of the pivot than the row above.

Or, to put it another way, when it is a matrix in row-echelon form where:

1. All pivots are equal to 1, and
2. Each pivot is the only non-zero in its column.

Some important terms are pivot position and pivot column. The position is the location of a leading 1, which meets the above criteria, and the column is a column that contains a pivot position.

So why do we give a damn above RREF if we have row-echelon form? Well, one reason is it lets us figure out if a set of linear equations has a solution and which variables are free and which are dependent. The reason for this is that the RREF of every matrix is unique (whereas merely row reducing a matrix can have many resulting forms).

The free variable is one that you have control over, i.e. you can choose and manipulate its value. The dependent one depends on the values of the other variables in the experiment or is constant.

Pivot columns represent variables that are dependent. Why? Recall that the column vector containing a pivot is all-zeros except for the pivot. So if element j in a row of a rref matrix is a pivot, then in our system of equations $x_j$ only appears in this one equations in our RREF matrix. Thus, its value must be determined as this is the only place it occurs. It must either be a constant or a combination of other variables.

Because column vectors containing a pivot are all-zeros except for the pivot, the set of pivot columns must also be LI (see later). You can always represent the free columns as linear combinations of the pivot columns.

If we have an augmented matrix $[A|b]$:

1. No Solution. If the last (augmented) column of $[A|b]$ (ie. the column which contains $b$) contains a pivot entry.
2. Restructed Solution Set. If the last row of the matrix is all zeros except the pivot column which is a function of $b_1\dots b_m$.
3. Exactly One Solution. If the last (augmented) column of $[A|b]$ (ie. the column which contains $b$) does not contain a pivot entry and all of the columns of the coefficient part (ie. the columns of $A$) do contain a pivot entry.
4. Infinitely Many Solutions. If the last (augmented) column of $[A|b]$ (ie. the column which contains $b$) does not contain a pivot entry and at least one of the columns of the coefficient part (ie. the columns of $A$) also does not contain a pivot entry.

Let's look at a quick example of a matrix in echelon-form: $$\left[\begin{array}{cccc}-5& -1& -3& 3\\ 0& 3& 5& 8\\ 0& 0& 2& -4\end{array}\right]$$

We can get the solution to the set of simultaneous linear equations using back substitution. Directly from the above row-echelon form (useful because the last row has one pivot and no free variables) matrix we know that: $$\begin{array}{}\text{(1)}& -5x_1-x_2-3X3=3\end{array}$$ $$\begin{array}{}\text{(2)}& 3x_2+5x_3=8\end{array}$$ $$\begin{array}{}\text{(3)}& 2x_3=-4\end{array}$$ From (1) we know: $$\begin{array}{}\text{(4)}& x_3=-2\end{array}$$ Substitute (4) back into (2): $$\begin{array}{}\text{(5)}& 3x_2+-10=8⟹x_2=6\end{array}$$ Substitute (5) and (4) back into (1): $$\begin{array}{}\text{(6)}& -5x_1-6+6=3⟹x_1=-\frac{3}{5}\end{array}$$

We can use RREF to accomplish the same thing and find the solutions to the above. $$\left[\begin{array}{cccc}-5& -1& -3& 3\\ 0& 3& 5& 8\\ 0& 0& 2& -4\end{array}\right]$$ $$\to \left[\begin{array}{cccc}1& \frac{1}{5}& -\frac{3}{5}& -\frac{3}{5}\\ 0& 3& 5& 8\\ 0& 0& 1& -2\end{array}\right](r1=\frac{r1}{5},r3=\frac{r3}{2})$$ $$\to \left[\begin{array}{cccc}1& \frac{1}{5}& -\frac{3}{5}& -\frac{3}{5}\\ 0& 3& 0& 18\\ 0& 0& 1& -2\end{array}\right](r2=r2-5r3)$$ $$\to \left[\begin{array}{cccc}1& \frac{1}{5}& -\frac{3}{5}& -\frac{3}{5}\\ 0& 1& 0& 6\\ 0& 0& 1& -2\end{array}\right](r2=\frac{r2}{3})$$ $$\to \left[\begin{array}{cccc}1& 0& 0& -\frac{3}{5}\\ 0& 1& 0& 6\\ 0& 0& 1& -2\end{array}\right](r1=r1+\frac{3r3}{5}\to ,r1=r1-\frac{r2}{5})$$ Which means we come to the same conclusion as we did when doing back substitution, but were able to do it using elementary row operations.

We can not talk about the general solution vector, $\overrightarrow{x}$, which in this case is: $$\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}-\frac{3}{5}\\ 6\\ -2\end{array}\right]$$ We can also talk about the solution set, which is the set of all vectors that result in a valid solution to our system of equations. In this case our solution set is trivial: it just has the above vector in it because the RREF had pivots in every column so there is exactly one solution.

Lets, therefore, look at something more interesting. Take the RREF matrix below: $$\left[\begin{array}{ccccc}1& 0& 4& 9& 0\\ 0& 1& 8& 3& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}\right]$$ Now we have two free variables! Now $x_3=a$ and $x_4=b$ where $a$ and $b$ can be any values we like. Now the general solution vector looks like this: $$\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right]=\left[\begin{array}{c}-4a-9b\\ -8a-3b\\ a\\ b\end{array}\right]$$ How did we get here? We we know from the RREF matrix that: $$x_1+4x_{3}a+9x_{4}b=0$$ $$x_2+8x_{3}a+3x_{4}b=0$$ We replace $x_3$ and $x_4$ with our free variables and then solve for the pivots, thus getting the general solution vector.

The above can then be represented using the general solution vector: $$\left[\begin{array}{c}-4a-9b\\ -8a-3b\\ a\\ b\end{array}\right]=a\left[\begin{array}{c}-4\\ -8\\ 1\\ 0\end{array}\right]+b\left[\begin{array}{c}-9b\\ -3b\\ 0\\ 1\end{array}\right]$$ The solution set thus becomes: $$\mathrm{span}(\left[\begin{array}{c}-4\\ -8\\ 1\\ 0\end{array}\right],\left[\begin{array}{c}-9\\ -3\\ 0\\ 1\end{array}\right])$$

from sympy import Matrix, init_printing

init_printing(use_unicode=True)

system = Matrix(( (3, 6, -2, 11), (1, 2, 1, 32), (1, -1, 1, 1) ))
system
system.rref()[0]

⎡1  0  0  -17/3⎤
⎢              ⎥
⎢0  1  0  31/3 ⎥
⎢              ⎥
⎣0  0  1   17  ⎦

from sympy import Matrix, solve_linear_system, init_printing
from sympy.abc import x, y, z

init_printing(use_unicode=True)

system = Matrix(( (3, 6, -2, 11), (1, 2, 1, 32), (1, -1, 1, 1) ))
system

solve_linear_system(system, x, y, z)

⎡3  6   -2  11⎤
⎢             ⎥
⎢1  2   1   32⎥
⎢             ⎥
⎣1  -1  1   1 ⎦
{x: -17/3, y: 31/3, z: 17}

Matrix / Vector Multiplication

Matrix/vector multiplication is pretty straight forward: $$\left[\begin{array}{cc}a& c\\ b& d\end{array}\right]\left[\begin{array}{c}2\\ 4\end{array}\right]=\left[\begin{array}{c}2a+4c\\ 2b+4d\end{array}\right]$$

The concept of matrix multiplication, the type I learnt in school, is shown in the little animation below. For each row vector of the LHS matrix we take the dot product of that vector with each column vector from the RHS matrix to produce the result:

But having said that, I'd never really thought of it as shown below until watching some stuff on Khan Academy:

$$\left[\begin{array}{cc}a& c\\ b& d\end{array}\right]\left[\begin{array}{c}2\\ 4\end{array}\right]=2\left[\begin{array}{c}a\\ b\end{array}\right]+4\left[\begin{array}{c}c\\ d\end{array}\right]$$

We can think of it as the linear combination of the column vectors of the matrix where the coefficients are the members of the vector, where the first column vector is multiplied by the first element, the second column vector by the second element and so on.

So, for any mxn matrix, $A$, and vector $\overrightarrow{v}\in {\mathbb{R}}^n$ we can say that, $$A\overrightarrow{v}=\left[\begin{array}{cccc}\uparrow & \uparrow & & \uparrow \\ ⋮& ⋮& & ⋮\\ \overrightarrow{c_1}& \overrightarrow{c_2}& \cdots & \overrightarrow{c_n}\\ ⋮& ⋮& & ⋮\\ \downarrow & \downarrow & & \downarrow \end{array}\right]\left[\begin{array}{c}{v}_1\\ v_2\\ ⋮\\ v_n\end{array}\right]=v_1\overrightarrow{c_1}+v_2\overrightarrow{c_2}+\cdots +v_n\overrightarrow{c_n}$$

Null Space Of A Matrix

Definition

For an nxm vector $A$, the nullspace of the nxm matrix $A$, $N(A)$ is defined as follows: $$N(A)=\{\overrightarrow{x}\in {\mathbb{R}}^m\mid A\overrightarrow{x}=\overrightarrow{0}\}$$ In words, the null space of a matrix is the set of all solutions that result in the zero vector, i.e. the solution set to the above. We can get this set by using the normal reduction to RREF to solve the above ($[A\mid \overrightarrow{0}]⟶[R\mid \overrightarrow{0}]$). The solution space set to this is the null space.

The system of linear equations $A\overrightarrow{x}=\overrightarrow{0}$ is called homogeneous. It is always consistent, i.e., has a solution, because $\overrightarrow{x}=\overrightarrow{0}$ is always a solution (and is called the trivial solution).

The null space of a matrix is a valid subspace of ${\mathbb{R}}^n$ because it satisfies the following conditions, as we saw in the section on subspaces.

1. $N(A)$ contains the zero vector: $\overrightarrow{0}\in N(A)$
2. $N(A)$ is closed under scalar multiplication: $\overrightarrow{x}\in N(A),\alpha \in \mathbb{R}⟹\alpha \overrightarrow{x}\in N(A)$
3. $N(A)$ is closed under addition: $\overrightarrow{a}\in N(A),\overrightarrow{b}\in N(A)⟹\overrightarrow{a}+\overrightarrow{b}\in N(A)$

It can also be shown that $N(A)=N(\mathrm{RREF}(A))$, where $\mathrm{RREF}$ is the reduced row echelon form.

Relation To L.I. Of Column Vectors

The nullspace of a matrix can be related to the linear independence of it's column vectors. Using the above definition of nullspace, we can write: $$A\overrightarrow{v}=\left[\begin{array}{cccc}\uparrow & \uparrow & & \uparrow \\ ⋮& ⋮& & ⋮\\ \overrightarrow{a_1}& \overrightarrow{a_2}& \cdots & \overrightarrow{a_n}\\ ⋮& ⋮& & ⋮\\ \downarrow & \downarrow & & \downarrow \end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right]=\left[\begin{array}{c}{0}_1\\ 0_2\\ ⋮\\ 0_m\end{array}\right]$$ Recalling how we can write out vector/scalar multipication, we get, $$x_1\overrightarrow{a_1}+x_2\overrightarrow{a_2}+\cdots +x_n\overrightarrow{a_n}=\overrightarrow{0}$$ Recall from the section on linear independence that the above set of vectors is said to be linearly dependent when: $$x_1\overrightarrow{a_1}+x_2\overrightarrow{a_2}+\cdots +x_n\overrightarrow{a_n}=\overrightarrow{0},\mathrm{\forall }\{x_i\mid x_i=0\}$$ Given that our nullspace is the set of all vectors that satisfy the above, by definition, then we can say that the column vectors of a matrix A are LI if and only if $N(A)=\overrightarrow{0}$.

Relation To Determinant

If the determinant of a matrix is zero then the null space will be non trivial.

Calculating The Null Space

To find the null space of a matrix $A$, augment it with the zero vector and convert it to RREF. Then the solution set is the null space. So, if there are only pivots, the null space only contains the zero vector because there is only one solution (which therefore must be 0).

Example #1

Let's look at a trivial example: $$\begin{array}{rl}\text{Let }A& =\left[\begin{array}{ccc}4& 1& 1\\ 2& 7.5& -2\\ 6& 1.5& 3\end{array}\right]\end{array}$$ Then the null space is defined as the solution set to $A\overrightarrow{x}=\overrightarrow{0}$, i.e... $$\left[\begin{array}{ccc}4& 1& 1\\ 8& 3& 0\\ 0& 0& 3\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]$$ We find the solution set using the normal augmented matrix method: $$\begin{gathered} \left[\begin{array}{cccc}4& 1& 1& 0\\ 8& 3& 0& 0\\ 0& 0& 3& 0\end{array}\right]\mapsto \left[\begin{array}{cccc}4& 1& 1& 0\\ 0& 1& -1& 0\\ 0& 0& 3& 0\end{array}\right]\mapsto \left[\begin{array}{cccc}4& 1& 1& 0\\ 0& 1& -1& 0\\ 0& 0& 1& 0\end{array}\right] \\ \mapsto \left[\begin{array}{cccc}4& 1& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\end{array}\right]\mapsto \left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\end{array}\right] \end{gathered}$$ There are no free variables, so therefore the solution set can contain only the zero vector because we have three contraints $x_1=0,x_2=0$ and $x_3=0$. The only values for the $x_i$'s that can satisfy these constrains is zero, hence the null space can only contain the zero vector.

Example #2

Lets try an consider another trivial example. $$\begin{array}{rl}\text{Let }A& =\left[\begin{array}{ccc}2& 3& 0\\ 6& 12& 0\\ 8& 15& 0\end{array}\right]\end{array}$$ It's pretty contrived because I constructed it by applying row operations to the identify matrix! Null space is defined as solutions to: $$\left[\begin{array}{ccc}2& 3& 0\\ 6& 12& 0\\ 8& 15& 0\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]$$ We find the solution set using the normal augmented matrix method: $$\left[\begin{array}{cccc}2& 3& 0& 0\\ 6& 12& 0& 0\\ 8& 15& 0& 0\end{array}\right]\mapsto \left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 0\end{array}\right]$$ Now we can see that $x_1=0$ and $x_2=0$. The variable $x_3$, however, is free. It can take any value. Let's call that value $x_3=a$. The solution vector is therefore: $$\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ a\end{array}\right]$$ The general solution vectors is therefore: $$a\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]$$ So we can say the null space is: $$\mathrm{N}(A)=\mathrm{span}\left(\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]\right)$$