Sketch Proofs

Question 1

Matrix algebra proofs (Prop 1&2)

Eg. A+(B+C)=(A+B)+C
Or A(BC)=(AB)C

Answer 1

Just use the (i,j) entry of the matrices

For the multiplication ones it may be easier to work on both sides and meet in the middle

Question 2

AIn=A=InA (Lemma 3)

Answer 2

Just use (i,j) entry

Question 3

Show if A is invertible, A has a unique inverse (Lemma 4)

Answer 3

Assume B,C both inverses. Consider BAC show B=C

Question 4

Show (AB)-1=(B-1)(A-1) if A,B invertible (Prop 5)

Answer 4

Literally just show (AB)(B-1)(A-1)=I

And the other way round

Question 5

An invertible nxn matrix can be reduced to In by EROs (Thm 6)

Answer 5

Show that only solution of Ax=0 is x=0 [x=Ix=(A-1)Ax=0]
Therefore x=0 is only solution of Ex=0. Where E is RRE of A

There are no free variables since all Xi must equal 0
Since there are no free variables each column must contain the leading entry of a row. Since each leading entry is to the right of the last one E=In

Question 6

Show applying an ERO is the same as left multiplying by the elementary matrix (Lemma 7)

Answer 6

Show manually for all 3 types

Question 7

If X1,X2,…,Xn are EROs that take A to In. If B is the result of using these EROs on In, then B is the inverse of A (Thm 8)

Answer 7

Consider the series of matrix multiplications of the elementary matrices then manipulate it

Question 8

In a vector space there exists a unique additive identity 0v (Lemma 9)

Answer 8

Assume multiple show equal

W+v+U

Question 9

In a vector space there exists unique additive inverses (Lemma 10)

Answer 9

Assume multiple show equal

Question 10

Properties of vector spaces (Prop 11)

