Pre.10.11.2023

INDEPENDENT COLUMNS AND MATRICES Math 208: Linear Algebra By Prof. Sara Billey https://en.wikipedia.org/wiki/Arrangement_of_hyperplanes

Warm up Fill a 5x5 matrix with 0's and 1's as follows. Flip a coin once for each entry, Heads=1, Tails=0. If you run this experiment many times, what percentage of the time will the columns of the matrix be independent? Here's one example 0 1 1 0 1 1 1 0 1 1 0 0 1 0 0 1 1 1 1 0 0 0 0 1 0 ↓ for Ix , 242 , 31 ....

Announcements We are finishing up Chapter 2 today. Next up: Chapter 3 Section 2! Comments/grades on Gradescope? S

Outline • Last time: • Linear independence of sets of vectors • Linear dependence of sets of vectors • Today: • Echelon Test for Independent Vectors • Unifying Theorem (Thm. 2.21 in textbook) • Rank of a Matrix • The Algebra of Matrices

Spanning Sets • Def: A vector b is in span{ ! ! , ! " , ..., ! # } if and only if there exists scalars # ! , # " , ... , # # ∈ ℝ such that # ! ! ! + ⋯ + # # ! # = b So, given b and ! ! , ! " , ..., ! # , we test membership by solving the linear system of equations ) ! ! ! + ⋯ + ) # ! # = b The vector 0 is always in the span of any set of vectors.

Independent Vectors Def: The collection ! ! , ! " , ..., ! # in ℝ $ is independent if the only solution to ) ! ! ! + ⋯ + ) # ! # = 0 is ) ! = 0, ) " = 0, ... , ) # = 0 (the trivial solution). Equivalently, no ! % is a linear combination of the others. Equivalently, no ! % is in the span of the others. Equivalently, the dimension of the span { ! ! , ! " , ..., ! # } is m.

Independent Sets of Vectors • Theorem: Let S= { ! ! , ! " , ..., ! # } be vectors in ℝ $ . • Then the following are equivalent: 1. S is an independent set. 2. The only solution to ) ! ! ! + ⋯ + ) # ! # = 0 is ) ! = 0, ) " = 0, ... , ) # = 0 ( the trivial solution). 3. No ! % is a linear combination of the others. 4. No ! % is in the span of the others. 5. The dimension of the span { ! ! , ! " , ..., ! # } is m.

Dependent Sets of Vectors • Theorem: Let S= { ! ! , ! " , ..., ! # } be vectors in ℝ $ . • Then the following are equivalent: 1. S is a dependent set. 2. 3. 4. 5.

Numerology • Fact: If S= { ! ! , ! " , ..., ! # } is a subset of ℝ $ , then the dimension of span { ! ! , ! " , ..., ! # } ≤ n, and greater than or equal to 0. • It is possible that m ≥ n, but this does not guarantee the span is n-dimensional. • Fact : If S= { ! ! , ! " , ..., ! # } is subset of ℝ $ and m>n, then S is (choose one: independent or dependent).

Spanning Sets of Vectors • Theorem: Let S= { ! ! , ! " , ..., ! & } be vectors in ℝ $ . Let A=[ ! ! ! " . ... ! & ]. Then the following are equivalent: 1. S spans ℝ $ . 2. For every vector b in ℝ $ , the vector equation ) ! ! ! + ⋯ + ) # ! # = b has at least one solution. 3. The matrix equation A x = b has at least one solution. - TFAE - Examples :

Echelon Test for Spanning Sets Theorem: Assume ! ! , ..., ! # are vectors in ℝ $ . Let A be the matrix with columns ! ! , ..., ! # . Let B be a matrix equivalent to A that is in echelon form. Then ! ! , ..., ! # spans ℝ $ if and only if B has a pivot in every row .

Echelon Test for Independent Sets Theorem: Assume ! ! , ..., ! " are vectors in ℝ # . Let A be the matrix with columns ! ! , ..., ! " . Let B be a matrix equivalent to A that is in echelon form. Then ! ! , ..., ! " are independent if and only if B has a pivot in every column . Why?

Example : Is there a value for a such that 5) it . (E) . (i) ) are linearly dependent ? What do you expect for a random c ?

Example : Is there a value for a such that 5) it . (E) . (i) ) are linearly dependent ? Yes x(e) i (it(i)-o. .. ) (i) : () socio otrivial A = 8 form

A = = E. I I R - R , &R2 R - R , R3 ! I

2 - 12 eg : A = )- : " I = B c - Y 8 100 pivots ? By Echelon Test for Linean Indesudue , Ei , z , iss are linealy in depudt Es E there exist - solutions NAX= 8 1 BY = 8 Es

By Echelon Test for Linean Indesudue , [ Ei , z , iss are linealy in depudt B = : ? ] dependent I Es E> there exist solution NAX = 8 1 1 BY = 8 Es

Echelon Test for Independent Sets Theorem: Assume ! ! , ..., ! " are vectors in ℝ # . Let A be the matrix with columns ! ! , ..., ! " . Let B be a matrix equivalent to A that is in echelon form. Then ! ! , ..., ! " are independent if and only if B has a pivot in every column . Why? If B has a pivot in every column, then A x =0 has a unique solution. So, by definition of independent sets ! ! , ..., ! " are independent. On the other hand, ...If B has a column with no pivot, then A x =0 has a free variable. Therefore, it will have an infinite number of solutions so ! ! , ..., ! " are dependent. -

Nicest Possible Case 0 1101 11011 00 100 11 10 0 0 0 10

The Unifying Theorem • Theorem: Let S= { ! ! , ! " , ..., ! & } be vectors in ℝ $ . Let A=[ ! ! ! " . ... ! & ]. Then the following are equivalent: 1. Dimension(Span { ! ! , ! " , ..., ! & } ) =n 2. S spans ℝ $ . 3. S is linearly independent. 4. A x = b has a unique solution for all b in ℝ $ Why?

The Unifying Theorem • Theorem: Let S= { ! ! , ! " , ..., ! # } be vectors in ℝ $ . • Let A=[ ! ! ! " . ... ! # ]. Then the following are equivalent: 1. S spans ℝ $ . 2. Dimension(Span { ! ! , ! " , ..., ! # } ) =n 3. S is linearly independent. 4. A x = b has a unique solution for all b in ℝ $ Why? 4 ⟹ 3: A x = b has a unique solution for all b in ℝ ! implies A x = 0 has only one solution. 3 ⟹ 2: S is linearly independent implies Dim(Span { ! ! , ! $ , ..., ! % } ) =n 2 ⟹ 1: Dim(Span{ $ " , $ # , ..., $ $ }) =n implies Span { $ " , $ # , ..., $ $ } = ℝ ! Since ℝ ! has no other n dimensional subspaces.

• The last step is to show 1 ⟹ 4 to complete the logical circle of implications. should we add anything more to Unifying Throu ?

Rank of a Matrix • Def: The rank of a matrix with n rows and n columns is the dimension of the span of its columns. • So by the Unifying Theorem, rank(A) =n iff the columns of A are independent and A is nxn matrix.

• Thinking Exercise: Show the rank of a matrix A is also the dimension of the span of the columns of A t =Transpose(A).

Recent Vocabulary • The span of a set of vectors • Dependent vectors • Independent vectors • The zero vector 0 in ℝ $ • Nonzero vectors in ℝ $ • Rank of a matrix