Number of indie vectors ##\leq ## cardinality of spanning set

In summary: So you could start by saying "Let ##u_1, \dots, u_n## be a minimal spanning set for the space. Then for every spanning set ##v_1, \dots, v_m##, with ##m > n##, we have the following contradiction..."In summary, the given statement is proven by assuming a minimal spanning set and any other spanning list, with a greater length, to show a contradiction. This implies that the length of every linearly independent list of vectors is less than or equal to the length of every spanning list.
  • #1
Terrell
317
26

Homework Statement


In a finite-dimensional vector space, the length of every linearly independent list of vectors is less than or equal to the length of every spanning list.
It's quite long :nb), hope you guys read through it. Thanks! :smile:

Homework Equations


N/A

The Attempt at a Solution


Let ##\{v_1, \cdots, v_m\}## be linearly independent and ##\{u_1, \cdots, u_m\}## spans V. Note that ##\{v_1, \cdots, v_m\} \subseteq \operatorname{span}(u_1, \cdots, u_n)## which implies ##\forall i=1,\cdots,m## ##v_i=\sum_{j=1}^{n}a_{j}u_{j}##. Suppose that ##n \lt m## and let ##v_1=\sum_{i=1}^{m}a_{i}u_{i}##,##\quad## ##v_2=\sum_{i=1}^{m}b_{i}u_{i}##,##\quad## ##\cdots##, ##\quad## ##v_3=\sum_{i=1}^{m}\eta_{i}u_{i}##. Observe that
\begin{align}
\delta_{1}v_1+\delta_{2}v_2+\cdots +\delta_{n}v_{n}=v_k; \quad k \in \{n+1,\cdots ,m\}\\
\Longleftrightarrow \delta_{1}(\sum_{i=1}^{m}a_{i}u_{i})+\delta_{2}(\sum_{i=1}^{m}b_{i}u_{i})+\cdots +\delta_n(\sum_{i=1}^{m}\eta_{i}u_{i}) &=v_k\\
\Longleftrightarrow \delta_1(a_{1}u_{1}+\cdots +a_{m}u_{m})+\delta_2(b_{1}u_{1}+\cdots +b_{m}u_{m})+\cdots +\delta_n(\eta_{1}u_{1}+\cdots +\eta_{m}u_{m}) &=v_k\\
\Longleftrightarrow (\delta_{1}a_{1}+\cdots +\delta_{n}\eta_{1})u_{1}+\cdots +(\delta_{1}a_{m}+\cdots +\delta_{n}\eta_{m})u_{m} &=v_{k}
\end{align}
Since ##\exists \xi_{i}\in\Bbb{F}## such that ##\xi_{1}u_1+\cdots +\xi_{m}u_m=v_{k}##, then by solving the following system of linear equations
\begin{align}
\delta_{1}a_{1}+\cdots +\delta_{n}\eta_{1} &= \xi_1\\
\vdots\\
\delta_{1}a_{m}+\cdots +\delta_{n}\eta_{m} &= \xi_{m}
\end{align}
we obtain the necessary ##\delta_{i}'s## so that ##\sum_{i=1}^{n}\delta_{i}v_{i}=v_k##. Since ##n \neq m##, there could either be non-unique solutions or no solutions. We consider the two scenarios.
Case 1: infinite solutions; By definition of a basis, ##\{v_1,\cdots ,v_n\}## cannot form a basis due to the required uniqueness of expressing ##v_k## with respect to the set of vectors ##\{v_1,\cdots ,v_n\}##. But ##\operatorname{span}(v_1, \cdots, v_n) \neq V## so it must be that ##\{v_1, \cdots , v_n\}## is not linearly independent. We have a contradiction.
Case 2: No solution; then ##v_k \notin \operatorname{span}(v_1, \cdots, v_n)## which implies ##\delta_{1}v_1 + \delta_{2}v_2 + \cdots + \delta_{n}v_n + \delta_{n+1}v_k = 0## if and only if all ##\delta_{i}'s## equal zero. Equivalently,
\begin{align}
& \Longleftrightarrow (\delta_{1}a_{1}+\cdots +\delta_{n}\eta_{1}+\delta_{n+1}\xi_{1})u_{1}+\cdots +(\delta_{1}a_{m}+\cdots +\delta_{n}\eta_{m}+\delta_{n+1}\xi_{m})u_{m} = 0\\
& \Longleftrightarrow \forall i=1,\cdots, m \quad \delta_{1}a_i+\cdots +\delta_{n}\eta_i+\delta_{n+1}\xi_i =0
\end{align}
But, if we let ##\delta_{n+1}=\frac{-(\delta_{1}a_i+ \cdots +\delta_{n}\eta_i)}{\xi_i}##, ##\forall i=1, \cdots, m##, then ##\exists \delta_i \neq 0## such that ##(\sum_{i=1}^{n}\delta_{i}v_i)+\delta_{n+1}v_k=0##. This implies the set of vectors ##\{v_1, v_2\cdots,v_n, v_k\}## is not linearly independent. We have another contradiction.

