Expected number of rows of the full rank matrix

Question

Let A be a m by n random matrix over finite fields F_q. Suppose the rank of A is n.

How much does expected number of m? I think m maybe qlogq by bins and balls property

But I do not know exactly why.

Thanks.

Answer 1

From the exchange in the comments, I gather that the question was intended to be how many rows of length $n$ you expect to add to a matrix over $\mathbb F_q$ if you successively add uniformly random rows (starting from none) until they span $\mathbb F_q^n$, that is until they form a matrix with full column rank.

This is a sort of coupon collector's problem, with modified probabilities, and the same approach yields the result.

For the first independent row, you have $q^n-1$ options, so the expected number of rows is $q^n/(q^n-1)$. For the next independent row, you have $q^n-q$ options, and generally, for the $(k+1)$-th independent row you have $q^n-q^k$ options. Thus the expected number of rows is

$$ q^n\sum_{k=0}^{n-1}\frac1{q^n-q^k}=\sum_{k=0}^{n-1}\frac1{1-q^{k-n}}\;. $$