How many subsets of $n$ linearly independent binary strings of length $n$?

193 Views Asked by At

Let's consider binary words of length $n$ with elements {-1,1}. There are $2^n$ binary words of length $n$. Now let's consider a subset of $n$ such binary words. All possible subsets are $\binom{2^n}{n}$. These subsets might contains linearly independent or dependent words. For instance if $n = 2$ one has 6 possible subsets of 2 words of length 2. Two of them contain linearly dependent words: {(1,1),(-1,-1)} and {(1,-1),(-1,1)}. The other four are made up of linearly independents words. In general one can check linear dependency by evaluating the determinant of the square matrix whose rows are the binary words (In the example the determinant is zero in the first case, and different from zero in the other cases). Is there a way to evaluate the number of subsets containing linearly dependent words for a generic $n$? The absolute value of the determinant of {-1,1} matrices range from 0 to a maximum value $2^{n−1}\cdot D(n)$ (see Hadamard largest determinant problem) by steps of $2^{n−1}$. Here the problem is to find how many of these subsets have null determinant. For small $n$, the fraction of subsets with null determinant seems to increase with $n$.