Determine this!

Algebra Level 4

Among the 4 x 4 matrices whose entries are all 1's and 0's, are there more invertible or more singular matrices (over the reals)?

More singular matrices More invertible matrices An equal number of singular and invertible matrices

1 solution

Otto Bretscher
Oct 13, 2015

Let $A$ be the set of all 4 x 4 matrices whose entries are all 1's and 0's; let $B$ be the matrices in $A$ with pairwise distinct nonzero rows; and let $C$ be the invertible matrices in $A$ .

Now $|C|=2^{16}=65536$ and $|B|=15*14*13*12=32760$ . We know that $C$ is a subset of $B$ , so that $|C|\leq |B|<|A|/2$ . Thus there are more singular matrices than invertible matrices in $A$ .

Moderator note:

As an upper bound on $|C|$ , we can use the interpretation of vector space over $\mathbb{F}_2$ . An invertible matrix has determinant 0 in $\mathbb{F}_2$ , which means that it's determinant in $\mathbb{R}$ is even (hence we only have an upper bound). Each 0-1 matrix then corresponds to a multi-set of 4 vectors, and an invertible matrix corresponds to a set of basis vectors. Hence, the number of ways is:

$( 2^4 - 1) ( 2^4 - 2 ) ( 2 ^4 - 4 ) ( 2 ^ 4 - 8 )$

@Challenge Master: This formula works over $F_2$ but not over the real numbers, which is what I'm asking for. As far as I know, there is no formula in that case.

Otto Bretscher - 5 years, 8 months ago

Oh yes, that is true. I calculated the number of matrices whose determinant is even (0 in $\mathbb{F}_2$ ), instead of those who are exactly 0.

I've updated the note.

Calvin Lin Staff - 5 years, 6 months ago

Determine this!

1 solution

Moderator note:

0 pending reports