Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Linearly Independent Vectors

Subject: Linearly Independent Vectors

From: Lin

Date: 13 Apr, 2009 11:33:01

Message: 1 of 14

Hi all..

Suppose i have generated a set of vectors using the following codes,

field = 3;
[d2,d1] = ndgrid(0:field-1,0:field-1);
d = [d1(:).';d2(:).'];
d(:,1) = [];

How can i obtained 4 linearly independent vectors from the set of vectors i have generated earlier?

Expected results:

1) [0;1]
2) [1;0]
3) [1;1]
4) [1;2]

Thank you for your help.

Subject: Linearly Independent Vectors

From: Wayne King

Date: 13 Apr, 2009 11:51:00

Message: 2 of 14

Hi Lin, I'm not sure I understand your question entirely. d in your example looks like this
d =

     0 0 1 1 1 2 2 2
     1 2 0 1 2 0 1 2

You can only have at most a set consisting of two vectors in R^2 that are linearly independent. Any set containing 3 vectors in R^2 will be linearly dependent. In the 8 columns of d, there are a number of combinations of 2 that are linearly independent ([0 1],[1 0]), ([0 1] [2 2]), ([0 1] [2 1]) just to list a few pairs. Are you seeking every such combination from d?

wayne

"Lin " <shenqlv@yahoo.com> wrote in message <grv7td$3jt$1@fred.mathworks.com>...
> Hi all..
>
> Suppose i have generated a set of vectors using the following codes,
>
> field = 3;
> [d2,d1] = ndgrid(0:field-1,0:field-1);
> d = [d1(:).';d2(:).'];
> d(:,1) = [];
>
> How can i obtained 4 linearly independent vectors from the set of vectors i have generated earlier?
>
> Expected results:
>
> 1) [0;1]
> 2) [1;0]
> 3) [1;1]
> 4) [1;2]
>
> Thank you for your help.

Subject: Linearly Independent Vectors

From: John D'Errico

Date: 13 Apr, 2009 12:32:00

Message: 3 of 14

"Lin " <shenqlv@yahoo.com> wrote in message <grv7td$3jt$1@fred.mathworks.com>...
> Hi all..
>
> Suppose i have generated a set of vectors using the following codes,
>
> field = 3;
> [d2,d1] = ndgrid(0:field-1,0:field-1);
> d = [d1(:).';d2(:).'];
> d(:,1) = [];
>
> How can i obtained 4 linearly independent vectors from the set of vectors i have generated earlier?
>
> Expected results:
>
> 1) [0;1]
> 2) [1;0]
> 3) [1;1]
> 4) [1;2]
>
> Thank you for your help.

Why do you think that these are linearly independent?

http://en.wikipedia.org/wiki/Linearly_independent

Can we write V3 as a linear combination of V1 and V2?
It seems fairly trivial to write it as:

   V3 = V1 + V2

Likewise, can you write V4 as a linear combination
of V1 and V2.

You will not be able to find more then TWO
linear independent vectors from the columns of d.

help orth

HTH,
John

Subject: Linearly Independent Vectors

From: Lin

Date: 13 Apr, 2009 13:17:01

Message: 4 of 14

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <grvbc0$g8c$1@fred.mathworks.com>...

> John

I want to get 4 vectors from the main set i have generated earlier, such that whichever pair chosen from this 4 vectors will be linearly independent.

1) [0;1]
2) [1;0]
3) [1;1]
4) [1;2]

[0;1] & [1;0] , [0;1] & [1;1], [0;1] & [1;2], [1;0] & [1;1] and etc...

Sorry for the misunderstanding.

Subject: Linearly Independent Vectors

From: John D'Errico

Date: 13 Apr, 2009 14:52:01

Message: 5 of 14

