0

Suppose $B \in \mathbb{R}^{n \times k}$ is a basis for a lattice $L$ of dimension $k$ ($n \geq k$ and the basis vectors are on the columns of $B$). Suppose also we have a set of $n$-vectors $\{ v_{(1)}, v_{(2)}, \cdots, v_{(\ell)} \}$, $1 \leq \ell < k$, which we know can be completed to a basis of $L$. Is there an efficient practical way to perform this completion?

As pointed out in the comments, the question is equivalent to: how does one practically complete an integer $n \times m$ matrix with $m < n$, to a unimodular $n \times n$ matrix (assuming the completion can be done)?

Latrace
  • 308
  • Maybe I don't understand, but aren't the $n$-vectors enough, since $n \geq k$? – jtb Feb 03 '23 at 21:15
  • https://kconrad.math.uconn.edu/blurbs/ringtheory/primvector.pdf – Will Jagy Feb 03 '23 at 22:31
  • @JoshBone, the $n$ in $n$-vector refers to the length of the $v_j$, of which there are $\ell < k$. – Latrace Feb 05 '23 at 20:14
  • @WillJagy I don’t understand how this reference answers the question. Kindly elaborate. – Latrace Feb 05 '23 at 20:14
  • You can make a rectangular matrix of integers that displays how the column vectors $v_j$ are represented as sums of the columns of $B.$ Call this new matrix $M.$ Your conditions say that $M$ can be completed to a unimodular matrix; the new elements of $\dot {M}$ show the rest of the basi completing the $v_j.$ Suggest you fiddle with cases where $B$ is 2 by 1, then explore 3 by 1 and 3 by 2. The part I wonder about is: if $B$ has real entries, it may be messy to do the first step, finding $M$ – Will Jagy Feb 05 '23 at 20:49
  • @WillJagy Thanks for the further comments. I see now that the question is equivalent to the task of completing an integer $n \times m$ matrix with $m < n$ to a unimodular $n \times n$ matrix. The 2 by 1 and 3 by 1 cases for $B$ are trivial. I've played around with the 3 by 2 case but didn't learn a general lesson. Regarding the question about $B$ having real entries: the equation we have is $V = BM$, with the basis vectors $v_{(j)}$ and $b_{(k)}$ on the columns of $V$ and $B$ respectively. Then $M = (B^\top B)^{-1} B^\top V$. – Latrace Feb 06 '23 at 12:16

0 Answers0