probability that a system of linear equations is solvable

Question

I came across this problem while surfing internet. The problem would be stated as follows, which is equivalent of asking whether given system of linear equations is solvable :

Let $F$ be a field. On choosing $A\in M_{n\times n}(F)$ and $b\in F^n$, what is the probability that $b \in \text{Im } A$?(thinking $A$ as linear map from $F^n$ to $F^n$)

As I lack understanding in concept of probability, I'm not even sure if the given conditions are sufficient to define probability for arbitrary fields. So I first consider only the cases with finite fields.

Let $|F|=q$. Total possibility would be $q^{n(n+1)}$ as one chooses an $n\times n $ matrix and a size n column vector. Classifying the elements of $M_{n \times n}(F)$ by the rank, let $\rho(k)$ denote the number of matrices in $M_{n \times n}(F)$ with rank $k$. If $A$ has rank $k$, image of $A$ is $F$-vector space of dimension $k$ and thus the possibility in consideration is calculated as $$\sum_{i=0}^{n} \rho(i)q^i$$

Thus counting $\rho(k)$ for integers $k$ yields the probability in question, but I can't quite come out with the way to calculate it. What method would there be to calculate $\rho(k)$? If in someway we have calculated the probability for finite fields, how can it be generalized to arbitrary fields?

Answer 1

This is a partial answer. I tried to find the number of $M_n$ matrices of rank $k$.

Let $M$ be one such matrix. $M$ is completely and uniquely determined by the images of $e_i = \pmatrix{0 & \dots & 0 & 1 & 0 & \dots & 0}^\top$

Let $k_i$ be the dimension of $\text{Vect} (e_1,\dots, e_i)$
We have $k_0 = 0,\ k_n = k,$ and $k_i$ is an increasing sequence.
So $k_i$ is characterized by the $k$ points at which it increases: $d_1\lt \dots\lt d_k$
We additionally define $d_0 = 0, d_{k+1} = n+1$

For $i=d_j$, $Me_i$ can take $q^n-q^j$ values
For $d_j<i<d_{j+1}$, $Me_i$ can take $q^j$ values

So we get a total of $$\sum_{1\leq d_1\lt \dots \lt d_k \leq n} \prod_{j=1}^{k} (q^n-q^j) q^{j(d_{j+1}-d_j - 1)} $$

matrices of rank $k$. I doubt a simple closed form expression exists, but I could be wrong.

Answer 2

Also a partial answer / not a closed form solution...

This is actually a very simple Markov chain with states $\{0, 1, ..., n\}$ representing the possible ranks. You start at rank (i.e. state) $0$ and keep adding a column every timestep. From state $r$ there are only 2 possible transitions:

• The new column is dependent and you stay at rank $r$. This happens with probability $P_{r,r} = \frac{q^r}{q^n}$.

• The new column is independent and you increase rank by $1$, i.e. you move to rank $r+1$. This happens with probability $P_{r,r+1} = 1 - \frac{q^r}{q^n}$.

So the Markov chain's transition probability matrix $P_{(n+1)\times (n+1)}$ is zero everywhere except along the main diagonal and the diagonal just above it.

As usual, the probabilities for being in the various states after $t$ timesteps (i.e. after adding $t$ columns) is given by $ \vec{1} \cdot P^t$ where $\vec{1} = $ the row vector $[1, 0, 0, ... ,0]_{(n+1)}$ and represents starting at the rank $0$ state.

Since $b$ is just the $(n+1)$th column, the event $b \in \text{Im } A$ is equivalent to saying that $(n+1)$th timestep is NOT a rank increase. The probability of this is:

$$\vec{1} \cdot P^n \cdot diag(P) $$

where $diag(P)$ is the column vector made of the (main) diagonal entries of $P$.

Now this is of course still not a closed form solution, but perhaps someone more skilled in dealing with matrices can help? Especially since $P$ has some nice internal structure that might be exploited?