"Lin " <shenqlv@yahoo.com> wrote in message <grve0d$8m9$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <grvbc0$g8c$1@fred.mathworks.com>...
>
> > John
>
> I want to get 4 vectors from the main set i have generated earlier, such that whichever pair chosen from this 4 vectors will be linearly independent.
>
> 1) [0;1]
> 2) [1;0]
> 3) [1;1]
> 4) [1;2]
>
> [0;1] & [1;0] , [0;1] & [1;1], [0;1] & [1;2], [1;0] & [1;1] and etc...
>
> Sorry for the misunderstanding.

D = d * diag(1./sqrt(sum(d.^2,1)));
[junk,I] = unique(D','rows');

I =
     2
     5
     8
     7
     6

D(:,I)'*D(:,I)
ans =
            1 0.89443 0.70711 0.44721 0
      0.89443 1 0.94868 0.8 0.44721
      0.70711 0.94868 1 0.94868 0.70711
      0.44721 0.8 0.94868 1 0.89443
            0 0.44721 0.70711 0.89443 1

Use this to convince yourself that I is a subset
of the columns of d, such that any TWO of them
are linearly independent. (Why should that convince
you? Think about it.) If your goal was to find a
subset that were maximally pairwise independent
under some measure, I would have suggested a
different strategy.

By the way, it would not have worked for a more
complex problem, where you wanted to ensure any
subsets of three vectors were linearly independent.
But that was not your question.

Finally, note that the trick I've used is slightly
dangerous, since it risks floating point problems in
the unique operation. This is not a problem, IN
THIS SPECIFIC CASE. A more careful solution
would have done it using a tolerance. My
consolidator code (from the FEX) would have
helped you there.

John

Subject: Linearly Independent Vectors

From: Lin

Date: 14 Apr, 2009 13:38:02

Message: 6 of 14

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <grvjih$lee$1@fred.mathworks.com>...
> "Lin " <shenqlv@yahoo.com> wrote in message <grve0d$8m9$1@fred.mathworks.com>...
> > "John D'Errico" <woodchips@rochester.rr.com> wrote in message <grvbc0$g8c$1@fred.mathworks.com>...
> >
 
> D = d * diag(1./sqrt(sum(d.^2,1)));
> [junk,I] = unique(D','rows');
>
> I =
> 2
> 5
> 8
> 7
> 6
>
> D(:,I)'*D(:,I)
> ans =
> 1 0.89443 0.70711 0.44721 0
> 0.89443 1 0.94868 0.8 0.44721
> 0.70711 0.94868 1 0.94868 0.70711
> 0.44721 0.8 0.94868 1 0.89443
> 0 0.44721 0.70711 0.89443 1

> John

Thanks John.. Your codes work well. However, can you explain how your codes work? I have problem understanding them. Example: What does those numbers in junk represent and the sentence
D = d * diag(1./sqrt(sum(d.^2,1)));

Once again, thanks for your help.

Subject: Linearly Independent Vectors

From: Lin

Date: 20 Apr, 2009 04:23:01

Message: 7 of 14

"Lin " <shenqlv@yahoo.com> wrote in message <gs23jq$et1$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <grvjih$lee$1@fred.mathworks.com>...
> > "Lin " <shenqlv@yahoo.com> wrote in message <grve0d$8m9$1@fred.mathworks.com>...
> > > "John D'Errico" <woodchips@rochester.rr.com> wrote in message <grvbc0$g8c$1@fred.mathworks.com>...

> Once again, thanks for your help.


Hi all.

I am not too sure how the previous codes work as such, i am not able to do the editing.

What I need.
Obtain any subsets of N vectors that are linearly independent.

Example
N = 2 -- ensure any subset of 2 vectors that are linearly independent
N = 3 -- ensure any subset of 3 vectors that are linearly independent
N = 4 -- ensure any subset of 4 vectors that are linearly independent

Thanks for helping.

Subject: Linearly Independent Vectors

From: Bruno Luong

Date: 20 Apr, 2009 05:57:01

Message: 8 of 14

"Lin " <shenqlv@yahoo.com> wrote in message <gsgtb5$rbq$1@fred.mathworks.com>...
> "Lin " <shenqlv@yahoo.com> wrote in message <gs23jq$et1$1@fred.mathworks.com>...
> > "John D'Errico" <woodchips@rochester.rr.com> wrote in message <grvjih$lee$1@fred.mathworks.com>...
> > > "Lin " <shenqlv@yahoo.com> wrote in message <grve0d$8m9$1@fred.mathworks.com>...
> > > > "John D'Errico" <woodchips@rochester.rr.com> wrote in message <grvbc0$g8c$1@fred.mathworks.com>...
>
> > Once again, thanks for your help.
>
>
> Hi all.
>
> I am not too sure how the previous codes work as such, i am not able to do the editing.
>
> What I need.
> Obtain any subsets of N vectors that are linearly independent.
>
> Example
> N = 2 -- ensure any subset of 2 vectors that are linearly independent
> N = 3 -- ensure any subset of 3 vectors that are linearly independent
> N = 4 -- ensure any subset of 4 vectors that are linearly independent
>


Use QR with column permutation (three outputs call).
[Q R E] = qr(d)

Check how many diagonal elements of R is non-zero, said N. Pick N first columns of d*E. That gives N independent vectors.

Bruno

Subject: Linearly Independent Vectors

From: Greg Heath

Date: 20 Apr, 2009 09:58:40

Message: 9 of 14

On Apr 13, 7:33=A0am, "Lin " <shen...@yahoo.com> wrote:
> Hi all..
>
> Suppose i have generated a set of vectors using the following codes,
>
> field =3D 3;
> [d2,d1] =3D ndgrid(0:field-1,0:field-1);
> d =3D [d1(:).';d2(:).'];
> d(:,1) =3D [];
>
> How can i obtained 4 linearly independent vectors from the set of vectors=
 i have generated earlier?
>
> Expected results:
>
> 1) [0;1]
> 2) [1;0]
> 3) [1;1]
> 4) [1;2]