P0v=0v
0V=0v
-P)v=P(-v
If Pv=0v then P=0 or v=0v

Answer 10

Use additive inverses

Try to prove these, they’re harder than you think

Question 11

Subspace test (Thm 12)

U is a subspace iff
0v in U and
Pu1+u2 in U for all u1, u2

Answer 11

Left->Right
Use axioms to show it’s always true

Right -> Left
Set U1,U2 to show closed

Question 12

If U is a subspace of V then U is a vector space (Prop 13)

Answer 12

State U has legitimate operations because it’s closed under addition and scalar multiplication

Then show the axioms - show it has an additive identity and inverse and state all other axioms inherited from V

Question 13

Take U,W subspaces of V

Then U+W is a subspace of V and
U intersect W is a subspace of V

(Prop 14)

Answer 13

Subspace test

Question 14

The span of any number of elements in V is a subspace of V (Lemma 15)

Answer 14

Use the subspace test

Question 15

Let v1,…,vm be linearly independent. Let vm+1 not be in span(v1,…,vm)
Then v1,…,vm,vm+1 are linearly independent (Lemma 16)

You can throw something not in a span and it’ll still be linearly independent

Answer 15

Take a linearly combination of them all. Assume am+1 is not 0 and show contradiction
Then show all the a’s=0 so it in linearly independent

Question 16

S (a subset of V) is a basis for V iff every vector in V has a unique expression as a linear combination of elements of S (Prop 17)

Answer 16

-> take 2 linear combinations and show they are the same

Question 17

Suppose V has a finite spanning set S. Then S contains a linearly independent spanning set (basis) (Prop 18)

Answer 17

Take the largest subset of S that is linearly independent and show it is a spanning set. Assume for contradiction it is not a spanning set and throw an extra element in to get contradiction

Question 18

Steinitz Exchange Lemma (Thm 19)

Take X a subset of V. Suppose that u in Span(X) but that u not in Span(X\{v}) for some v. 
Then let Y=(X\{v})U{u}. Span(Y)=Span(X)

Answer 18

Write u as a linear combination of X and rearrange to get v= (letting v=vn).
Then consider arbitrary element w in Span(Y). Write out linear combination and show w also in Span(X).
Same for w in Span(X) -> show in Span(Y)
Span(X)=Span(Y) by double inclusion

Question 19

For S,T finite subsets of V. If S is linearly independent and T spans V, the size of S is smaller or equal to the size of T. (Thm 20)

“Linearly independent sets are at most as big as spanning sets”

Answer 19

Use Steinitz exchange Lemma to swap out elements of T and replace them with elements of S. This new list still spans V. If you run out of elements of T before S you have a list Tj composed entirely of elements of S that spans V. If there are elements of S remaining, say u(j+1) then u(j+1) is a linear combination of Tj which is false since S is linearly independent

Question 20

If V is finite dimensional and S, T are bases of V. S and T are finite and the same size (Cor 21)

Answer 20

Since V is finite dimensional there exists a basis B of size n.

Then use the fact that linearly independent sets are at most as big as spanning sets 2000 times.
Remember B, S, and T are all spanning and linearly independent. Just use the rule in every possible way

Question 21

Let A be a matrix and B be a matrix obtained from A by a finite sequence of EROs. Then rowsp(A)=rowsp(B) and rowrank(A)=rowrank(B). (Lemma 22)

Answer 21

Check for each type of ERO that the spans are the same

Question 22

Let U be a subspace of finite-dimensional V. Then U is finite-dimensional and dim(U)<=dim(V). If dim(U)=dim(V), then U=V. (Prop 23)

Answer 22

Choose S to be a largest linearly independent set contained in U. Since is is linearly independent the size of S <=n. Show by contradiction that S spans U and such S is a basis for U

Then show that if dim(U)=dim(V) adding a vector to S causes S to be linearly dependent so S spans V.

Question 23

Show that, in an n-dimensional vector space V, If U is a spanning set for V and U has size n, U is a basis for V.

Answer 23

U is a spanning set for V and so U contains a basis for V. A basis for V must have size n so U is this basis.

Question 24

Show that, in an n-dimensional vector space V, if U is a linearly independent subset of V and U has size n, U is a basis for V

Answer 24

All linearly independent subsets have size at most n (as there is a spanning set of size n - the basis). So adding any vector v to U gives a linearly dependent set.

So v can be written as a linear combination of U. So U spans V so U is a basis

Question 25

Let U be a subspace of a finite-dimensional vector space V.
Then every basis of U can be extended to a basis of V.

That is, if u1,…,um is a basis for U. Then there is a basis for V that is u1,…,um,u(m+1),…,un 
for u(m+1),…,un ∈V. (Thm 24)

Answer 25

Take bases for U and V respectively. Create a list S0 for the basis of U. For each element in the basis of V add it to the list if vi∉Span(Si).
All Si are linearly independent as adding something not in the span maintains linear independence.
Proceed inductively.
vi ∈ Si ∀i and hence vi ∈ Sn ∀i.
So Span(Sn)=V.
So we have constructed a basis for V out of a basis for U

Question 26

Dimension Formula

Let U, W be subspaces of finite-dimensional vector space V over F. Then dim⁡(U+W)+dim⁡(U∩W)=dim⁡(U)+dim⁡(W) (Thm 25)

Answer 26

Consider a basis for U∩W.
Extend it to a basis for U and extend it to a basis for W.
Then show the combination of these bases is a basis for U+W: Show it spans U+W and show its linearly independent. Then the result follows

Question 27

Let U, W be subspaces of V. Then the following are equivalent (alternate definitions of direct sum) (Prop 26)

i) V is the direct sum of U and W
ii) every v has a unique expression v=u+w
iii) dim(V)=dim(U)+dim(W) and V=U+W
iv) dim(V)=dim(U)+dim(W) and U∩W ={0v}
v) if u1,…,um is a basis for U and w1,…,wn is a basis for W. Then u1,…,um,w1,…,wn is a basis for V

