MA106 - Linear Algebra Theorems

Question 1

Every matrix can be brought to row reduced form by elementary row transformations.

Answer 1

Need an algorithm, where:
After Termination the resulting matrix has Row Reduced Form
The algorithm terminates after finitely many steps

Call (i,j) the Pivot Position and aim the Pivot Entry. Begin with (i,j)=(1,1)

1. if akj = 0 for all k ≥ i, move Pivot to (i, j+1)
   Repeat Step 1, terminate if j=n
2. If aij = 0 but akj≠ 0 for some k > i, apply (R2) and swap ri, rk
3. Now aij≠ 0, if aij≠1, apply (R3) to multiply ri by 1/aij
4. aij=1, If any k≠i, akj≠0, use (R1) to subtract akjxri from rk
5. akj=0 ∀ k≠i. Terminate if i=m or j=n, otherwise move Pivot to (i +1, j+1) and go back to Step 1

Question 2

By Applying Elementary Row & Column operations, a matrix can be brought into the form of Identity in top left surrounded by 0

Answer 2

Use Elementary Row operations to row reduce A. Hence ai,c(i)=1.
Use (C1) ∀ aij≠0 with j≠ c(i) to replace cj with aij-c(i).
∀ i starting from i = 1, exchange ci and cc(i), putting all the zero columns at
the right-hand side.

Question 3

The vectors v1,v2,…,vn ∈ V are linearly dependent iff either v1 = 0 or, for some r, the vector vr is a linear combination of v1, . . . , vr−1.

Answer 3

If v1=0, set a1=1, and ai=0 ∀ i>1. Hence the linear combination equals 0

If vr is a linear combination,
vr = α1v1 +···+αr−1vr−1
α1v1 + ··· + αr−1vr−1 − 1vr = 0

Conversely, suppose that v1,v2,…,vn ∈V are linearly dependent. Let r be maximal with ar≠0.
then α1v1 +α2v2 +···+αrvr = 0
If r=1, α1v1 = 0 which is only possible if v1=0
Otherwise
vr =−α1/αr. v1−···−αr−1/αr. vr−1.

Question 4

The vectors v1,…,vn form a basis of V if and only if every v ∈ V can be written uniquely as v = α1v1 + · · · + αnvn; that is, the coefficients α1, . . . , αn are uniquely determined by the vector v.

Answer 4

Suppose there are other scalars βi ∈ K. Write out a vector v as a linear combination of both.
Let 0= v-v then show ai =βi.

Conversely,
Suppose α1v1+α2v2+···+αnvn =0, then
Ifα1v1+α2v2+···+αnvn = 0v1 + 0v2 +…
Uniqueness implies a1=…=an=0. hence they are linearly independent, hence form a basis.

Question 5

Suppose that the vectors v1,v2,…,vn,w span V and that w is a linear combination of v1,…,vn. Then v1,…,vn span V.

Answer 5

any vector is a linear combination (including w). w is a linear combination of vi.
Substitute into first linear combination.

Question 6

Suppose that the vectors v1, . . . , vr span the vector space V . Then there is a subsequence of v1,…,vr which forms a basis of V.

Answer 6

Sift v1,…,vr. Hence remaining vectors Span V.
No remaining are 0 or a linear combination
Hence they are linearly independent.
They form a basis

Question 7

Let V be a vector space over K which has a finite spanning set, and suppose that the vectors v1, . . . , vr are linearly independent in V . Then we can extend the sequence to a basis v1,…,vn of V, where n≥r.

Answer 7

Suppose w1,…,wq is a spanning set.
Sift v1,…,vn,w1,…,wq. This results in a basis for V.
v1,…,vr are linearly independent, hence no vi removed. Hence basis contains them

Question 8

What is the Exchange Lemma?

Answer 8

Suppose that vectors v1,…,vn span V and that vectors w1, . . . , wm ∈ V are linearly independent. Then m ≤ n.

Question 9

Suppose that vectors v1,…,vn span V and that vectors w1, . . . , wm ∈ V are linearly independent. Then m ≤ n.

