aThis note is based on Linear Done Right by Sheldon Axler, explaining some aspects that confuse me when reading Sec. 2.1 of the book. I personally don't own any credit for the proofs showing here. This is just a compilation of better ways(in my personal opinion) to present the content in the book. By following the same nomenclature in the book, we use F${\displaystyle \mathcal{F}}$ to represent either R${\displaystyle \mathbb{R}}$ or C${\displaystyle \mathbb{C}}$. TOC1. Definitions: Span and Linear Independence 2. Useful lemmas of linear (in)dependency 3. Interesting Examples of Using Linearly (In)Dependency Lemmas 4. Finite- and Infinite-dimensional vector space 1. Definitions: Span and Linear Independence

Definition1Let a list of vectors, v1,v2,...,vm∈V${\displaystyle v_1,v_2,...,v_m\in V}$. The list spans the vector space V${\displaystyle V}$, when every element v∈V${\displaystyle v\in V}$ can be represented by the vectors in the list, i.e.,(1)V={v=m∑iaivi:vi∈V,ai∈F,for i=1,2,3...,m }$$V=\{v=\sum _i^m{a}_i{v}_i:v_i\in V,a_i\in \mathcal{F},fori=1,2,3...,m\}$$In other words, V=span(v1,v2,...,vm)${\displaystyle V=span(v_1,v_2,...,v_m)}$.

The Definition 1 represents element in V${\displaystyle V}$ using linear combination, i.e., sum of products of scalar and vector. The Definition 1 DOES NOT implies the uniqueness of the linear combination for v∈V${\displaystyle v\in V}$. To see this, let v1=(1,0,0), v2=(0,1,0), v3=(1,1,0)${\displaystyle v_1=(1,0,0),v_2=(0,1,0),v_3=(1,1,0)}$ and v4=(0,0,1)${\displaystyle v_4=(0,0,1)}$, and it's easy to show that R3=span(v1,v2,v3,v4)${\displaystyle {\mathbb{R}}^3=span(v_1,v_2,v_3,v_4)}$. Suppose we have another vector, v=(3,3,2)${\displaystyle v=(3,3,2)}$, we havev=3v1+3v2+2v4=3v3+2v4$$v=3v_1+3v_2+2v_4=3v_3+2v_4$$So we have two different ways to present v${\displaystyle v}$ in the vector space R3${\displaystyle {\mathbb{R}}^3}$. With this example A natural follow-up question would be,

Question

1

Is there a collection of vector {vi}${\displaystyle \{v_i\}}$ in V${\displaystyle V}$ that has an unique way to express any vector in V${\displaystyle V}$ if possible?

To answer this question, let's first introduce the concept of linear independence.

Definition2A list of vectors v1,v2,...,vm${\displaystyle v_1,v_2,...,v_m}$ is called linearly independent if the only choice of {ai}${\displaystyle \{a_i\}}$ that makes a1v1+a2v2+⋯+amvm=0${\displaystyle a_1{v}_1+a_2{v}_2+\cdots +a_m{v}_m=0}$ is a1=a2=⋯=am=0${\displaystyle a_1=a_2=\cdots =a_m=0}$. The empty list is also considered to be linearly independent.

The Definition 2 indicates the following lemma that relates to the unique way of expressing vectors.

Lemma1If a vector can be uniquely expressed by a list {vi} ${\displaystyle \{v_i\}}$of vectors, then {vi}${\displaystyle \{v_i\}}$ are linearly independent.