Answer 27

(i) <=> (ii) assume 2 expressions and show they are equal
(i) <=> (iii) and (i) <=> (iv) by dimension formula
(ii) <=> (v) quite simple via basis manipulation

Question 28

Let T:V->W be linear. Then T(0v)=0w (Prop 27)

Answer 28

Let z=T(0v)∈W. Consider z+z and show z=0w

Question 29

Let T:V0>W. Then the following are equivilent:
(i) T is linear
(ii) T(av1+bv2)=aT(v1)+bT(v2)
(iii) For any n>=1. T(a1v1+…+anvn)=a1T(v1)+…+anT(vn)
(Prop 28)

Answer 29

(i) =>(ii) simply
(ii) =>(i) show it abides definition of linear
(ii) =>(iii) by induction
(iii) =>(i) show it abides definition of linear

Question 30

Do the set of linear transformations form a vector space?
Let S, T be linear maps such that S,T:V→W.
Define S+T:V→W by (S+T)(v)=S(v)+T(v) and
Define λS:V→W by (λS)(v)=λS(v)
(Prop 29)

Answer 30

Show the vector space axioms fit

Question 31

Let S:U->V and T:V->W be linear.
Then ToS:U-> W is linear.
(Prop 30)

Answer 31

Just do the linear map test: Show (ToS)(au+bv)=a(ToS)(u)+b(ToS)(v)

Question 32

Let T:V->W be linear. Then T is invertible iff T is bijective (Prop 31)

Answer 32

Assume T has an inverse S. ST=idv and TS=idw. Show T is 1-1 and onto. To show 1-1 assume T(v)=T(w) and show v=w. To show onto note that TS(w)=w for all w so w is in the image of T

Assume T is bijective. Then T has an inverse S:W->V. Show S is linear. Take w1,w2 such that v1=S(w1),v2=S(w2). This implies T(v1)=w1, T(v2)=w2. Then show S(aw1+bw2)=aS(w1)+bS(w2)

Question 33

Let S:U->V and T:V->W be invertible linear maps. Then TS:U->W is invertible and (TS)^-1=S^-1 T^-1
(Prop 32)

Answer 33

Just show (TS)(S^-1 T^-1)=idv and (S^-1 T^-1)(TS)=idu

Question 34

T(v1)=T(v2) iff v1-v2∈KerT

Lemma 33

Answer 34

Quite simple. Just rearrange

Question 35

T:V->W. T is injective iff kerT={0} (Cor 34)

Answer 35

=> Assume kerT≠{0} for contradiction. Then there is a v such that T(v)=0w. So T(v)=T(0v) so not injective.

<= Same as all injective proofs. Assume T(v1)=T(v2) show v1=v2

Question 36

i) kerT is a subspace of V and ImT is a subspace of W
ii) If A is a spanning set for V, then T(A) is a spanning set for ImT
iii) If V is finite dimensional, then KerT and ImT are finite dimensional

Answer 36

i) Use the subspace test
ii) Take a spanning set A. Say that for any w in ImT there is v: T(v)=w then write v in terms of A and expand
iii) KerT<=V so is finite dimensional. ImT is finite dimensional from ii

Question 37

Rank-Nullity Theorem
Let V, W be vector spaces with V finite-dimensional.
Let T:V→W be linear. Then dimV=rank(T)+null(T) (Thm 36)

Answer 37

Take a basis, v1,…,vn, for kerT.
Extend it to a basis v1,…,vn,v’1,…,v’r for V.
Let wi=T(v’i)

CLAIM: S={w_1,…,w_r } is a basis for ImT.

S∪{T(v_1),…,T(v_n)} spans ImT from proposition 35 but v1,…,vn∈kerT so T(v1 ),…,T(vn ) do not contribute and so S spans ImT

Show S is linearly independent. Take a linear combination of S = 0w. Rewrite as T(v’i) and use linearity to get an element of kerT.
This can then be written as a linear combination of v1,…,vn. But v1,…,vn,v’1,…,v’r are linearly independent so all scalars=0 so w1,…,wr are linearly independent.

Result Follows

Question 38

Let T:V→V be linear. The following are equivalent: (Cor 37)

(i) T is invertible
(ii) rankT=dimV
(iii) nullT=0

Answer 38

(i) =>(ii). T invertible means T bijective means T surjective. So ImT=V so (ii)
(ii) =>(iii) rank-nullity
(iii) =>(i). Show T injective (kerT={0v}). Show T surjective (rank nullity). T bijective=>T invertible

Question 39

Let T:V→V be linear.

Then any one-sided inverse of T is a two-sided inverse, and so is unique. (Cor 38)

Answer 39

Say T has a right inverse S so TS=idv. Since idv surjective, T surjective. So rankT=dimV. So T has an inverse say S’. Show S=S’

Say T has a left inverse S so ST=idv. Since idv bijective, T bijective. So nullT=0. So T has an inverse say S’. Show S=S’

Question 40

Let V and W be vector spaces, with V finite-dimensional.
Let T:V→W be linear. Let U≤V. Then
dimU-nullT≤dimT(U)≤dimU.

In particular, if T is injective then dimT(U)=dimU (Lemma 39)

Answer 40

Take S:U→W as the restriction of T to U. S is linear and kerS≤kerT so nullS≤nullT.

By rank-nullity. dim⁡(ImS)=rankS=dim⁡U-nullS.

Use the inequalities and the fact that T(U)=Im(S) to get the needed inequalities.

If T injective then nullT=0. So from proved result: dimU≤dimT(U)≤dimU

Question 41

Let V be an n-dimensional vector space over F, let Bv be an ordered basis for V.
Let W be an m-dimensional vector space over F, let Bw be an ordered basis for W.
Then
(i) The matrix of 0:V→W is 0mxn
(ii) The matrix of idv:V→V is In
(iii) If S:V→W, T:V→W are linear and α,β∈F, then M(αS+βT)=αM(S)+βM(T)

Moreover, let T:V→W be linear, with matrix A wrt.Bv and Bw
Take v∈V with co-ordinates x=(x1,…,xn ) with respect to Bv. Then Ax is the coordinate vector of T(v) wrt. Bw

(Prop 40)

Answer 41

Consider the standard bases and T(vi) and construct the matrix like normal.
Then for (iii) simply deconstruct the matrix and show the equality.

Consider T(v)=T(sum of xjvj). Use linearity and write as elements of A. Then show that the coordinates of T(v) are the entries of Ax

Question 42

Let U, V, W be finite-dimensional vector spaces over F, with ordered bases Bu,Bv,Bw respectively.
Say |Bu|=m, |Bv|=n, |Bw|=p.
Let S:U→V,T:V→W be linear. Let A be the matrix of S wrt. Bu and Bv. Let B be the matrix of T wrt. Bv and Bw.
Then the matrix of T∘S wrt. Bu and Bw is BA. (Prop 41)

Answer 42

Quite intuitive.
Set up what S(ui ) and T(vi) are using summation notation.
Use the ideas of matrix multiplication and show that your final result is the (i,j) entry of BA

Question 43

Take A∈Mmxn(F)
Take B∈Mnxp(F)
Take C∈Mpxq(F).
Then A(BC)=(AB)C (Using linear maps). (Cor 42)

Answer 43

Consider A, B and C as left multiplication maps (which we know are linear).
Simple but just a bit nasty with notation.
Make sure you define all the maps with correct domain and codomain.

Question 44

Let V be a finite-dimensional vector space.
Let T:V→V be an invertible linear transformation.
Let v1,…,vn be a basis of V. Let A be the matrix of T with respect to this basis. Then A is invertible and A inverse is the matrix of T inverse with respect to this basis.
(Cor 43)

Answer 44

