Introductory Linear Algebra/Vectors and subspaces

Vectors

Introduction

Without distinguishing row and column vectors, we can define Template:Colored em as follows: Template:Colored definition Template:Colored remark A special type of vector is the Template:Colored em. Template:Colored definition Template:Colored remark Template:Colored example However, in linear algebra, we sometimes need to distinguish row and column vectors, which are defined as follows: Template:Colored definition Template:Colored remark Template:Colored example Template:Colored remark The two basic vector operations are addition and scalar multiplication. Using these two operations only, we can Template:Colored em multiple vectors as in the following definition. Template:Colored definition Template:Colored example Template:Colored exercise Another concept that is closely related to linear combinations is Template:Colored em. Template:Colored definition Template:Colored remark Template:Colored example Template:Colored exercise

Linear independence

Template:Colored definition Template:Colored remark Then, we will introduce an intuitive result about linear dependence, in the sense that the results match with the name 'linear dependence'. Template:Colored proposition

Proof.

• Only if part:

• without loss of generality, suppose $c_1{𝐯}_1+\cdots +c_k{𝐯}_k$ in which $c_1\ne 0$ (we can replace $c_1$ by another scalar, and the result still holds by symmetry).
• Then, ${𝐯}_1=-\frac{c_2}{c_1}{𝐯}_2-\cdots -\frac{c_k}{c_1}{𝐯}_k$, i.e. ${𝐯}_1$ is a linear combination of the others.

• If part:

• without loss of generality, suppose ${𝐯}_1=b_2{𝐯}_2+\cdots +b_k{𝐯}_k$ (we can similarly replace ${𝐯}_1$ by another vector, and the result still holds by symmetry).
• Then, ${𝐯}_1-b_2{𝐯}_2-\cdots -b_k{𝐯}_k=\mathrm{𝟎}$.

• Since the coefficient of ${𝐯}_1$ is nonzero (it is one), ${𝐯}_1,\dots ,{𝐯}_k$ are linearly dependent.

$◻$

Template:Colored remark Template:Colored example Then, we will introduce a proposition for Template:Colored em vectors. Template:Colored proposition

Proof. $$a_1{𝐯}_1+\cdots +a_k{𝐯}_k=b_1{𝐯}_1+\cdots +b_k{𝐯}_k,\iff (a_1-b_1){𝐯}_1+\cdots +(a_k-b_k){𝐯}_k=\mathrm{𝟎}$$ By the linear independence of vectors, $$a_1-b_1=\cdots =a_k-b_k=0,$$ and the result follows.

$◻$

Template:Colored example Template:Colored example Template:Colored exercise Then, we will discuss two results that relate linear independence with SLE. Template:Colored proposition

Proof. Setting $𝐱=(c_1,\dots ,c_n{)}^T$, $$c_1{𝐯}_1+\cdots +c_n{𝐯}_n=\mathrm{𝟎}⟺A𝐱=\mathrm{𝟎},$$ a homogeneous SLE. By definition of linear independence, $S$ is linearly independent is equivalent to $A𝐱=\mathrm{𝟎}$ only has the Template:Colored em solution, which is also equivalent to $A$ is invertible, by the simplified invertible matrix theorem.

$◻$

Proof. Let ${𝐚}_1,\dots ,{𝐚}_n$ be the Template:Colored em of $A$, and let $𝐱=(x_1,\dots ,x_n{)}^T$.

Then, $A𝐱=𝐛⟺x_1{𝐚}_1+\cdots +x_n{𝐚}_n=𝐛$. Assume there are two distinct solutions $(x_1,\dots ,x_n{)}^T$ and $(y_1,\dots ,y_n{)}^T$ for the SLE, i.e., $$x_1{𝐚}_1+\cdots +x_n{𝐚}_n=𝐛=y_1{𝐚}_1+\cdots +y_n{𝐚}_n.$$ But, by the proposition about comparing coefficients for linear independent vectors, $$(x_1,\dots ,x_n)=(y_1,\dots ,y_n),$$ which contradicts with our assumption that these two solutions are distinct.

$◻$

Subspaces

Then, we will discuss subspaces. Simply speaking, they are some subsets of ${ℝ}^n$ that have some nice properties. To be more precise, we have the following definition. Template:Colored definition Template:Colored remark Template:Colored example Template:Colored example We can see from this example that the entries themselves do not really matter. Indeed, we have the following general result: Template:Colored proposition

