# Linear dependence of set of linear combinations of linearly independent vectors

I came across this problem:

Given the set of linearly independent vectors $\{u,v,w\} \subseteq \mathbb{R}^n$, determine whether or not the following set of vectors is linearly dependent: $\{u-v-w, 2u+w, 3u+v+3w\}$

There's a theorem which says that if at least one of the vectors in a set is a linear combination of other vectors, then the set is linearly dependent. In this particular question, I had to go through all of the three vectors $\{u-v-w, 2u+w, 3u+v+3w\}$ and check whether any of them is a linear combination of others (and I think the answer is that the set is linearly independent).

But is there more efficient way of doing this? I tried checking linear dependence using matrix, that is, checking for a non-trivial solution of the following system:

$$\begin{bmatrix} (u_1-v_1-w_1) & (2 u_1 + w_1) & (3 u_1 + v_1 + 3 w_1) & 0\\ (u_2-v_2-w_2) & (2 u_2 + w_2) & (3 u_2 + v_2 + 3 w_2) & 0\\ & \vdots \\ (u_n-v_n-w_n) & (2 u_n + w_n) & (3 u_n + v_n + 3 w_n) & 0 \end{bmatrix}$$

But I have no idea how to do this because I don't know the components of the vectors $u, v, w$ and I don't know $n$.

## 3 Answers

Suppose $$\DeclareMathOperator{Null}{Null} \DeclareMathOperator{Span}{Span} \lambda_1\cdot(u-v-w)+\lambda_2\cdot(2u+w)+\lambda_3\cdot(3u+v+3w)=\mathbf 0\tag{1}$$ Then $$(\lambda_1+2\lambda_2+3\lambda_3)\cdot u + (-\lambda_1+\lambda_3)\cdot v + (-\lambda_1+\lambda_2+3\lambda_3)\cdot w = \mathbf0\tag{2}$$ Since $\{u,v,w\}$ is linearly independent (2) implies \begin{align*} \lambda_1+2\lambda_2+3\lambda_3 &= 0 \\ -\lambda_1+\lambda_3&= 0 \\ -\lambda_1+\lambda_2+3\lambda_3 &= 0 \end{align*} which is equivalent to the equation $A\vec\lambda=\mathbf 0$ where $$A= \begin{bmatrix} 1 & 2 & 3 \\ -1 & 0 & 1 \\ -1 & 1 & 3 \end{bmatrix}$$ But $\DeclareMathOperator{Rank}{Rank}\Rank(A)=2$ and we see that $$\Null(A)= \Span \left\{ \begin{bmatrix} 1\\-2\\ 1 \end{bmatrix} \right\}$$ Hence the equation (1) is solved by $\lambda_1=1$, $\lambda_2=-2$, and $\lambda_3=1$ and we see that $\{u-v-w, 2u+w, 3u+v+3w\}$ is linearly dependent.

• Brilliant. Thank you, sir! How I didn't think of that. – user175788 Oct 22 '14 at 7:54

The information that $u$, $v$ and $w$ belong to $\mathbb{R}^n$ is irrelevant; it's even better thinking to those vector in an arbitrary $n$-dimensional space $V$. You can complete $\{u,v,w\}$ to a basis of $V$, say to the set $\{u,v,w,z_4,\dots,z_n\}$ and there is a unique linear map $f\colon V\to\mathbb{R}^n$ such that \begin{align} f(u)&=e_1\\ f(v)&=e_2\\ f(w)&=e_3\\ f(z_k)&=e_k &&(4\le k\le n) \end{align} and this map is bijective, because it sends a basis to a basis. Thus a set of vectors $\{x_1,x_2,\dots,x_m\}$ is linearly independent if and only if $\{f(x_1),\dots,f(x_n)\}$ is linearly independent in $\mathbb{R}^n$.

This shows that it's not restrictive to assume $u=e_1$, $v=e_2$ and $w=e_3$, so you just need to check whether the set $$\left\{ \begin{bmatrix}1\\-1\\-1\\0\\\vdots\\0\end{bmatrix}, \begin{bmatrix}2\\0\\1\\0\\\vdots\\0\end{bmatrix}, \begin{bmatrix}3\\1\\3\\0\\\vdots\\0\end{bmatrix} \right\}$$ is linearly independent which is clearly equivalent to showing that the matrix $$\begin{bmatrix} 1&2&3\\ -1&0&1\\ -1&1&3 \end{bmatrix}$$ has rank $3$. The rank is easily computed with Gaussian elimination: $$\begin{bmatrix} 1&2&3\\ -1&0&1\\ -1&1&3 \end{bmatrix} \to \begin{bmatrix} 1&2&3\\ 0&2&4\\ 0&3&6 \end{bmatrix} \to \begin{bmatrix} 1&2&3\\ 0&1&2\\ 0&3&6 \end{bmatrix} \to \begin{bmatrix} 1&2&3\\ 0&1&2\\ 0&0&0 \end{bmatrix}$$ so the rank is $2$ and the three given vectors are linearly dependent. If you go on with backwards elimination, you reach $$\begin{bmatrix} 1&0&\color{red}{-1}\\ 0&1&\color{red}{2}\\ 0&0&0 \end{bmatrix}$$ so you conclude that $$3u+v+3w=\color{red}{-1}(u-v-w)+\color{red}{2}(2u+w)$$

Forget what space $u,v,w$ live in; the only important thing is that they are linearly independent. Therefore they form a basis of the subspace $V=\langle u,v,w\rangle$ spanned by themselves (they are a spanning set by definition of $V$, and independent by hypothesis). This means that the operation of formation of linear combinations $L:(a,b,c)\mapsto au+bv+cw$ is an isomorphism $\def\R{\Bbb R}\R^3\to V$ so it has an inverse isomorphism $L^{-1}:V\to\R^3$ which is expression of vectors of $V$ in coordinates on the basis $[u,v,w]$. Now directly form the definition \begin{align} L^{-1}(u−v−w)&=(1,-1,-1), \\L^{-1}(2u+w)&=(2,0,1), \\ L^{-1}(3u+v+3w)&=(3,1,3). \end{align} Since an isomorphism preserves linear dependence or independence, the question whether the vectors $u−v−w$, $2u+w$, $3u+v+3w$ of $V$ are linearly dependent is equivalent to the question whether their images $(1,-1,-1)$, $(2,0,1)$, and $(3,1,3)$ in $\R^3$ under the isomorphism $L^{-1}$ are linearly dependent.

Thus a somewhat abstract question in $\R^n$ is translated into a concrete question in$~\R^3$. To actually answer that question, one has to set up and find all solutions of a $3\times 3$ system of linear equations, which is exactly the system in the answer by Brain Fitzpatrick. Since there are actually non-zero solutions, the given vectors are linearly dependent. I won't repeat that (easy) computation; the main point I want to make is that the reduction to a problem in $\R^3$ results directly from the expression of relevant vectors in coordinates with respect to an appropriate basis (here $[u,v,w]$), which is why for computations the spaces of the form $\R^k$ are of such a central importance, and why the notion of basis (of a space or of a subspace) is so important.