Quite simple. T^(-1) is linear and so has a matrix B. T^(-1) (T)=idv=T(T^(-1)).
The matrices for these compositions must also be equal. This gives you definition of inverse

Question 45

Let A be an n x n matrix. Any one-sided inverse of A is a two-sided inverse (Cor 44) (in terms of linear maps)

Answer 45

Let A represent the linear map T:V→V.
If A has a left inverse B such that BA=I. Then T has a left inverse T’:V→V represented by matrix B such that T’T=idv. However, if T’ is a left inverse, T’ must be a unique two-sided inverse T^(-1) (proved earlier) so TT’=idv.
The matrix for TT’ is AB so AB=I=BA so B is a two-sided inverse for A
Same proof for right inverse

Question 46

Change of Basis Theorem
Let V, W be finite-dimensional vector spaces over F.
Let T:V→W be linear.
Let v1,…,vn and v’1,…,v’n be bases for V.
Let w1,…,wm and w’1,…,w’m be bases for W.
Let A=(aij)∈Mmxn(F) be the matrix for T wrt. v1,…,vn and w1,…,wm.
Let B=(bij)∈Mmxn(F) be the matrix for T wrt. v’1,…,v’n and w’1,…,w’m.
Take pij.qij∈F such that v’i=sum of (pjivj) from j=1 to n and w’i’=sum of (qjiwj) from j=1 to m.
Let P=(pij)∈Mnxn(F) and Q=(qij)Mmxm(F).
Then B=Q^(-1)AP.
(Thm 45)

Answer 46

First take Q to be invertible and set up Q^(-1)=(r_ij)
so that wi=sum(rjiw’j) from j=1 to m

The rest follows quite nicely. You’re trying to show what B equals so start with T(v’i) as that’s what B represents.

Question 47

Take A∈M_mxn (F), let r=colrank(A).
Then there are invertible matrices P∈Mnxn(F) and Q∈Mmxm(F) such that Q^(-1)AP has the block form
( Ir 0rxs )
( 0txr 0txs )

where s=n-r and t=m-r.
(Prop 47)

Answer 47

Consider LA: Fcol^n→Fcol^m (which has matrix A wrt. Standard bases), and find suitable bases for domain and codomain with respect to which the matrix for L_A has the required form.

Find the rank and nullity of LA (considering rank=colrank(A)). Take a basis of kerLA and extend it to a basis of the domain.

You can then find a basis for the image and extend that to a basis for the codomain

Then consider each basis vector of the domain under the transformation and you get a matrix of the required form

Then change of basis theorem then shows that there are change of basis matrices P and Q that give the result

Question 48

Let A be an m x n matrix.
Then colrank(A)=rowrank(A) (Thm 49)

Answer 48

State that there exists Q, P such that B=Q^(-1)AP where B is in the block form.
rowrank(Q^(-1)AP)=rowrank(A), 
colrank(Q^(-1)AP)=colrank(A).
But rowrank(B)=colrank(B)=r. 
So rowrank(A)=r=colrank(A)

Question 49

Let A be an m x n matrix
Let x be the n x 1 column vector of variables x1,…,xn.
Let S be the solution space of the system Ax=0 of m homogeneous linear equations in x1,…,xn, that is,
S={v∈ n-colvectors :Av=0}. Then dimS=n-colrankA
(Prop 50)

Answer 49

See from theorem that S is the kernel of LA. So consider LA: n-colvectors → m-colvectors

Considering the standard basis e1,…,en of n-colvectors. Im(LA) is spanned by Ae1,…,Aen. Since Aei is the ith column of A,
Im(LA )= colspace(A) ⇒ rank(LA )=colrank(A)

Then by rank-nullity n = null(LA )+rank(LA ) = dim⁡(S)+colrank(A)

Question 50

