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$
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.