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?

Question

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$?

Please give me the correct answer for this!!

Answer 1

Suppose for a contradiction that $n<m$ 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

Answer 2

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$.