These are not l.i.d.

v3 =3D v1+v2
v4 =3D v3+v1

If you have a matrix of column vectors the singular vectors
corresponding to nonzero singular values are l.i.d.

doc svd
help svd
A =3D[v1 v2 v3 v4]
[U S V] =3D svd(A)

Hope this helps.

Greg

Subject: Linearly Independent Vectors

From: John D'Errico

Date: 20 Apr, 2009 12:08:01

Message: 10 of 14

"Lin " <shenqlv@yahoo.com> wrote in message <gsgtb5$rbq$1@fred.mathworks.com>...
> "Lin " <shenqlv@yahoo.com> wrote in message <gs23jq$et1$1@fred.mathworks.com>...
> > "John D'Errico" <woodchips@rochester.rr.com> wrote in message <grvjih$lee$1@fred.mathworks.com>...
> > > "Lin " <shenqlv@yahoo.com> wrote in message <grve0d$8m9$1@fred.mathworks.com>...
> > > > "John D'Errico" <woodchips@rochester.rr.com> wrote in message <grvbc0$g8c$1@fred.mathworks.com>...
>
> > Once again, thanks for your help.
>
>
> Hi all.
>
> I am not too sure how the previous codes work as such, i am not able to do the editing.
>
> What I need.
> Obtain any subsets of N vectors that are linearly independent.
>
> Example
> N = 2 -- ensure any subset of 2 vectors that are linearly independent
> N = 3 -- ensure any subset of 3 vectors that are linearly independent
> N = 4 -- ensure any subset of 4 vectors that are linearly independent
>
> Thanks for helping.

The strategy that I gave you last week will not
work for a case where you wish to find subsets
of more than 2 vectors. But you originally only
asked for the case where N = 2.

So let me see if I understand you. You now wish
to solve the different problem:

Given an arbitrary set of K vectors (in some
number (N?) dimensions), choose some subset
of the original vectors, such that any subset of
N members of this subset of vectors is linearly
independent.

