multiple sets of linearly independent vectors


by SvS
Tags: binary vectors, linearly independent
SvS
SvS is offline
#1
Jan31-12, 08:17 AM
P: 4
hallo

I am trying to calculate the probability to obtain 2 sets of linearly independent vectors from a set of binary vectors of length k.

For example:
k = 4, and therefore I have 2^k = 16 vectors to select from.

I want to randomly select 7 vectors (no repetition).

What is the probability that 4 of the selected vectors forms a linearly independent set (4 x 4 matrix with rank 4)
and
the other 3 forms a linearly independent set (4 x 3 matrix of rank 3)? These two sets are viewed independently from each other.

I can calculate the probability of obtaining a single set of linearly independent vectors, but I cannot figure out how to calculate 2 sets at the same time.

Any help would be greatly apprectiated.
Thank YOU
Phys.Org News Partner Science news on Phys.org
NASA's space station Robonaut finally getting legs
Free the seed: OSSI nurtures growing plants without patent barriers
Going nuts? Turkey looks to pistachios to heat new eco-city
chiro
chiro is offline
#2
Feb1-12, 04:39 AM
P: 4,570
Hey SvS and welcome to the forums.

So assuming your uniform distribution and non-repetition constraint, it seems like you will have a combinatoric problem.

The first thing to do is to figure out the number of different basis you have. Once this is done you can start to either draw up a probability tree diagram or use straight combinatoric arguments to get the probabilities. Since we know that everything is uniform, this is simplified greatly.

So based on this, what do you think the next steps are?
SvS
SvS is offline
#3
Feb1-12, 05:37 AM
P: 4
chiro

Thank you for the reply.

As an engineer struggling with these combinatoric problems, I have trouble to follow all the mathematical terms and methods.

Are you referring to the number of linearly independent sets that can be possibly constructed? I have done so.

Next I tried to construct a probability tree diagram to find the worst possible case. I figured that this would be a lower bound on my problem. But I am struggling to generalise this.

I have also tried to determine the number of possible choices of vectors I can select each time; eliminating the linearly dependent vectors as choices. But considering 2 sets, confuses me greatly.

I am unsure if I am clear.

Thank YOU for the help so far

chiro
chiro is offline
#4
Feb1-12, 05:42 AM
P: 4,570

multiple sets of linearly independent vectors


So to clarify you want to do it for n-dimensional vectors (so 2^n possible vectors) with different situations involving a nxk linear system where 0 < k < n+1?

Assuming a uniform distribution, you want a probability if getting a nxk linear system that is linearly independent? Do you actually want to do something with this information?

Also do you want to actually generate the solutions with a software routine?
SvS
SvS is offline
#5
Feb1-12, 05:54 AM
P: 4
Hallo

I have 2^k possible vectors (eg: 2^4 = 16) of length k.
I want to select n (where k < n+1) vectors (eg: n = 7). k vectors must form a linearly independent set AND the other (n-k) vectors must also be linearly independent when viewed seperately.

I do not want all the solutions. I simply want to determine what the probability is of finding such a selection in the first 7 packets I choose.
SvS
SvS is offline
#6
Feb14-12, 08:41 AM
P: 4
Hallo.

Can somebody please help me with my problem.

If you can just help me with the following piece, I shall be very greatful:

Problem:
How to determine the probability to obtain a set of k linearly independent vectors after n > k random selections. (Vectors are binary of length k.)

Attempt at Solution

I calculated the probability to obtain k linearly independent vectors after k selections. The probability can be calculated by p = ∏[itex]^{n}[/itex][itex]_{i=1}[/itex] (1-2[itex]^{i-1-n}[/itex]).

But this changes as I select more vectors.

Thank YOU in advance


Register to reply

Related Discussions
Linear Algebra - showing sets are linearly independent/dependent Calculus & Beyond Homework 1
determining whether sets of matrices in a vectorspace are linearly independent? Linear & Abstract Algebra 2
Linearly Independent Sets After Subtraction Calculus & Beyond Homework 14
Linearly Independent Sets and Bases Calculus & Beyond Homework 4
Linearly Independent Sets and Bases Precalculus Mathematics Homework 1