Proof. The idea of the proof is shown in the above example:

• $\mathrm{𝟎}\in V$ since zero vector is a linear combination of the vectors belonging to $S$; Template:Tick
• $𝐮,𝐯\in V\Rightarrow 𝐮+𝐯\in V$ since $𝐮+𝐯$ is a linear combination of the vectors belonging to $S$; Template:Tick
• $𝐯\in V,c\in ℝ\Rightarrow c𝐯\in V$ since $c𝐯$ is a linear combination of the vectors belonging to $S$. Template:Tick

$◻$

In particular, we have special names for some of the spans, as follows: Template:Colored definition Template:Colored remark Template:Colored example Template:Colored example Template:Colored example Template:Colored exercise Then, we will introduce some more terminologies related to subspaces. Template:Colored definition Template:Colored definition Template:Colored remark The following theorem highlights the importance of Template:Colored em. Template:Colored theorem

Proof.

• Only if part:

• $\beta$ is a generating set, so each vector in $V$ belongs to $\mathrm{span}\beta$, i.e. each vector in $V$ is a linear combination of vectors in $\beta$.
• Template:Colored em follows from the proposition about comparing coefficients for linear independent vectors.

• If part:

• $\beta$ generates $V$ because:

1. by definition of subspace, $\mathrm{span}\beta \subseteq V$ (since linear combinations of vectors in $\beta$ (the vectors in $\beta$ are also in $V$, by $\beta \subseteq V$) are belonging to $V$);
2. on the other hand, since each vector in $V$ can represented as a linear combination of vectors in $\beta$, we have $V\subseteq \mathrm{span}\beta$.
3. Thus, we have $\mathrm{span}\beta =V$, so $\beta$ generates $V$ by definition. Template:Tick

• $\beta$ is linearly independent because

• let ${𝐯}_1,\dots ,{𝐯}_n$ be the vectors in $\beta$ and
• assume $a_1{𝐯}_1+\cdots +a_n{𝐯}_n=\mathrm{𝟎}$ in which $a_1,\dots ,a_n$ are Template:Colored em, (i.e. ${𝐯}_1,\dots ,{𝐯}_n$ are linearly Template:Colored em) then we can express the zero vector in $V$ in two different ways:

$$a_1{𝐯}_1+\cdots +a_n{𝐯}_n,\text{ and }0{𝐯}_1+\cdots +0{𝐯}_n,$$

which contradicts the uniqueness of representation. Template:Tick

$◻$

Template:Colored example Template:Colored example Template:Colored exercise Then, we will discuss some ways to construct a basis. Template:Colored theorem Template:Colored remark Its proof is complicated. Template:Colored corollary

Proof. We start with an empty set $\varnothing$. It is linearly independent (since it is Template:Colored em linearly dependent by definition), and is a subset of every set. By extension theorem, it can be extended to a basis for subspace of ${ℝ}^n$. Thus, each subspace of ${ℝ}^n$ has a basis, found by this method.

$◻$

Template:Colored example Template:Colored exercise A terminology that is related to Template:Colored em is Template:Colored em. Template:Colored definition Template:Colored remark Recall that there are infinitely many bases for a subspace. Luckily, all bases have the same number of vectors, and so the dimension of subspace is unique, as one will expect intuitively. This is assured bFy the following theorem. Template:Colored theorem

Proof. Let ${\beta }_1=\{{𝐮}_1,\dots ,{𝐮}_k\}$ and ${\beta }_2=\{{𝐰}_1,\dots ,{𝐰}_{\ell }\}$. Also, let $U_{n\times k}$ and $W_{n\times \ell }$ be the matrices with ${𝐮}_i$'s and ${𝐰}_j$'s as Template:Colored em.

By definition of basis, $\mathrm{span}{\beta }_1=V$, and $\mathrm{span}{\beta }_2=V$, so $${𝐰}_1+0{𝐰}_2+\cdots +0{𝐰}_k=a_{11}{𝐮}_1+a_{21}{𝐮}_2+\cdots +a_{k1}{𝐮}_k⟹{𝐰}_1=U{𝐚}_1$$ for some ${𝐚}_1=(a_{11},\dots ,a_{k1}{)}^T$. By symmetry, ${𝐰}_2=U{𝐚}_2,\dots ,{𝐰}_{\ell }=U{𝐚}_{\ell }$. Thus, $W=UA$ in which $A$ is the matrix whose columns are ${𝐚}_1,\dots ,{𝐚}_{\ell }$, of size $k\times \ell$.