Answer 9

Place one wi in front of v1,…,vn and sift each time.
Since vj span V and wi are linearly independent, at least one vj is deleted.
In total m wi vectors are added, with at least 1 vj removed each time. Hence m ≤ n.

Question 10

Let V be a vector space of dimension n over K. Then any n vectors which span V form a basis of V, and no n−1 vectors can span V.

Answer 10

After sifting, remaining vectors form a basis.

Hence there must be n=dim(V) vectors.

Question 11

Let V be a vector space of dimension n over K. Then any n linearly independent vectors form a basis of V and no n+1 vectors can be linearly independent.

Answer 11

Any linearly independent set is contained in a basis. But there must be n=dim(V) vectors in the extended set.

Question 12

If W1 and W2 are subspaces of V then so is W1 ∩ W2.

Answer 12

Show it is closed under addition and scalar multiplication. (Hint: Start with 2 elements of W1∩ W2)

Question 13

If W1, W2 are subspaces of V then so is W1 + W2. In fact, it is the smallest subspace that contains both W1 and W2.

Answer 13

Show it is closed under addition & Scalar multiplication (Hint: Start with 2 elements of W1+W2)
Any subspace of V containing W1 and W2 must contain W1 + W2 hence it is the smallest

Question 14

Let V be a finite-dimensional vector space, and let W1,W2 be sub- spaces of V . Then
dim(W1 + W2) = dim(W1) + dim(W2) − dim(W1 ∩ W2).

Answer 14

Find what is a subset of which. Define a basis for W1 ∩ W2 and extend them to form W1 and W2 separately. Show the resulting bases Span and are linearly independent.

Question 15

Let T:U→V be a linear map. Then

(i) T(0U)=0V;
(ii) T(−u) = −T(u) for all u ∈ U.

Answer 15

Definition

i: T(0U)=T(0U +0U)=T(0U)+T(0U), Hence T(0U)=0V
ii. a=-1 in definition of T

Question 16

Let U,V be vector spaces over K, let S be a basis of U and let f:S→V be any function assigning to each vector in S an arbitrary element of V . Then there is a unique linear map T:U→V such that for every s∈S we have T(s)=f(s).

Answer 16

Let u ∈ U, u = α1s1 + · · · + αnsn
If T exists:
T(u)=T(α1s1 +···+αnsn)=α1f(s1)+···+αnf(sn), Hence it would be unique.

Question 17

Let U,V be vector spaces over K of dimensions n,m, respectively. Then, for a given choice of bases of U and V , there is a one-one correspondence between the set HomK(U,V) of linear maps U → V and the set Km,n of m×n matrices over K.

Answer 17

any linear map T : U → V determines an m × n matrix A over K.

Conversely, let A=(aij) be an mxn matrix over K. Then there is one Linear T: U→V. with T(ej)=􏰕Sum from 1 to m=aijfi
Hence it is a one to one correspondence.

Question 18

Let T : U → V be a linear map. Let the matrix A = (aij ) represent T with respect to chosen bases of U and V , and let u and v be the column vectors of coordinates of two vectors u ∈ U and v ∈ V , again with respect to the same bases. Then T(u)=v if and only if Au=v.

Answer 18

Summation Proof

Question 19

1. Let T1, T2 : U → V be linear maps with m × n matrices A, B respectively. Then the matrix of T1 + T2 is A + B.
2. LetT:U→V be a linear map with m×n matrix A and let λ∈K be a scalar. Then the matrix of λT is λA.

Answer 19

Use Definitions.

Question 20

Let T1: V → W be a linear map with l×m matrix A = (aij) and let T2: U → V be a linear map with m×n matrix B = (bij). Then the matrix of the composite map T1T2 : U → W is AB.

Answer 20

Summation Proof.

Question 21

Let T : U → V be a linear map. Then

(i) im(T) is a subspace of V ;
(ii) ker(T) is a subspace of U.

Answer 21

Show they are closed under addition and scalar multiplication.

Question 22

What is the Rank-Nullity Theorem?

