Mathwizurd.com is created by David Witten, a mathematics and computer science student at Stanford University. For more information, see the "About" page.

Rank

Definition

The rank of a matrix is the number of non-zero rows in its RREF.

MathJax TeX Test Page $$\begin{bmatrix}1 & 2 & 5 & 10 \\ 3 & 4 & 8 & 10 \\ 3 & 4 & 8 & 10\end{bmatrix} \to \begin{bmatrix}1 & 2 & 5 & 10 \\ 0 & -2 & -7 & -20 \\ 0 & 0 & 0 &0\end{bmatrix} \to \begin{bmatrix}\boxed{1} & 0 & -2 & -10 \\ 0 & \boxed{1} & 3.5 & 10 \\ 0 & 0 & 0 &0\end{bmatrix}$$ In this example, the rank of this matrix is 2. As you can see if the rank equals the number of non-zero rows, it equals the number of pivots. The pivots cannot be greater than the number of rows or columns. $$\text{Rank } \le \min(m,n) \text{ (m = rows, n = columns)}$$

Injective

MathJax TeX Test Page Injective means a function is one-to-one. That is to say $$f(x) \text{ is injective iff } \forall x,y \text{ if } f(x) = f(y) \to x = y$$ One theorem is T(x) is injective iff T(x) = 0 is unique. $$

Theorem: Injective means Tx = 0 is trivial

MathJax TeX Test Page One theorem is T(x) is injective iff T(x) = 0 has only the trivial solution. $$\text{ Assume T(x) is injective}$$ $$T(0) = 0 \text{ (by definition}) $$ $$\text{ If }T(x) = T(0), x = 0 $$ $$\text{So, } T(x) = 0 \text{ only has the trivial solution.}$$ Now, we prove it the other way. Let's prove the contrapositive. That is to say, instead of proving (T(x) = 0 trivial) $\to$ (T(x) injective), we prove (T(x) not injective) $\to$ (T(x) = 0 non-trivial) $$\text{Assume } T(x) = 0 \text{ is not injective.}$$ $$\exists u,v, u \neq v \text{ s.t. } Tu = Tv = b$$ $$Tu - Tv = b - b = 0 \to T(u-v) = 0$$ $$T(u-v) = T(0) = 0$$ $$T(x) = 0 \text{ is not unique}$$ Why is this important? Because we can now use another important theorem.

Theorem: Ax = 0 is trivial means columns of A are linearly independent

MathJax TeX Test Page Let's dissect what $Ax = 0$ is trivial means. This means $$A\begin{bmatrix}x_1 \\ x_2 \\ x_3 \\ ... \\x_n\end{bmatrix} = \vec{0}_m$$ $$x_1\vec{a_1} + x_2\vec{a_2} + ... + x_n\vec{a_n} = \vec{0}_m$$ Saying that this equals 0 iff $x_1 ... x_n = 0$ is the same as saying $a_1 ... a_n$ are linearly independent.

Theorem: If the columns of A are L.I., then the number of pivots equals n.

MathJax TeX Test Page Row-reduction is a linear transformation, because it can be expressed as a matrix. All matrix products are linear transformations. So, we can say $B = M*A$ $$Ax = 0 \to MAx = M*0 \to Bx = 0$$ Observe that the values that satisfy $x$ will not change. That is to say, the columns of B are also linearly independent. This means none of the columns are 0. This means there is a non-zero value in every column. If there are n columns with a 1, with each one on a different row, then there are n rows with a 1, meaning there are n pivots. By definition, this means there are n non-zero rows. So, $\boxed{\text{rank} = n}$

Surjective

MathJax TeX Test Page A linear transformation means that $\forall b \in \mathbb{R}^m, \exists x \text{ s.t. } Tx = b$. Alternatively, you can say the columns of T span $\mathbb{R}^m$.

Theorem: A is surjective means that there m pivots.

MathJax TeX Test Page If A is surjective, then there exists a solution for every $Ax = b$. We can write this as an augmented matrix. $$\begin{bmatrix} A_1 & b_1 \\ A_2 & b_2 \\ A_3 & b_3 \\ ...\\ A_m & b_m\end{bmatrix}$$ Assume it doesn't have m pivots, then there exists a row that is all 0. $$\begin{bmatrix} A_1 & b_1 \\ A_2 & b_2 \\ A_3 & b_3 \\ ...\\ \vec{0} & b_m - c_1b_1 + ... + c_{m-1}b_{m-1}\end{bmatrix}$$ In order for this equation to be consistent, $b_m - c_1b_1 + ... + c_{m-1}b_{m-1} = 0$. However, we specified that this works for any $b_1 ... b_m$. Therefore, there is a contradiction.

We conclude that A has m pivots.

Row Space

A row space is the span of the rows of a matrix. The row space of two row-equivalent matrices is the same. Why? because to row reduce you just add linear combinations of rows. The basis of the row space is equal to the non-zero rows in the row-reduced matrix, which equals the dimension of the row space.

Column Space

The column space is the span of the columns of A. In other words, it’s the image of a matrix A. I will prove that the dimension of the column space equals the dimension of the row space which equals the rank.

Null Space

The null space is the set of all x such that Ax = 0. I will later prove that the Rank + Dim (Null Space) = n (columns in A).

Column Space

Markov Chains