We claim that $A𝐱=\mathrm{𝟎}$ only has the trivial solution, and this is true, since:

• If $A𝐱=\mathrm{𝟎}$, then $W𝐱=UA𝐱=U\mathrm{𝟎}=\mathrm{𝟎}$, and thus $𝐱=0$, since the columns of $W$ are linearly independent, by the proposition about the relationship between linear independence and number of solutions in SLE.

Thus, the RREF of $(A|\mathrm{𝟎})$ (with $\ell +1$ columns) has a leading one in each of the first $\ell$ columns. Since there are $k$ rows in $(A|\mathrm{𝟎})$, we have $k\ge \ell$ (if $k<\ell$ , we cannot have $\ell$ leading ones, since there are at most $k<\ell$ leading ones)

By symmetry (swapping the role of ${\beta }_1$ and ${\beta }_2$), $k\le \ell$, and thus $k=\ell$

$◻$

Template:Colored example Template:Colored example Template:Colored exercise Then, we will discuss the bases of row, column and null spaces, and also their dimensions. Template:Colored proposition

Proof. It can be proved that the row space is unchanged when an ERO is performed. E.g.,

• (type I ERO) $\mathrm{span}(\{{𝐫}_1,{𝐫}_2,{𝐫}_3\})=\mathrm{span}(\{{𝐫}_2,{𝐫}_1,{𝐫}_3\})$;
• (type II ERO) $\mathrm{span}(\{{𝐫}_1,{𝐫}_2,{𝐫}_3\})=\mathrm{span}(\{k{𝐫}_1,{𝐫}_2,{𝐫}_3\})$;
• (type III ERO) $\mathrm{span}(\{{𝐫}_1,{𝐫}_2,{𝐫}_3\})=\mathrm{span}(\{{𝐫}_1+k{𝐫}_2,{𝐫}_2,{𝐫}_3\})$.

Assuming this is true, we have $\mathrm{Row}(A)=\mathrm{Row}(R)$. It can be proved that the nonzero rows of $R$ generate $\mathrm{Row}(R)$, and they are linearly independent, so the nonzero rows form a basis for $\mathrm{Row}(R)=\mathrm{Row}(A)$.

$◻$

Proof. Using Gauss-Jordan algorithm, $(A|\mathrm{𝟎})$ can be transformed to $(R|\mathrm{𝟎})$ via EROs, and they are row equivalent. Thus, $A𝐱=\mathrm{𝟎}$ and $R𝐱=\mathrm{𝟎}$ have the same solution set. Then, it can be proved that linearly (in)dependent columns of $A$ correspond to linearly (in)dependent columns of $R$. It follows that $\{{𝐚}_{i_1},\dots ,{𝐚}_{i_k}\}$ is linearly Template:Colored em, and all other columns belong to the span of this set.

$◻$

Proof. The idea of the proof is illustrated in the above example: if there are $k$ independent unknowns in the solution set, we need a set consisting at least $k$ vectors to generate the solution set.

$◻$

We have special names for the dimensions of row, column and null spaces, as follows: Template:Colored definition Indeed, the row rank and the column rank of each matrix are the same. Template:Colored proposition

Proof. We can see this from the bases found by the proposition about basis for row space (number of nonzero rows is the number of leading ones of the RREF of $A$) and the proposition about basis for column space (there are $k$ column vectors, and $k$ is the number of leading ones by the assumption).

$◻$

Because of this proposition, we have the following definition. Template:Colored definition Template:Colored remark Then, we will introduce an important theorem that relates Template:Colored em and Template:Colored em. Template:Colored theorem

Proof. Let $R$ be the RREF of $A$. $\mathrm{rank}(A)$ is the number of Template:Colored em of $R$, and $\mathrm{nullity}(A)$ is the number of Template:Colored em unknowns of $R𝐱=\mathrm{𝟎}$, which is $n$ minus the number of Template:Colored em of $R$. The result follows.

$◻$