Proof: (⇐${\displaystyle \Leftarrow }$) Suppose {vi}${\displaystyle \{v_i\}}$ are linearly independent, and we have v=∑aivi=∑bivi,where ai≠bi$$v=\sum a_i{v}_i=\sum b_i{v}_i,\text{where}{a}_i\ne b_i$$then, 0=∑(ai-bi)vi$$0=\sum (a_i-b_i)v_i$$From Definition 2, we know ai-bi≡0${\displaystyle a_i-b_i\equiv 0}$, which contradicts with the condition ai≠bi${\displaystyle a_i\ne b_i}$. Thus, the expression must be unique.(⇒${\displaystyle \Rightarrow }$) Suppose v=∑aivi${\displaystyle v=\sum a_i{v}_i}$ and 0=∑civi${\displaystyle 0=\sum c_i{v}_i}$, so we havev=∑(ai+ci)vi$$v=\sum (a_i+c_i)v_i$$By the uniqueness of the expression, we must have ai+ci=ai${\displaystyle a_i+c_i=a_i}$, which gives ci=0${\displaystyle c_i=0}$. From Definition 2, {vi}${\displaystyle \{v_i\}}$ are linearly independent. Lemma 1 tells partial answer to the Question 1, i.e., the collection {vi}${\displaystyle \{v_i\}}$ must be made of linear independent vectors in the space. To make sure any v∈V${\displaystyle v\in V}$ can be expressed by {vi}${\displaystyle \{v_i\}}$, we must have V=span({vi})${\displaystyle V=span(\{v_i\})}$. The linearly independent vectors {vi}${\displaystyle \{v_i\}}$ that span a vector space V${\displaystyle V}$ is called the bases of V${\displaystyle V}$. A vector space that has finite number of bases is called finite-dimentional, and infinite-dimensional otherwise. In quantum computing, quantum states(vectors) of a quantum system live only in subspaces of a much bigger(often infinite-dimensional) vector space. Physically, this means that the quantum system of our interest usually has finite number of pure states(eigenvectors that are known to us). The superposition(linear combination) of these pure states gives arbitrary states of the quantum system. With this in mind, the following theorem lays out a way to find the subspace that contains at least the quantum states(vectors) of our interest.

Theorem1The span of a list of vectors in V${\displaystyle V}$ is the smallest subspace of V${\displaystyle V}$ containing all the vectors in the list of v1,v2,...,vm${\displaystyle v_1,v_2,...,v_m}$.

Proof:Suppose M${\displaystyle M}$ is the smallest subspace of V${\displaystyle V}$ containing all the vectors in the list. Because vj=0v1+0v2+⋯+1vj+⋯+0vm$$v_j=0v_1+0v_2+\cdots +1v_j+\cdots +0v_m$$we have vj∈span(v1,...,vm)${\displaystyle v_j\in span(v_1,...,v_m)}$, and M⊆span(v1,...,vm)${\displaystyle M\subseteq span(v_1,...,v_m)}$. Also, M${\displaystyle M}$ is a subspace and vj∈M${\displaystyle v_j\in M}$, we have, a1v1+a2v2+⋯+amvm∈M$$a_1{v}_1+a_2{v}_2+\cdots +a_m{v}_m\in M$$for all aj∈F${\displaystyle a_j\in \mathcal{F}}$. Thus, all the elements in span(v1,...,vm)${\displaystyle span(v_1,...,v_m)}$ are also contained in M${\displaystyle M}$, i.e.M⊇span(v1,...,vm).$$M\supseteq span(v_1,...,v_m).$$It now follows that M=span(v1,...,vm)${\displaystyle M=span(v_1,...,v_m)}$□ 2. Useful lemmas of linear (in)dependency There are two lemmas that are repeatedly used in proofs of interesting properties of vector (sub)spaces, as listed below:

Lemma2Linear Dependence LemmaSuppose v1,v2,...,vm${\displaystyle v_1,v_2,...,v_m}$ is a linearly dependent list of V${\displaystyle V}$. Then there exists j∈{1,2,3,...,m}${\displaystyle j\in \{1,2,3,...,m\}}$ such that the following hold:a) vj∈span(v1,...,vj-1)${\displaystyle v_j\in span(v_1,...,v_{j-1})}$;b) if the jth${\displaystyle j^{th}}$ term is removed from {vj}${\displaystyle \{v_j\}}$ list, the span of the remaining list equal original span.

Proof:The linear dependency of the list results in some of the coefficients aj∈F${\displaystyle a_j\in \mathcal{F}}$ in the equation below are nonzero:0=a1v1+⋯+amvm$$0=a_1{v}_1+\cdots +a_m{v}_m$$chossing j${\displaystyle j}$ to be the largest number that has aj≠0${\displaystyle a_j\ne 0}$. Then,vj=-a1

ajv1-a2

ajv2-⋯-aj-1

ajvj-1∈span(v1,...,vj-1)$$v_j=-\frac{a_1}{a_j}{v}_1-\frac{a_2}{a_j}{v}_2-\cdots -\frac{a_{j-1}}{a_j}{v}_{j-1}\in span(v_1,...,v_{j-1})$$This proves a). To prove b), we notice that for arbitrary vector u∈span(v1,v2,...,vm)${\displaystyle u\in span(v_1,v_2,...,v_m)}$, we haveu=c1v1+⋯+cmvm$$u=c_1{v}_1+\cdots +c_m{v}_m$$We can replace vj${\displaystyle v_j}$ with an expression of other vectors using the second equation above. This shows that u${\displaystyle u}$ is in the span of the list without vj${\displaystyle v_j}$.□