Answer 22

Let U, V be vector spaces over K with U
finite-dimensional, and let T : U → V be a linear map. Then:
rank(T) + nullity(T) = dim(U).

Question 23

Let U, V be vector spaces over K with U
finite-dimensional, and let T : U → V be a linear map. Then:
rank(T) + nullity(T) = dim(U).

Answer 23

ker(T) is a subspace hence is also finite-dim.
Define a basis of Ker(T) ei, extend it to a basis of U. Show dim(im(T))= size of extension.
T(e1)….T(f1)…. span im(T). but T(ei)=0.
Then left with T(fi)
Suppose for contradiction they are linearly dependent. Can prove they form a Basis of im(U).

Question 24

Let T : U → V be a linear map, and suppose that dim(U ) = dim(V ) =n. T
hen the following properties of T are equivalent:
(i) T is surjective;
(ii) rank(T ) = n;
(iii) nullity(T ) = 0;
(iv) T is injective;
(v) T is bijective;

Answer 24

i implies im(T)=V, which give ii.
Converse, dim(im(T))=dim(V), same basis. im(T)=V.
Rank Nullity- ii double implication iii
Nullity(T)=0, hence ker(T)={0}. iv gives iii
SupposeT(u)=T(u’), T(u-u’)=0, hence u-u’ in ker(T) and are equal. T is injective
v is equivalent to i and iv.

Question 25

Let T : U → V be a linear transformation, and let e1,…,en be a basis of U. Then the rank of T is equal to the size of the largest linearly independent subset of T(e1),…,T(en).

Answer 25

im(T) spanned by T(ei), hence some subset is a basis of im(T).
This has size dim(im(T))=rank(T). No larger subset can be linearly independent.

Question 26

Suppose that the linear map T has matrix A. Then rank(T ) is equal to the column rank of A.

Answer 26

the columns c1, . . . , cn of A are precisely the column vectors of coordinates of the vectors T(e1),…, T(en) wrt chosen basis.
rank(T) = size of largest linearly independent subset of these.
This is Column rank by definition.

Question 27

Applying elementary row operations (R1), (R2) or (R3) to a matrix does not change the row or column rank. The same is true for elementary column operations (C1), (C2) and (C3).

Answer 27

Row Rank of A is the dim(rowspace(A)), the space of linear combinations λ1r1 + · · · + λmrm of the rows of A. (R1), (R2) and (R3) do not change this space, so they do not change the row-rank.

columns linearly independent if
x1c1 +x2c2 +···+xscs = 0
Expand these column vectors to make a system of equations. Then Check each (Ri) on them to see if it affects the solution, hence the linear dependence.
Column operation proof the same with col/row swapped.

Question 28

Let s be the number of non-zero rows in the row and column reduced form of a matrix A. Then both row rank of A and column rank of A are equal to s.

Answer 28

elementary operations preserve ranks, can find both ranks in this form.
row space is precisely the space spanned by the first s standard vectors, dim=s.
Similarly column space dim=s

Question 29

The rank of a matrix A is equal to the number of non-zero rows after reducing A to upper echelon form.

Answer 29

Show non-zero rows linearly independent by contradiction.

Question 30

Let A be a matrix of a linear map T. A linear map T is invertible if and only if its matrix A is invertible. The inverses T−1 and A−1 are unique.

Answer 30

Since the inverse map of a bijection is unique, T −1 is unique. Under the bijection between matrices and linear maps, A−1 must be the matrix of T−1. Thus, A−1 is unique as well.

Question 31

If A and B are invertible n × n matrices, then AB is invertible, and (AB)−1 = B−1A−1.

Answer 31

ABB^−1A^−1 = B^−1A^−1AB = In.

Question 32

The row reduced form of an invertible n × n matrix A is In.

Answer 32

If invertible, rank=n. Let B=(bij) be its row reduced form.

bic(i)=1 for 1≤i≤ n where c(1)

Question 33

An invertible matrix is a product of elementary matrices.

Answer 33

