Find largest number of linearly dependent vectors among these 6 vectors

[Mohamed Abdul]

Homework Statement

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.

Homework Equations

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

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.

 

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

 

[Mohamed Abdul]

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.

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

 

[StoneTemplePython]

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

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.

 

[Mohamed Abdul]

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.

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?

 

[StoneTemplePython]

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?

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:

https://www.physicsforums.com/threads/solution-sets-of-linear-systems.924634/

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

What text are you using?

 

[Mohamed Abdul]

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:

https://www.physicsforums.com/threads/solution-sets-of-linear-systems.924634/

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

What text are you using?

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.

 

[StoneTemplePython]

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.

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.

 

[Mohamed Abdul]

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.

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.

 

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

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?

 

[StoneTemplePython]

I'm sorry, I never purchased the book

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
https://www.math.brown.edu/~treil/papers/LADW/LADW_2017-09-04.pdf

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?

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.

 

[haruspex]

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?

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 v₄ can be expressed as a linear combination of v₁ and v₂ you know that v₅ and v₆ 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.

 

[Mohamed Abdul]

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 v₄ can be expressed as a linear combination of v₁ and v₂ you know that v₅ and v₆ 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.

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.

 

[haruspex]

wouldn't that make v2,v3, and v5 all independent.

a) that does not follow as a logical consequence of

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.

and b) how would it conflict with what I wrote?

 

[LCKurtz]

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.

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?