0
$\begingroup$

Disclaimer: I think of vectors as row vectors.

I have a full-rank $m \times n$ ($m < n$) binary matrix $B$ which is a basis of $m$-dimensional subspace $V \subset\mathbb F_2^n$ (i.e. subspace $V$ is formed by linear combinations of rows of $B$).

I fixed $k \leq m$ and I want to generate a random full-rank $k \times n$ matrix $A$, such that the space spanned by $A$ (i.e. linear combinations of rows of $A$) is a subset of $V$.

Two things are important for me:

  • $A$ should be uniformly random among all such matrices. More precisely, if $\mathfrak A = \{ A_1, A_2, \dotsc, A_N\}$ is a set of all full-rank $k \times n$ matrices that span a subset of $V$, then it should hold that $\Pr[A = A_i] = \frac 1 N$.
  • Since I will need to generate such matrix many times, the method should be (in some sense) efficient.

One of the obvious solutions I see is just to generate random $A$ of required size until I get the one with a full rank. Probability of this is quite hight so it won't take many iterations. However, checking that matrix is full-rank is expensive operation. Or not?

$\endgroup$

1 Answer 1

0
$\begingroup$

Let $B=[B_1,\cdots,B_m]^T$, where the $(B_i)$ are linearly independent ($rank(B)=m$). The $k$ rows of $A$ are linear combinations of the $(B_i)$ with coefficients in $\mathbb{F}_2$; that is, there is a matrix $U\in M_{k,m}$ s.t. $A=UB$. Since $im(B)=\mathbb{R}^m$, $rank(A)=k$ iff $rank(U)=k$ iff $\det(UU^T)\not= 0$. Thus, for each random choice of $U$, to verify that $rank(A)=k$ has complexity $O(kn^2)$. The probability that $rank(A)=k$ is well-known, but I don't remember the result. This probability lets you know in advance how many tests you have to perform; practically, it is useless because you have not the choice; you must do the job...

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .