aNote here is proofs of important theorems related to Basis and Dimension of vector space. All proofs are provided by the author(some inspired by Axler's book), so read it on your own risk. 1. Intertwined Definitions of Basis and Dimension 2. Spanning List, Linear Independency, and Subspace 1. Intertwined Definitions of Basis and DimensionAs what we eluded in previous notes, basis of a vector space should be a list of vectors that are linearly independent and span the space. However, a vector space could have multiple basis sets, do those sets have the same length? The answer to this has significant consequence in quantum computing, as it decides whether basis changes of a quantum system can be complished by n×n${\displaystyle n\times n}$ matrices, with n${\displaystyle n}$ being the dimension of vector space in which the quantum states live. Fortunately, all the basis sets of a vector space have the same length as we are proving now.

Theorem1All the bases of a vector space have the same length.

Proof:Let B1${\displaystyle B_1}$ and B2${\displaystyle B_2}$ are bases of a vector space V${\displaystyle V}$. Because vectors in B1${\displaystyle B_1}$ are linearly independent, and vectors in B2${\displaystyle B_2}$ span V${\displaystyle V}$. Because of the Lemma 3 in the note Span and Linear Dependency, we have the length of B1≤${\displaystyle B_1\le }$the length of B2${\displaystyle B_2}$. Using the similar argument, we also have the length of B2≤${\displaystyle B_2\le }$the length of B1${\displaystyle B_1}$. As a result, we have length of B1=${\displaystyle B_1=}$length of B2${\displaystyle B_2}$□ We can take the advantage of the uniqueness of basis length, indicated by Theorem 1, to define the dimension of vector space as

Definition1The dimension of a vector space is the length of its basis, and we use dim V${\displaystyle dimV}$ to present the dimension of vector space V${\displaystyle V}$.

2. Spanning List, Linear Independency, and SubspaceLike the previous notes, we consider things in the section title to find interesting and useful theorems related to the concepts of basis and dimemsion. Our first stop is to show a way that reduces spanning list to basis of a vector space by proving the following lemma.

Lemma1Spanning list can always be reduced to a basis of corresponding vector space

Proof:Let V=span(v1,v2,...,vm)${\displaystyle V=span(v_1,v_2,...,v_m)}$, and we can follow the algorithm below to eleminate vectors in the set {vi}${\displaystyle \{v_i\}}$, after which we will obtain the desired basis:Step 1: if v1=0${\displaystyle v_1=0}$, remove it from {v1}${\displaystyle \{v_1\}}$，remain it in {vi}${\displaystyle \{v_i\}}$ otherwise;Step j: if vj∈span(v1,...,vj-1)${\displaystyle v_j\in span(v_1,...,v_{j-1})}$, remove vj${\displaystyle v_j}$. Acoording to Lemma 2 in Span and Linear Dependency, we must have span({vi})=span({vi}-vj)=V${\displaystyle span(\{v_i\})=span(\{v_i\}-v_j)=V}$;Step m: vectors in the set now satisfy vj∉span(v1,...,vj-1)${\displaystyle v_j\notin span(v_1,...,v_{j-1})}$, indicating that v1,v2,...,vj${\displaystyle v_1,v_2,...,v_j}$ are linearly independent. To see this, suppose we have v1,v2,...,vj-1${\displaystyle v_1,v_2,...,v_{j-1}}$ linearly independent, and vj∉span(v1,...,vj-1)${\displaystyle v_j\notin span(v_1,...,v_{j-1})}$. If v1,v2,...,vj${\displaystyle v_1,v_2,...,v_j}$ are linearly dependent, there exist some nonzero ai∈F${\displaystyle a_i\in \mathcal{F}}$ such that a1v1+a2v2+⋯+ajvj=0$$a_1{v}_1+a_2{v}_2+\cdots +a_j{v}_j=0$$according to the definition of linear independency. If aj≠0${\displaystyle a_j\ne 0}$, then we must have some ai≠0${\displaystyle a_i\ne 0}$ for i=1,2,...,j-1${\displaystyle i=1,2,...,j-1}$ to give vj=-1/aj(a1v1+⋯+aj-1vj-1)${\displaystyle v_j=-1/a_j(a_1{v}_1+\cdots +a_{j-1}{v}_{j-1})}$, contradicting to the condition of vj∉span(v1,...,vj-1)${\displaystyle v_j\notin span(v_1,...,v_{j-1})}$. But if aj=0${\displaystyle a_j=0}$, then ai≡0${\displaystyle a_i\equiv 0}$ for i=1,2,...,j${\displaystyle i=1,2,...,j}$, another contradiction to the linear dependency we assumed. Thus, vj∉span(v1,...,vj-1)${\displaystyle v_j\notin span(v_1,...,v_{j-1})}$ gives linear independency of v1,v2,..,vj${\displaystyle v_1,v_2,..,v_j}$. The final set still spans V${\displaystyle V}$ as explained above, and the resulting set has vectors linearly independent and span V${\displaystyle V}$. So the set is indeed a basis of V${\displaystyle V}$.□ The basis of a vector space can also be obtained from a linearly independent vector set, as we now show by proving the following lemma.

Lemma2A linearly independent vector list can always be extended to a basis of vector space.

Proof:Let B={w1,w2,...,wm}${\displaystyle B=\{w_1,w_2,...,w_m\}}$ and {v1,v2,...,vn}${\displaystyle \{v_1,v_2,...,v_n\}}$ be the basis of vector pace V${\displaystyle V}$ and a linearly independent list in V${\displaystyle V}$, respectively. Because V=span(B)${\displaystyle V=span(B)}$, we have n≤m=dim V${\displaystyle n\le m=dimV}$ due to Lemma 3 in Span and Linear Dependency. Now we create a new list of v1,v2,...,vn,w1,w2,...,wm${\displaystyle v_1,v_2,...,v_n,w_1,w_2,...,w_m}$, and our target is to add some w${\displaystyle w}$'s into {vi}${\displaystyle \{v_i\}}$ so that the new set remains linearly independent and has a length of m${\displaystyle m}$. Starting from w1${\displaystyle w_1}$, we can follow the steps below to make such a set:Step 1: if w1∉span(v1,v2,...,vn)${\displaystyle w_1\notin span(v_1,v_2,...,v_n)}$ then add w1${\displaystyle w_1}$ in {vi}${\displaystyle \{v_i\}}$, otherwise proceed to the next stepStep m-n: Repeat step 1 for m-n${\displaystyle m-n}$ times to make a list of m${\displaystyle m}$ vector. Because wi∉span(v1,...,vn,w1,...,wi-1)${\displaystyle w_i\notin span(v_1,...,v_n,w_1,...,w_{i-1})}$, we must have our new list linearly independent. As a result, we get a new basis list make of v${\displaystyle v}$'s and some w${\displaystyle w}$'s. □ The proof above might leave readers wonder: what if I have a linearly independent list that has a length of dim V${\displaystyle dimV}$? Does that make the set a basis of vector space? Yes, and we can show this by proving the following theorem:

Theorem2A list of linearly independent vectors is a vector space basis if its length equals to the dimension of the vector space.

Proof:Suppose B={v1,v2,...,vn}${\displaystyle B=\{v_1,v_2,...,v_n\}}$ are linearly independent in V${\displaystyle V}$, and the length of B${\displaystyle B}$ equals to dim V${\displaystyle dimV}$. By using the steps in Lemma 2, we notice that extending B${\displaystyle B}$ to the basis of V${\displaystyle V}$ is trivial, as every basis of V${\displaystyle V}$ has a length of dim V${\displaystyle dimV}$, according to Theorem 1.□ Conversely, what if we have a spanning list that has a length of dim V${\displaystyle dimV}$? Yes again, and we have the following theorem.

Theorem3A spanning list is a vector space basis if its length equals to the dimension of the vector space.

Proof:Let dim V=n${\displaystyle dimV=n}$, and V${\displaystyle V}$ is spanned by v1,v2,...,vn${\displaystyle v_1,v_2,...,v_n}$. We now need to show that the list is linearly independent. Suppose {vi}${\displaystyle \{v_i\}}$ is linearly dependent, then we must have at least one vector that can be expressed as linear combination of other vectors,i.e., vj=a1v1+⋯+aj-1vj-1+aj+1vj+1+⋯+anvn$$v_j=a_1{v}_1+\cdots +a_{j-1}{v}_{j-1}+a_{j+1}{v}_{j+1}+\cdots +a_n{v}_n$$where some a${\displaystyle a}$'s are nonzero. According to Lemma 2 in Span and Linear Dependency, we have span({vi})=span({vi}-vj)=dim V≠n$$span(\{v_i\})=span(\{v_i\}-v_j)=dimV\ne n$$causing a contradiction. Therefore, a spanning list of dim V${\displaystyle dimV}$ vectors must be basis of V${\displaystyle V}$.□ Now that we have laid out useful things about spanning list and linearly independent list, we focus on subspaces in the following paragraphs. The most obvious lemma we can prove is argubly that

Lemma3If U${\displaystyle U}$ is a subspace of V${\displaystyle V}$, then dim U≤dim V${\displaystyle dimU\le dimV}$.

Proof (Axler's way):The equality indicates U=V${\displaystyle U=V}$, as can be easily shown. For the case of dim U<dim V${\displaystyle dimU<dimV}$, let U=span(u1,u2,...,un)${\displaystyle U=span(u_1,u_2,...,u_n)}$ and V=span(v1,v2,...,vm)${\displaystyle V=span(v_1,v_2,...,v_m)}$. Think of {ui}${\displaystyle \{u_i\}}$ as a linearly independent list, and {vi}${\displaystyle \{v_i\}}$ a spanning list, then the length of {ui}≤${\displaystyle \{u_i\}\le }$the length of {vi}${\displaystyle \{v_i\}}$. So it must be true that dim U≤dim V${\displaystyle dimU\le dimV}$.□ Axler's book introduced a neat proof to the following theorem. We will not repeat it here as copy exactly is not fun at all, and the author could not find a better alternative proof either.

Theorem4If U1${\displaystyle U_1}$ and U2${\displaystyle U_2}$ are subspaces of a finite-dimensional vector space, thendim(U1+U2)=dimU1+dim U2-dim(U1∩U2)$$dim(U_1+U_2)=dim{U}_1+dim{U}_2-dim(U_1\cap U_2)$$