John

Subject: Linearly Independent Vectors

From: Lin

Date: 20 Apr, 2009 14:57:01

Message: 11 of 14

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <gshoj1$q26$1@fred.mathworks.com>...

> The strategy that I gave you last week will not
> work for a case where you wish to find subsets
> of more than 2 vectors. But you originally only
> asked for the case where N = 2.
>
> So let me see if I understand you. You now wish
> to solve the different problem:
>
> Given an arbitrary set of K vectors (in some
> number (N?) dimensions), choose some subset
> of the original vectors, such that any subset of
> N members of this subset of vectors is linearly
> independent.
>
> John

Thanks Greg, Bruno, John for replying.

Yes John, you are right. That's what I need exactly. Please help me out in this. Thank you.

%Expected Results
An arbitrary set of 2x1 vectors, any subset of 2 will be linearly independent
An arbitrary set of 3x1 vectors, any subset of 3 will be linearly independent
and so forth

Subject: Linearly Independent Vectors

From: Bruno Luong

Date: 20 Apr, 2009 15:19:01

Message: 12 of 14

> Please help me out in this. Thank you.

A=[1 0 1 0 1;
   0 1 1 0 0;
   0 0 0 0 0;
   0 0 0 1 1];

[Q R E]=qr(A);
N=find(diag(R)~=0,1,'last')
[selected dummyJ]=find(E(:,1:N));
Independent=A(:,selected)

Bruno

Subject: Linearly Independent Vectors

From: Lin

Date: 24 Apr, 2009 12:22:02

Message: 13 of 14

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gsi3p5$6f0$1@fred.mathworks.com>...
> > Please help me out in this. Thank you.
>
> A=[1 0 1 0 1;
> 0 1 1 0 0;
> 0 0 0 0 0;
> 0 0 0 1 1];
>
> [Q R E]=qr(A);
> N=find(diag(R)~=0,1,'last')
> [selected dummyJ]=find(E(:,1:N));
> Independent=A(:,selected)
>
> Bruno

Hi all

Suppose input
0 0 1 1
0 1 0 1

%What I have gotten from the codes
1 1
1 0

Can we list out all the possible combinations instead?

%Expected
1 1 0
1 0 1

so that I can choose my own set of linearly independent vectors instead of getting a fix set of linearly independent vectors from the code.

Subject: Linearly Independent Vectors

From: John D'Errico

Date: 24 Apr, 2009 13:42:01

Message: 14 of 14

"Lin " <shenqlv@yahoo.com> wrote in message <gssata$3i6$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gsi3p5$6f0$1@fred.mathworks.com>...
> > > Please help me out in this. Thank you.
> >
> > A=[1 0 1 0 1;
> > 0 1 1 0 0;
> > 0 0 0 0 0;
> > 0 0 0 1 1];
> >
> > [Q R E]=qr(A);
> > N=find(diag(R)~=0,1,'last')
> > [selected dummyJ]=find(E(:,1:N));
> > Independent=A(:,selected)
> >
> > Bruno
>
> Hi all
>
> Suppose input
> 0 0 1 1
> 0 1 0 1
>
> %What I have gotten from the codes
> 1 1
> 1 0
>
> Can we list out all the possible combinations instead?

No. Not trivially.
 
> %Expected
> 1 1 0
> 1 0 1
>
> so that I can choose my own set of linearly independent vectors instead of getting a fix set of linearly independent vectors from the code.

QR will not give you a set such that any subset
of vectors is linearly independent. QR will only
give you a SINGLE subset of independent vectors.

I think you are left with brute force. No magic
solution will give you the answer. If the rank of
your system is k, then find k independent vectors
in the set. QR will do this, as Bruno has shown.

Now add another vector to the set only if it,
paired with any subset of k-1 of these vectors,
is linearly independent of those vectors.

When magic fails, brute force applies.

John

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us