Find largest number of linearly dependent vectors among these 6 vectors

Tags:
1. Dec 1, 2017

Mohamed Abdul

1. The problem statement, all variables and given/known data
Given the six vectors below:

1. Find the largest number of linearly independent vectors among these. Be sure to carefully describe how you would go about doing so before you start the computation.

2 .Let the 6 vectors form the columns of a matrix A. Find the dimension of and a basis for the column space of A.

3. Find the dimension of and a basis for the row space of A.

4. Find the dimension of and a basis for the null space of A.

5. Find the rank and the nullity of A.

2. Relevant equations

Gaussian elimination method given here: mathworld.wolfram.com/GaussianElimination.html

3. The attempt at a solution

For 1, I tried setting up a matrix using each of these vectors as rows. Then, after Gaussian elimination, I will see all the non-zero rows, adding them up, and having that be my largest number of linearly independent vectors. My question is what separates part 1 from part 2 of the problem, or if I'm even doing this correctly at all.

2. Dec 1, 2017

StoneTemplePython

my take is you should forget matrices at first, and try the basic linear independence equation:

$x_1 \mathbf v_1 + x_2 \mathbf v_2 + x_3 \mathbf v_3 + x_4 \mathbf v_4 + x_5 \mathbf v_5 + x_6 \mathbf v_6 = \mathbf 0$

which is linearly independent iff all $x_i = 0$.

You should be able to know that there are at most 4 of said vectors in such an equation while being linearly independent (because vectors are 4 dimensional).

You should also be able to come up with a few different examples to get things going on part 1. You can eyeball this and know that at least 2 vectors can be linearly independent, and after playing around with combinations, can do better and find an example of at least 3. Maybe you can do better than 3?

for part 2, all you need to do is make the jump from the equation above to matrix vector multiplication...

$\mathbf V \mathbf x= \bigg[\begin{array}{c|c|c|c|c} \mathbf v_1 & \mathbf v_2 &\cdots & \mathbf v_{5} & \mathbf v_{6} \end{array}\bigg] \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_{5}\\ x_6 \end{bmatrix} = x_1 \mathbf v_1 + x_2 \mathbf v_2 + ... x_{5}\mathbf v_{5} + x_6 \mathbf v_6 = \mathbf 0$

and hence you're solving in the nullspace of $\mathbf V$
- - - -
starting with Gaussian elimination seems like a mistake to me.

3. Dec 1, 2017

Mohamed Abdul

Is there any way to go about finding the largest number of vectors without resorting to finding combinations?

4. Dec 1, 2017

StoneTemplePython

Yes and no.

First observe that none of those vectors is the zero vector.

Now, you should be able to start with $\mathbf v_1$ and then look at $\mathbf v_2$ and see that it only 'speaks' to one component of $\mathbf v_1$ hence they're linearly independent. Now consider $\mathbf v_3$ how could it be written as a linear combination of $\mathbf v_1$ and $\mathbf v_2$ ? Or if it can't, then it is linearly independent and you have a set of 3 linearly independent vectors. And continue on down.

- - - -
assuming we're in reals, there's another approach involving orthogonality, but I don't think it's needed.

5. Dec 1, 2017

Mohamed Abdul

I understand what you're saying; it wasn't as difficult as I anticipated. After adding the combinations of 2 vectors from the six, I found that there were combinations that added to make vectors 2,3, and 5, but 1,4, and 6 were unique, so then would my answer be 3?

Edit: Also, for part 2 would I have these vectors be the columns for a larger matrix, than I proceed with reduction techniques until I can find the dimension and basis and then for part 3 I do the same but have my vectors become the rows of my matrix?

6. Dec 1, 2017

StoneTemplePython

I'm not sure I follow what you're saying. If you found ways to create 2, 3, and 5 solely from linear combinations of 1, 4, and 6, then yes. Otherwise, the brute force approach is to try all combinations of 4 from those 6 vectors (there are 15 in total).