##\therefore## ##m \leq n##.o0)
 
Physics news on Phys.org
  • #2
It might be easier to assume that you have a set of m lin. independent vectors and a spanning set with n vectors, with m > n. If you get a contradiction (which should be easier to do than what you did), you're done.

Also, it looks like you have a typo in the first line of your proof. The two sets -- the linearly independent vectors and the spanning set, shouldn't have the same final index of m.
 
  • Like
Likes Terrell
  • #3
Mark44 said:
it looks like you have a typo in the first line of your proof.
Yes. It should be ##\{u_1,\cdots, u_n\}##
Mark44 said:
It might be easier to assume that you have a set of m lin. independent vectors and a spanning set with n vectors, with m > n.
I believe this is what I did. At line 2, my third sentence starts with suppose ##m \lt n##. Then I got a contradiction in the end. But as what you've probably already notice, my proof seems more complicated than it should be. So I have a feeling that I might have an incorrect use of contradiction. :nb)
 
  • #4
Terrell said:
Yes. It should be ##\{u_1,\cdots, u_n\}##

I believe this is what I did. At line 2, my third sentence starts with suppose ##m \lt n##.
Actually what you wrote is "Suppose that n < m..." which is correct for a proof by contradiction if your spanning set is ##\{u_1, u_2, \dots, u_n \}##
Terrell said:
Then I got a contradiction in the end. But as what you've probably already notice, my proof seems more complicated than it should be. So I have a feeling that I might have an incorrect use of contradiction. :nb)
Yes, your proof seems more complicated than it needs to be, in part because of the use of lots more letters than are needed.

For example, instead of having coefficients of ##a_i, b_i,## and ##\eta_i##, just use two subscripts. So ##v_i = \sum_{j = 1}^n a_{i~j}u_j##. If you write the equations for ##v_1, v_2, \dots, v_n## in the form of a matrix product, you have ##\vec v = A \vec u##, where A is a matrix with m rows and n columns.I think you can assume without loss of generality that the u vectors are a minimal spanning set; i.e., a basis for the space. Since you need to prove the given statement for every spanning list, it doesn't matter if you prove it for the smallest spanning set.
 
Last edited:
  • Like
Likes Terrell

FAQ: Number of indie vectors ##\leq ## cardinality of spanning set

What does "number of indie vectors" mean?

The term "indie vectors" refers to independent vectors, which are vectors that are not linearly dependent on each other. This means that no vector can be expressed as a linear combination of the other vectors. The "number of indie vectors" refers to the number of independent vectors in a set.

What is the cardinality of a spanning set?

The cardinality of a spanning set is the number of vectors in the set. A spanning set is a set of vectors that can be used to create any vector in a given vector space through linear combinations.

What does it mean for the number of indie vectors to be less than or equal to the cardinality of a spanning set?

This statement means that the number of independent vectors in a set is equal to or less than the number of vectors in a spanning set. In other words, the number of independent vectors cannot exceed the number of vectors needed to span the vector space.

Why is the number of indie vectors important?

The number of independent vectors is important because it is a measure of the dimensionality of a vector space. In other words, it tells us how many basis vectors are needed to span the space. This can help us understand the properties and behavior of the vectors in that space.

How is the number of indie vectors related to linear independence?

The number of independent vectors in a set is directly related to linear independence. If the number of indie vectors is equal to the cardinality of the spanning set, then the vectors are linearly independent. If the number is less than the cardinality, then there are linearly dependent vectors in the set.

Back
Top