Lemma3Length of linearly independent list ≤${\displaystyle \le }$length of spanning listIn a finite-dimensional vector space, the length of every linearly independent vector is less than or equal to the length of every spanning list of vectors

Proof (Axler's proof with slight modification):Suppose u1,...,um${\displaystyle u_1,...,u_m}$ is linearly independent in V${\displaystyle V}$, and w1,...,wn${\displaystyle w_1,...,w_n}$ spans V${\displaystyle V}$. To show m≤n${\displaystyle m\le n}$, we replace wj${\displaystyle w_j}$ with ui${\displaystyle u_i}$ step by step. Step 1: Let B={wi}${\displaystyle B=\{w_i\}}$, and adding u1${\displaystyle u_1}$ in B${\displaystyle B}$ gives a list of linearly dependent vectors, as ui${\displaystyle u_i}$ can be represented by vectors in B${\displaystyle B}$. Thus, by Lemma 2, we can remove one of the vectors in B${\displaystyle B}$ so that the remaining vectors still span V${\displaystyle V}$. Step j: The list B${\displaystyle B}$ from step j-1${\displaystyle j-1}$ spans V${\displaystyle V}$. And the list now contains u1,...,uj-1${\displaystyle u_1,...,u_{j-1}}$ and some wi${\displaystyle w_i}$. Because {uj}${\displaystyle \{u_j\}}$ are linearly independent. By Lemma 2, there must be a vector in {wi}${\displaystyle \{w_i\}}$ that can be represented as a linear combination of {uj}${\displaystyle \{u_j\}}$ and the rest of wj${\displaystyle w_j}$. At this point, we need to assure there is enough w${\displaystyle w}$'s for us to proceed this replacement process. It turns out it must be! Assume uk+1,...,um${\displaystyle u_{k+1},...,u_m}$ are left out after the replacement at the step k. Then, u1,u2,...,uk${\displaystyle u_1,u_2,...,u_k}$ span V${\displaystyle V}$ now. Since uk+1∈V${\displaystyle u_{k+1}\in V}$, we have uk+1=a1u1+⋯+akuk${\displaystyle u_{k+1}=a_1{u}_1+\cdots +a_k{u}_k}$ with some of {ai}${\displaystyle \{a_i\}}$ being nonzero, causing a contradiction to the condition of {ui}${\displaystyle \{u_i\}}$ being linearly independent. Therefore, we should always have vectors in B${\displaystyle B}$ waiting for replacement before we finish the step m${\displaystyle m}$. Step m: We have added all the u${\displaystyle u}$'s in to the list that spans V${\displaystyle V}$. Because at each step we move one w${\displaystyle w}$ out of B${\displaystyle B}$, there are at least m${\displaystyle m}$ w${\displaystyle w}$'s in B.${\displaystyle B.}$□ 3. Interesting Examples of Using Linearly (In)Dependency LemmasWe first introduce an example that uses the concept of linearly dependent to make the proof easier.

Lemma4Suppose v1,...,vm${\displaystyle v_1,...,v_m}$ is linearly independent in V${\displaystyle V}$ and w∈V${\displaystyle w\in V}$. Then v1,...,vm,w${\displaystyle v_1,...,v_m,w}$ is linearly independent if and only ifw∉span(v1,...,vm)$$w\notin span(v_1,...,v_m)$$

Proof:We first notice that Lemma 4 can be rephrased as v1,...,vm,w${\displaystyle v_1,...,v_m,w}$ is linearly dependent if and only if w∈span(v1,...,vm)${\displaystyle w\in span(v_1,...,v_m)}$. (⇒${\displaystyle \Rightarrow }$) ∵ v1,...,vm,w${\displaystyle \because v_1,...,v_m,w}$ is linear dependent, ∴ a1v1+a2v2+⋯+bw=0${\displaystyle \therefore a_1{v}_1+a_2{v}_2+\cdots +bw=0}$ does not have all the cofficients being zero. If b=0${\displaystyle b=0}$, then a1v1+a2v2+⋯+amvm=0${\displaystyle a_1{v}_1+a_2{v}_2+\cdots +a_m{v}_m=0}$ and ai≡0${\displaystyle a_i\equiv 0}$, contradicting with the linear dependency. Thus b≠0${\displaystyle b\ne 0}$, and w=-1

bm∑i=1aivi$$w=-\frac{1}{b}\sum _{i=1}^m{a}_i{v}_i$$which follows w∈span({vi})${\displaystyle w\in span(\{v_i\})}$.(⇐${\displaystyle \Leftarrow }$) ∵w∈span(v1,...,vm),∴w=b1v1+⋯+bmvm${\displaystyle \because w\in span(v_1,...,v_m),\therefore w=b_1{v}_1+\cdots +b_m{v}_m}$. According to Lemma 4, we have v1,...,vm,w${\displaystyle v_1,...,v_m,w}$ being linearly dependent. The following two proofs show how we can use Lemma 3 to identify whether a vector list spans vector spaces.

Question

2

: Explain why there does not exist a list of six polynomials that is linearly independent in P4(F)${\displaystyle {\mathcal{P}}_4(\mathcal{F})}$Solution: Pm(F)${\displaystyle {\mathcal{P}}_m(\mathcal{F})}$ denotes the set of all polynomials with coefficients in F${\displaystyle \mathcal{F}}$ and degree at most m${\displaystyle m}$. Also, Pm(F)=span(1,z,...,zm)${\displaystyle {\mathcal{P}}_m(\mathcal{F})=span(1,z,...,z^m)}$. Notice that P4(F)=span(1,z,z2,z3,z4)${\displaystyle {\mathcal{P}}_4(\mathcal{F})=span(1,z,z^2,z^3,z^4)}$, from Lemma 3 the length of linearly independent vector list cannot longer than the length of spanning vector list.

Question

3

: Explain why no list of four polynomials spans P4(F)${\displaystyle {\mathcal{P}}_4(\mathcal{F})}$.Solution: ∵P4(F)=span(1,z,...,z4)∴${\displaystyle \because {\mathcal{P}}_4(\mathcal{F})=span(1,z,...,z^4)\therefore }$length of spanning vector list is 5. If there is a four-polynomial list spanning P4(F)${\displaystyle {\mathcal{P}}_4(\mathcal{F})}$, then the length of linearly independent list (e.g.,1,z,z3,z4${\displaystyle 1,z,z^3,z^4}$) is larger than the length of spanning list (e.g., 1,z,z2,z3,z4${\displaystyle 1,z,z^2,z^3,z^4}$), contradicting Lemma 3. So no list of four polynomials spans P4(F)${\displaystyle {\mathcal{P}}_4(\mathcal{F})}$.

4. Finite- and Infinite-dimensional vector spaceWe don't care about infinite-dimensional vector space in quantum computing, because we cannot have infinite number of qubits after all. But we introduce its concept here anyway for completeness.

Definition3A vector space is called finite-dimensional if a list of finite number of vectors spans the space. Otherwise, it is infinite-dimensional.

Definition 3 is related to linear dependency through the following Lemma:

Lemma5V${\displaystyle V}$ is infinite-dimensional if and only if there is a sequence of v1,v2,...∈V${\displaystyle v_1,v_2,...\in V}$ such that v1,...,vm${\displaystyle v_1,...,v_m}$ is linearly independent for every positive integer m.

Proof: By induction if v1,v2,⋯,vm∈V${\displaystyle v_1,v_2,\cdots ,v_m\in V}$ is linearly independent, because V${\displaystyle V}$ is infinite-dimensional, there must exist some vm+1∈V${\displaystyle v_{m+1}\in V}$ such that vm+1∉span(v1,v2,v3,...vm)${\displaystyle v_{m+1}\notin span(v_1,v_2,v_3,...v_m)}$. From Lemma 2, v1,v2,v3,...,vm,vm+1${\displaystyle v_1,v_2,v_3,...,v_m,v_{m+1}}$ are linearly independent. Because V${\displaystyle V}$ is infinite-dimensional, we can keep adding new vector into the list that does not belong to the subspaces spanning by the old list. Thus, we have the list of v1,v2,v3,...,vm${\displaystyle v_1,v_2,v_3,...,v_m}$ being linearly independent for any positive interger m${\displaystyle m}$.□