# How to show that the dimension of the set $A$ is less than or equal to the dimension of the set $B$ under the following conditions?

Let $A=\{a_1\ldots,a_m \}$ be a set of linearly independent vectors. Suppose that each $a_j$ $(j=1,\ldots,m)$ can be written as a linear combination of vectors in the set $B=\{b_1,\ldots,b_n\}$.

Then how to show that $m \le n$?

I have tried as follows:

Since $a_j \in A$, we have $a_j \in \operatorname{span} (B)$.

Then we have $$A \subseteq \operatorname{span} (B).$$

Therefore, can we say that $m \le n$?

• I think you have a typo. Do you mean your set $B$ to be $B=\{b_1,\ldots,b_{\textbf{n}}\}$? (that is, with $n$ elements, instead of with $s$ elements as you wrote it?) Commented Mar 16, 2016 at 19:02
• I corrected it. Thanks! Commented Mar 16, 2016 at 19:04

Suppose for a contradiction that $$n and write the equations:

\begin{align*}a_1&=\alpha_{11}b_1+\ldots+\alpha_{1n}b_n\\\vdots & \hspace{2cm}\vdots\\ a_m&=\alpha_{m1}b_1+\cdots +\alpha_{mn}b_n\end{align*}

From here we start a process that will allow us to obtain coefficients $$\gamma_1,\ldots,\gamma_{n+1}$$ not all zero such that $$\gamma_1 a_1+\cdots + \gamma_{n+1}a_{n+1}=0$$, contradicting the fact that $$\{a_1,\ldots,a_{n+1}\}$$ are linearly independent.

We do $$n$$ steps, and each step have 3 parts: "substituting", "renaming", "separating".

Step 1:

• In this step we do not substitute.
• Rename the vectors $$b_1,\ldots,b_n$$ such that $$\alpha_{11}\neq 0$$.
• We have $$\displaystyle{a_1=\alpha_{11} b_1 + \sum_{j=2}^n \alpha_{1j}b_j}$$, from which we obtain $$b_1=\dfrac{1}{\alpha_{11}}\left(a_1-\sum_{j=2}^{n} \alpha_{1n}b_n\right)$$

Step 2:

• Replace $$b_1$$ in the equation $$a_2=\alpha_{21}b_1+\cdots+\alpha_{2n}b_n$$.
• Rename the coefficients and the $$b_i's$$ to obtain $$a_2=\beta_{21}a_1+\beta_{22}b_2+\cdots \beta_{2n}b_n$$ with $$\beta_{22}\neq 0$$. Note that $$b_1$$ is not mentioned in this equation because we substitute it with a linear combination of the vectors $$a_1,b_2,\ldots,b_n$$. Also, it is not possible that all coefficients of $$b_2,\ldots,b_n$$ are zero because otherwise, $$a_2=\beta_{21}a_1$$ which would contradict that $$a_1,a_2$$ are linearly independent.
• Separate $$b_2$$: $$b_2=\dfrac{1}{\beta_{22}}\left(a_2-\beta_{21}a_1-\sum_{j=3}^n\beta_{2j}b_j\right)$$

$$\vdots$$

Step $$k+1$$:

• Replace $$b_1,b_2,\ldots,b_k$$ in terms of $$a_1,\ldots,a_k,b_{k+1},\ldots,b_n$$ in the equation $$a_{k+1}=\alpha_{k+1,1}b_1+\cdots+\alpha_{k+1,n}b_n$$

• Rename the coefficients and the $$b_i's$$ ($$i=k+1,\ldots,n$$) to obtain $$a_{k+1}=\beta_{k+1,1}a_1+\beta_{k+1,2}a_2+\cdots+\beta_{k+1,k}a_k+\beta_{k+1,k+1}\cdots \beta_{k+1,n}b_n$$ with $$\beta_{k+1,k+1}\neq 0$$. Again, this is possible because if the coefficients of all $$b_i's$$ were zero, then it would contradict the fact that $$a_1,\ldots,a_{k+1}$$ are linearly independent.

• Separate:$$b_{k+1}=\dfrac{1}{\beta_{k+1,k+1}}\left(a_{k+1}-\sum_{j=1}^k \beta_{k+1,j}a_j - \sum_{j=k+2}^n\beta_{k+1,n}b_j\right)$$

After doing $$n$$ steps of this process, and substituting $$b_1,\ldots,b_n$$ in terms of $$a_1,\ldots,a_n$$ in the equation

$$a_{n+1}=\alpha_{n+1,1}b_1+\cdots + \alpha_{n+1,n}b_n$$

we obtain

$$a_{n+1}=\beta_{n+1,1}a_1+\cdots \beta_{n+1,n}a_n.$$

If we put $$\gamma_i=\beta_{n+1,i}$$ for $$i=1,\ldots,n$$, we finally obtain,

$$\gamma_1 a_1 + \cdots + \gamma_n a_n - a_{n+1}=0$$ which will contradict the fact that $$a_1,\ldots,a_{n+1}$$ are linearly independent.

This final contradiction allows us to conclude that $$m\leq n$$. QED

• @Falcon I hope is clear. Do not hesitate to ask me if you do not understand anything. Commented Mar 16, 2016 at 21:01
• Thank you very much for the answer! I want know that, if $m=n$ how to conclude that the vectors in $B$ are linearly independent ? Commented Mar 17, 2016 at 4:56
• @Falcon Using the argument, after the $n$-th step you find equations that tell you how to write $b_1,\ldots,b_n$ as linear combinations of $a_1,\ldots,a_n$. Thus, if $b_1,\ldots,b_n$ were not linearly independent, there is a linear combination $\alpha_1b_1+\cdots+\alpha_nb_n=0$ with not all $\alpha_i$ equal to zero. By substituting each $b_i$ in terms of $b_i$, we would find a linear combination of the $a_i$ that is equal to zero where not all its coefficients are zero. This contradicts the fact that the $a_i's$ are linearly independent. Commented Mar 17, 2016 at 6:55

You are almost there. Consider for the sake of contradiction that $m>n$ but you still have $A\subseteq$span$(B)$. Then, you have a set of $m>n$ vectors in a space spanned by $n$ vectors so the set $\{a_j\}$ must be linearly dependent, a contradiction to our assumptions so it must be that $m\leq n$.

• Your answer is a circular argument: Part of your argument is that "you have a set of $m>n$ vectors in a space spanned by $n$ vectors so the set $\{a_j\}$ must be linearly dependent" which is equivalent to the statement you want to prove. Commented Mar 16, 2016 at 19:41
• @Tony I want to know how you decided that the set $A$ is dependent when $m>n$. And also I want to know how you used the fact $A \subseteq span(B)$. Your answer is not clear. Please explain it clearly.
– Oily
Commented Mar 16, 2016 at 19:56
• Consider the span of $n$ vectors span$(b_n)$. This span is contained in some vector space, $V$, with dim$(V)\leq n$. Then, the set $A$ is a subset of $V$ and so has dimension less than or equal to the dimension of $V$ which is bounded above by $n$. Then, since $A$ cannot contain a set of linearly independent vectors with cardinality greater than the dimension of $A$, and since $m>n$, $a_m$ must be linearly dependent. Commented Mar 17, 2016 at 1:47