-----
strange that your edited comment showed up in my quote, but not on my screen when I responded.

re-visit my original post for part 2. There is a direct link between matrix vector products and linear independence tests.

- - - -
another note:
you may want to look at this thread:

it is awfully similar to this one, and my thinking / advice is awfully similar.

What text are you using?

7. Dec 1, 2017

Mohamed Abdul

Ok I'm a little confused here. What I did was found combinations of two separate vectors that added up to another vector in the group of six vectors. Was I supposed to use more than two to find a combination, like 3 and 4. If so, I'm wondering if that will be overly time consuming, considering I'd have to check about 60 or so combination of four vectors.

8. Dec 1, 2017

StoneTemplePython

again, what book are you using?

I just told you that there are a maximum of 15 not 60 combinations of 4 vectors.

The goal here is to find vectors that can generate other ones. Ideally you find 4 linearly independent ones of them and call it a basis. Maybe there is only 3 linearly independent ones in your problem though. That is for you to figure out.

This is starting to sound like one of those threads where someone doesn't want to do the work. In which case by forum rules I cannot help you.

9. Dec 1, 2017

Mohamed Abdul

I'm sorry, I never purchased the book. I also did the work for the problem to arrive at my initial answer, which I can provide.

10. Dec 1, 2017

Mohamed Abdul

I understand how you arrived at the number of 15 maximum combinations looking at all the vectors. My question is if these sets can contain a maximum of four vectors, do I find all the sets with only two vectors, then three vectors, then four vectors that, if the members of the sets are added together, don't add up to another vector in the group?

11. Dec 1, 2017

StoneTemplePython

You need to get a book to reference and help you learn from. The line of thinking here just doesn't make much sense to me.

Here are links to two excellent free books:
https://math.byu.edu/~klkuttle/Linearalgebra.pdf

it's not clear to me whether this is a conceptual misunderstanding, or you are looking for an algorithmic way to solve this problem.

There's no need to find all sets with 2 linearly independent vectors. You only need to find one set that has this to prove that there are at least 2 linearly independent vectors.

There's also no need to find all sets with 3 linearly independent vectors -- you just need to try and find one set.

Same with trying to find 4 linearly independent vectors.

I know of a much shorter algorithmic approach over reals, but I see no benefit in discussing it. You need to understand what is going on in simple problems like this first.

You should be able to find a linearly independent 3 vector set pretty easily. From there, maybe you need to just brute force all 15 possible combinations of 4 vectors from the 6, and get your answer.

12. Dec 2, 2017

haruspex

There is much symmetry here.

It should be evident that vectors 1 to 3 are independent, that 4 to 6 are not independent, that 1 to 3 can be produced from each other by rotating their lowest three rows (dimensions), and that the same rotation relates 4 to 6 (except one of them would need its signs flipped).
Thus, when you observe that v4 can be expressed as a linear combination of v1 and v2 you know that v5 and v6 can also be expressed as linear sums of pairs from the first row.

If there is a subset of four independent vectors, what is the maximum you can choose from the top row? Does it matter which of that many you choose? What is the max you can choose from the lower row? Etc.

Of course, this is not a general method, and STPython may well have something better.

13. Dec 2, 2017

Mohamed Abdul

But by adding v1 and v4 I got v2, and by adding v1 and v5 I got v3, and by adding v2 and v6 I got v3. So wouldn't that make v2,v3, and v5 all independent.

14. Dec 2, 2017

haruspex

a) that does not follow as a logical consequence of
and b) how would it conflict with what I wrote?

15. Dec 2, 2017

LCKurtz

I assume that you have figured out that $\{v_1,~v_2,~v_3\}$ is an independent set already. While your last sentence above doesn't follow, your three equations are relevant to the problem. What do your observations tell you about whether including any of the remaining vectors with the first three would give you a larger independent set?