Proposed Problem
If anyone can get a good answer to this I'll take you to lunch or something.
Given n randomly chosen bit strings of size n, what is the probability that one can arrange them in an nxn matrix and get a 0 diagonal. (bit strings mean alphabet is {0,1}, so n elements in {0,1}^n randomly chosen).
So for example n=3.
{(001),(010),(110)} Can be re-arranged to :
010
001
110
{(111),(010),(001)} Cannot be re-arranged!
Its random, so you can get same one twice the domain is (2^n)^n.
If something looks wrong here let me know.
Alright...
posted by Diego Matute at 11:51 AM
6 Comments:
Here are some thoughts.
Proposition: There is a permutation of the rows of an n*n matrix of bits such that the result has a diagonal if 0's iff there are no rows or columns of 1's.
Then, what is the probability that an n*n matrix of bits has a row or column of 1's?
An O(n^2) algorithm calculates these probabilities:
1 000 000 trials
1*1: ~0.497, 5s
2*2: ~0.430, 6s
4*4: ~0.635, 9s
8*8: ~0.940, 24s
16*16: ~0.999, 1m 5s
32*32: 1.0, 3m 52s
As you were saying, as n -> inf, P = 1.
However, our hypotheses about the linear independence do not seem correct.
Here is a sample 4x4 inputs and their results.
A := [[0,1,0,0],[0,1,1,0],[1,1,1,0],[0,0,0,0]]
- true
- det(A) = 0
A := [[0,1,1,0],[1,0,0,1],[0,1,0,1],[0,1,1,1]]
- true
- det(A) = 1
A := [[0,0,0,1],[1,0,0,0],[0,1,1,0],[0,1,0,0]]
- true
- det(A) = 1
A := [[0,1,1,0],[0,1,0,1],[0,1,1,0],[0,1,0,1]]
- false
- det(A) = 0
A := [[1,0,1,0],[1,0,0,1],[1,1,1,1],[1,1,0,1]]
- false
- det(A) = -1
2:23 PM
For a 2*2 matrix,
P(permutation with diagonal of 0s)
= 1 - (P(row of 1s and no cols of 1s) + P(col of 1s and no rows of 1s) + P(col of 1s and row of 1s))
= 1 - (2/16 + 2/16 + 5/16)
= 1 - 9/16 = 7/16 = 0.4375
Proposition: The probability that an n*n matrix has a at least 1 row of 1s and no cols of 1s is the same as the probability that it has at least 1 col of 1s and no rows of 1s.
Proposition: The above probability may be expressed as
A(n) = n * 2^(n-2) / 2^(n^2)
Then we need to find B(n), the probability of both one row and one columns in an n*n matrix, to complete the statement of probability.
P(n) = 2*A(n) + B(n)
P(2) = 2*2/16 + 5/16 = 0.4375
4:22 PM
You can have matrices that don't have columns or rows of ones but still don't have the 0 permutation. Eg :
1 0 1 1
1 1 0 1
1 1 0 1
0 1 0 0
9:03 AM
I hate you.
So then do the rows need to be linearly independent? Hmm... I have to think about that.
12:16 PM
If the rows are linearly independent, like if you are talking about n-dim binary vectors? Can't guarantee the 0 diagonal, for example you can have lin independent with a 1 column :
1 0 1 1
0 0 1 1
0 1 1 1
1 1 0 1
12:49 PM
Also,
1001
0110
0110
1001
10:25 PM
Post a Comment
<< Home