Linearly independent set is not bigger than a span

Dependencies:

  1. Vector Space
  2. Linear independence
  3. Span
  4. Matrix
  5. Homogeneous linear equations with more variables than equations

Let $U = [u_1, u_2, \ldots, u_m]$ and $V = [v_1, v_2, \ldots, v_n]$ be sequences of vectors from a vector space over field $F$. If $U \subseteq \operatorname{span}(V)$ and $m > n$, then $U$ is linearly dependent.

Proof

Since $U \subseteq \operatorname{span}(V)$, let $u_i = \sum_{j=1}^n a_{i, j}v_j$. Let $A$ be an $m$-by-$n$ matrix over field $F$ where $A_{i, j} = a_{i, j}$.

Consider the system of equations $A^Tx = 0$. This is a system of $n$ equations in $m$ variables. Since $n < m$, there exists a non-zero solution $b$, i.e., $b \in F^m - \{0\}$ such that $A^Tb = 0$. Hence, \[ \sum_{i=1}^m b_iu_i = \sum_{i=1}^m \sum_{j=1}^n b_ia_{i,j}v_j = \sum_{j=1}^n (A^Tb)_jv_j = 0. \] Therefore, $U$ is linearly dependent.

Dependency for:

  1. Dimension of a polyhedron
  2. span(A)=span(B) & |A|=|B| & A is linindep ⟹ B is linindep
  3. Dimension of a set of vectors
  4. Linearly independent set can be expanded into a basis
  5. Maximally linearly independent iff basis
  6. Basis of a vector space
  7. Minimally spanning iff basis
  8. Spanning set of size dim(V) is a basis
  9. A set of dim(V) linearly independent vectors is a basis
  10. A matrix is full-rank iff its rows are linearly independent
  11. Vector matroid

Info:

Transitive dependencies:

  1. /linear-algebra/vector-spaces/condition-for-subspace
  2. /linear-algebra/matrices/gauss-jordan-algo
  3. /sets-and-relations/equivalence-relation
  4. Group
  5. Ring
  6. Polynomial
  7. Integral Domain
  8. Comparing coefficients of a polynomial with disjoint variables
  9. Field
  10. Vector Space
  11. Linear independence
  12. Span
  13. Semiring
  14. Matrix
  15. Stacking
  16. System of linear equations
  17. Product of stacked matrices
  18. Matrix multiplication is associative
  19. Reduced Row Echelon Form (RREF)
  20. Matrices over a field form a vector space
  21. Row space
  22. Elementary row operation
  23. Every elementary row operation has a unique inverse
  24. Row equivalence of matrices
  25. Row equivalent matrices have the same row space
  26. RREF is unique
  27. Identity matrix
  28. Inverse of a matrix
  29. Inverse of product
  30. Elementary row operation is matrix pre-multiplication
  31. Row equivalence matrix
  32. Equations with row equivalent matrices have the same solution set
  33. Homogeneous linear equations with more variables than equations
  34. Rank of a homogenous system of linear equations
  35. Rank of a matrix
  36. Basis of a vector space