Let V be a finite-dimensional vector space over F.
Let be a bilinear form on V.
Let v1,…,vn be a basis for V. Let A∈Mnxn(F) be the associated Gram matrix.
For u,v∈V,let x=(x1,…,xn )∈F^n and y=(y_1,…,y_n)∈F^n be the unique coordinate vectors such that
u=x1v1,…,xnvn and
v=y1v1,…,ynvn.
Then <u> =xAy^T
(Prop 51).</u>

Answer 50

Just write <u> in terms of the basis. Then use linearity and the entries of the gram matrix and you get the answer eventually</u>

Question 51

Let V be a finite-dimensional real inner product space.
Take u∈V{0}.
Define u^⊥≔{v∈V: =0}. Then u^⊥ is a subspace of V, and dim⁡(u^⊥ )=dim⁡(v)-1 and V=Span(u)⨁u^⊥. (Prop 52)

Answer 51

Consider f:V→R given by f(v)=.
f is linear since is bilinear.
Then since Im(f)≤R it can be shown rank(f)=1. Then rank-nullity

Then show span(u)∩u^⊥={0} and since dim⁡(span(u))+dim⁡(u^⊥) = dim⁡(V),
V=span(u)⨁u^⊥.

Question 52

Let {v1,…,vn} be an orthonormal set in an inner product space V.
Then v1,…,vn are linearly independent. (Lemma 53)

So if V is n-dimensional v1,…,vn are a basis

Answer 52

As in all linear independent proofs consider 0=α1v1+⋯+αnvn and show αi=0 ∀i

Consider 0=<0,vi> ∀i. Plug in the above and get the result.

Question 53

Let V be an n-dimensional real inner product space.

Then there is an orthonormal basis v1,…,vn of V. (Theorem 54)

Answer 53

Proof by induction on n.
n=0 trvial.
n=1 take v∈V.Let v1=v/‖v‖ . Show v1 is an orthonormal basis.

Take n=n. Define v1 in the same way. Consider U=v1^⊥ which is n-1-dimensional. U is an inner product space as you can restrict to U×U

So there is an orthonormal basis for U, v2,…,vn. Show this and v1 is an orthonormal basis for V

Question 54

Take X∈Mnxn(R). Consider R^n equipped with the usual inner product =x⋅y.
The following are equivalent:
(i) XX^T=In
(ii) X^TX=In
(iii) The rows of X form an orthonormal basis of R^n
(iv) The columns of X form an orthonomal basis of Rcol^n
(v) For all x,y∈R^n,we have xX⋅yX=x⋅y

(Lemma 55)

Note (v) says that the right multiplication map of an orthogonal matrix preserves the dot product (and such preserves length and angle). It is therefore an isometry as we already know.

Answer 54

(i) ⇔(ii) shown earlier with linear maps
(i) ⇔(iii) Say the rows of X are x1,…,xn. The (i,j) entry of XX^T is xi⋅xj=δij since XX^T=In
(ii) ⇔(iv) Similar to above
(i) ⇒(v) Consider xX∙yX=(xX)(yX)^T=xXX^Ty^T=xy^T=x⋅y
(v) ⇒(iii) Let e1,…,en be the standard basis of R^n. Then e1X is the ith row of X. We have eiX⋅ejX=ei⋅ej=δij. So e1X,…,enX is an orthonormal set and therefore an orthonormal basis.

Question 55

Cauchy-Schwarz Inequality –
Let V be a real inner product space. Take v1,v2∈V. Then
|| ≤ ‖v1‖‖v2‖, with equality iff v1,v2 are linearly dependent. (Thm 56)

Answer 55

If v1 or v2=0. Then inequality clear, assume v1,v2≠0.

For t∈R, consider ‖tv1+v2‖^2=. This gives a quadratic. Since always positive (positive definite) the discriminant is always 0 or less. This gives result

If equality, discriminant is 0 so there is a repeated root. So there is an α∈R so that ‖αv1+v2‖=0. By positive-definiteness, αv1+v2=0 so v1,v2 linearly dependent