Matrix inverse's existential crisis

Probability Level 4

Consider the matrix

$A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}$

with $P(a_{ij} = 0) = P(a_{ij} = 1) = \frac{1}{2}$ for all entries.

If the probability that $A$ is invertible can be expressed as $\frac{m}{n}$ , where $m$ and $n$ are positive coprime integers, find $m+n$ .

The answer is 11.

2 solutions

Marilyn Bretscher
May 25, 2015

There are $2^4=16$ such matrices all together.

If a matrix contains no 1, exactly one 1, or four 1's, it cannot possibly be invertible.

If there are exactly two 1s, along either diagonal, then it's invertible (2 cases).

If there are exactly three 1s in any position, then it's invertible too (4 cases).

So it's invertible in 6 out of 16 cases, and the probability is $\frac{6}{16}=\frac{3}{8}$ , with $m+n=\boxed{11}$ .

As obvious as it might be, you should atleast mention in your solution that the main criteria for $A$ to be invertible is $|A|\neq 0$ which leads to the obvious conclusions.

$|A|\neq 0\iff a_{11}a_{22}\neq a_{12}a_{21}$

Since the only entries possible are $0$ and $1$ and they are equally likely, it simply boils down to basic counting of the cases where one side of the above inequation is $1$ and the other side is $0$ and then we use the definition of probability to get the answer.

Clarification: $|A|$ is the determinant of the square matrix $A$ .

Prasun Biswas - 6 years ago

I did not do the problem the way you assume.

By Gaussian elimination, the matrix fails to be invertible if there is a row of zeros or the two rows are equal. This will always be the case if there are zero, one or four 1s, and it will never be the case if there are three 1s. The case of two 1s is then quickly analysed.

Marilyn Bretscher - 6 years ago

Fair enough. :)

Prasun Biswas - 6 years ago

Ron Sperber
May 27, 2015

The first row can be anything other than 2 zeros, so there are 3 choices for the first row. Once we know the first row, the second row cannot be 2 zeros, nor can it be the same as the first row, but the other 2 possibilities will work. Thus, for each valid first row, there are 2 possible 2nd rows, for a total of 3x2=6 possibilities. There are 16 possible matrices, so the probability is 6/16=3/8.

Matrix inverse's existential crisis

The answer is 11.

2 solutions

0 pending reports