# Proof: Addition of vector makes the set remain linearly independent

• Oct 4th 2009, 08:49 AM
owq
Proof: Addition of vector makes the set remain linearly independent
Let's say \$\displaystyle u_{1}, u_{2}..., u_{k}\$ are linearly independent vectors in \$\displaystyle R^n\$.

Suppose \$\displaystyle u_{k+1}\$ is a vector in \$\displaystyle R^n\$ and \$\displaystyle u_{k+1}\$ is not a linear combination of \$\displaystyle u_{1}, u_{2}..., u_{k}\$.

Show that \$\displaystyle u_{1}, u_{2}..., u_{k}, u_{k+1}\$ are linearly independent.

I have some idea, but I can't think of a rigorous proof. Any ideas?
• Oct 4th 2009, 09:03 AM
aman_cc
Quote:

Originally Posted by owq
Let's say \$\displaystyle u_{1}, u_{2}..., u_{k}\$ are linearly independent vectors in \$\displaystyle R^n\$.

Suppose \$\displaystyle u_{k+1}\$ is a vector in \$\displaystyle R^n\$ and \$\displaystyle u_{k+1}\$ is not a linear combination of \$\displaystyle u_{1}, u_{2}..., u_{k}\$.

Show that \$\displaystyle u_{1}, u_{2}..., u_{k}, u_{k+1}\$ are linearly independent.

I have some idea, but I can't think of a rigorous proof. Any ideas?

I will try to get you started.
Let \$\displaystyle a_1u_{1}+a_2u_{2}...+a_ku_{k}+a_{k+1}u_{k+1}=0\$

Now we can have two cases:
1. \$\displaystyle a_{k+1}\$ not equal to \$\displaystyle 0\$
Prove that this is not possible.
So we are left with
2. \$\displaystyle a_{k+1}=0\$. Under this what can you say about \$\displaystyle a_1,a_2,...,a_k\$?

What can we conclude finally?
• Oct 4th 2009, 09:31 AM
owq
Thanks.

Can we say that since \$\displaystyle a_1u_{1}+a_2u_{2}...+a_ku_{k}\$ not equals \$\displaystyle a_{k+1}u_{k+1}\$, the equation will never be equal to zero unless \$\displaystyle a_{k+1}=0\$?

Does this work: since \$\displaystyle u_{k+1}\$ and span(\$\displaystyle u_{1}, u_{2}..., u_{k}\$) are linearly independent, and \$\displaystyle u_{1}, u_{2}..., u_{k}\$ are linearly independent, thus \$\displaystyle u_{1}, u_{2}..., u_{k}, u_{k+1}\$ are linearly independent?
• Oct 4th 2009, 09:53 AM
aman_cc
Quote:

Originally Posted by owq
Thanks.

Can we say that since \$\displaystyle a_1u_{1}+a_2u_{2}...+a_ku_{k}\$ not equals \$\displaystyle a_{k+1}u_{k+1}\$, the equation will never be equal to zero unless\$\displaystyle a_{k+1}=0\$?

I am also new to the subject. Though what you say is correct in essence a more 'rigorous' argument will be
If \$\displaystyle a_{k+1}\$ is not equal to 0, it has an inverse \$\displaystyle a_{k+1}^{-1}\$. If we multiply the entire equation \$\displaystyle a_1u_{1}+a_2u_{2}...+a_ku_{k}+a_{k+1}u_{k+1}=0\$
by \$\displaystyle a_{k+1}^{-1}\$ we get\$\displaystyle
b_1u_{1}+b_2u_{2}...+b_ku_{k}+u_{k+1}=0\$

Which is not possible - hence \$\displaystyle a_{k+1}\$ is not equal to 0.

Quote:

Does this work: since \$\displaystyle u_{k+1}\$ and span(\$\displaystyle u_{1}, u_{2}..., u_{k}\$) are linearly independent, and \$\displaystyle u_{1}, u_{2}..., u_{k}\$ are linearly independent, thus \$\displaystyle u_{1}, u_{2}..., u_{k}, u_{k+1}\$ are linearly independent?

Mu question would be - How do you define (and then prove) independence of a vector with a set span(\$\displaystyle u_{1}, u_{2}..., u_{k}\$)?
• Oct 4th 2009, 11:53 PM
owq
If \$\displaystyle a_{k+1}\$ is not equal to 0, it has an inverse \$\displaystyle a_{k+1}^{-1}\$.
If we multiply the entire equation \$\displaystyle a_1u_{1}+a_2u_{2}...+a_ku_{k}+a_{k+1}u_{k+1}=0\$ by \$\displaystyle a_{k+1}^{-1}\$ we get

\$\displaystyle u_{k+1} = -a_{k+1}^{-1}a_1u_{1}+-a_{k+1}^{-1}a_2u_{2}...+-a_{k+1}^{-1}a_ku_{k}\$ which is not possible.
Hence \$\displaystyle a_{k+1} = 0\$.

I see. Is there any other way to solve this?
• Oct 5th 2009, 12:10 AM
aman_cc
Not that I know of. I feel this one is pretty fine, as we have just relied on axioms of field and vector space. I guess, any other approach should use a similar argument(about the existence of inverse - as I think that is the key axiom used here). Thanks