Inverses of E E(n)1−λ,i,j, E(n)2i,j and E(n)3λ−1,i
if ErEr−1 ···E1A = In then:
A = (Er Er-1 …E1 )−1 = E1^−1E2^−1 …Er^−1,

Question 34

Let A be an n × n matrix. Then
(i) the homogeneous system of equations Ax = 0 has a non-zero solution if and
only if A is singular;
(ii) the equation system Ax = b has a unique solution if and only if A is non-
singular.

Answer 34

The solution set of the equations is exactly nullspace(A).
nullspace(A ) = ker(T ) = {0} ⇐⇒ nullity(T ) = 0 ⇐⇒ T is non-singular,

If A is singular then its nullity is greater than 0 and so its nullspace is not equal to {0}, and contains more than one vector. Either there are no solutions, or the solution set is x + nullspace(A) for some specific solution x, in which case there is more than one solution. Hence there cannot be a unique solution when A is singular. Conversely, if A is non-singular, then it is invertible by Theorem 10.2, and one solution is x = A−1b. Since the complete solution set is then x + nullspace(A), and
nullspace(A) = {0} in this case, the solution is unique.

Question 35

Elementary row operations affect the determinant of a matrix as follows.
(i) det(In) = 1.

(ii) Let B result from A by applying (R2) Then det(B) =− det(A).
(iii) If A has two equal rows then det(A) = 0.
(iv) Let B result from A by applying (R1) Then det(B) = det(A).
(v) Let B result from A by applying (R3) Then det(B) = λ det(A).

Answer 35

Use definition of Determinant.

Question 36

If A = (aij) is upper triangular, then det(A) = a11a22 …ann is the
product of the entries on the main diagonal of A.

Answer 36

apply row operations (R1) to reduce the matrix to the diagonal matrix with same aii on main diagonal.
Use:
(i) det(In) = 1.
(v) Let B result from A by applying (R3) Then det(B) = λ det(A).

Question 37

Let A = (aij) be an n × n matrix. Then det(AT) = det(A).

Answer 37

Use definition of determinant. and Inverse permutation.

Question 38

For an n × n matrix A, det(A) = 0 if and only if A is singular.

Answer 38

A can be made to row reduced echelon form. rank(A) not affected hence neither is whether or not it is singular. (When Rank(A)

Question 39

If E is an n×n elementary matrix, and B is any n×n matrix, then det(EB) = det(E) det(B).

Answer 39

Determine det(EB), then let B=In to find individual det(Ei)

Question 40

For any two n × n matrices A and B, we have det(AB) = det(A) det(B).

Answer 40

If det(A)=0 then rank(A)

Question 41

Let A be an n × n matrix.
det(A)=ai1ci1 +ai2ci2 +···+aincin

det(A)=a1jc1j +a2jc2j +···+anjcnj

Answer 41

Use Definition of Determinant.

Question 42

A adj(A) = det(A)In = adj(A) A

Answer 42

….

Question 43

If det(A) ̸= 0, then A^−1 = 1/det(A). adj(A).

Answer 43

…

Question 44

Let A be an n × n matrix. Then λ is an eigenvalue of A if and only if det(A − λIn) = 0.

Answer 44

…

Question 45

Similar matrices have the same characteristic equation and hence
the same eigenvalues.

Answer 45

…

Question 46

Let T : V → V be a linear map. Then the matrix of T is diagonal with respect to some basis of V if and only if V has a basis consisting of eigenvectors of T.
Equivalently, let A be an n × n matrix over K. Then A is similar to a diagonal matrix if and only if the space Kn,1 has a basis of eigenvectors of A.

Answer 46

…

Question 47

Let λ1,…,λr be distinct eigenvalues of T: V → V, and let v1, . . . , vr be corresponding eigenvectors. (So T (vi) = λivi for 1 ≤ i ≤ r.) Then v1,…,vr arelinearlyindependent.

Answer 47

…

Question 48

If the linear map T : V → V (or equivalently the n × n matrix A) has n distinct eigenvalues, where n = dim(V ), then T (or A) is diagonalisable.

Answer 48

…