Multiple sets of linearly independent vectors

[SvS]

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

 

[chiro]

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]

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]

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]

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

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]

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 = ∏^{n}_{i=1} (1-2^{i-1-n}).

But this changes as I select more vectors.

Thank YOU in advance