Existence of a linearly independent subset in $\mathbb{Z}/p\mathbb{Z}$.

Question

Let $U$ be a subspace of dimension $k$ in $\mathbb{Q}^n$. The question is:

Is there a basis $\{\textbf{u}_1,\dots, \textbf{u}_k\}$ of $U$ such that each $\textbf{u}_i \in \mathbb{Z}^n$ and with the property that, the $\{\overline{\textbf{u}}_1,\dots, \overline{\textbf{u}}_k\}$ is also linearly independent in the vector -space $(\mathbb{Z}/p\mathbb{Z})^n$?

Here, $\overline{\textbf{u}_i}$ denote the passage of $\textbf{u}_i$ into $(\mathbb{Z}/p\mathbb{Z})^n$.

My attempt: Given a basis of $U$, we may assume WLOG that each $\textbf{u}_i$ lie in $\mathbb{Z}^n$ (by clearing denominators) and moreover its image in $\mathbb{Z}/p\mathbb{Z}^n$ is nonzero (by factoring out multiples of $p$).

If I write each $\textbf{u}_i=(u_{1i}, u_{2i},\cdots, u_{ni})$. Then the problem of asking whether $\{\overline{\textbf{u}}_1,\cdots \overline{\textbf{u}}_k\}$is linearly dependent over $\mathbb{Z}/p\mathbb{Z}^n$ is equivalent to asking if the linear system

$$\begin{pmatrix} u_{11} & u_{12} & \cdots & u_{1k} \\ u_{21} & u_{22} & \cdots & u_{2k} \\ \vdots& \vdots & \ddots& \vdots \\ u_{n1} & \cdots &\cdots & u_{nk}\end{pmatrix}\textbf{v} = 0 \pmod{p}$$

has a solution.

However it is not clear to me how to proceed from here. Any hints given would be greatly appreciated!

Answer 1

In fact, something stronger is true: Since the group $\mathbb{Z}^n$ is a free Abelian group of finite rank, the subgroup $U \cap \mathbb{Z}^n$ must also be free. Let $v_1, \ldots, v_r$ be a basis for this subgroup. I then claim that this fixed set $v_1, \ldots, v_r$ remains linearly independent when reduced modulo any prime $p$.

To see this, suppose that $\alpha_1 \bar v_1 + \cdots + \alpha_r \bar v_r = 0$ in $\mathbb{F}_p^n$. Then each $\alpha_i$ is the image of some $b_i \in \mathbb{Z}$, and $w := b_1 v_1 + \cdots + b_r v_r \in p \cdot \mathbb{Z}^n$. Then $\frac{1}{p} \cdot w \in U \cap \mathbb{Z}^n$, so it is equal to $c_1 v_1 + \cdots + c_r v_r$ for some $c_1, \ldots, c_r \in \mathbb{Z}$. Now, by the independence of $v_1, \ldots, v_r$, it follows that $b_1 = p c_1, \ldots, b_r = p c_r$, so each $\alpha_i = p \cdot \bar c_i = 0$ as a scalar in $\mathbb{F}_p$.

(To finish up, it should be straightforward to show that $r = k = \dim_{\mathbb{Q}}(U)$.)

Answer 2

Firstly, I don't think that using any given basis of $U$ will work. For example, $$\mathbf{u}_1 = (1, 1, 0), \ \mathbf{u}_2 = (2, 0, 1), \ \mathbf{u}_3 = (0,2,2)$$ forms a basis for $U = \mathbb{Q}^3$, but $\overline{\mathbf{u}_1} + \overline{\mathbf{u}_2} + \overline{\mathbf{u}_3} = 0$ in $(\mathbb{Z}/3\mathbb{Z})^3$.

Secondly, a basis of a subspace in $\mathbb{Q}^n$ could map to a set of smaller size in $(\mathbb{Z}/p\mathbb{Z})^n$. For example, the basis $\{(p+1, 1), (1, 1)\}$ of $U = \mathbb{Q}^2$ projects onto $\{(1,1)\}$, which is a linearly independent set.

By using induction on $k$ and exploiting this "collapsing" effect when needed, I believe we can always find a suitable basis for $U$ which maps to a linearly independent set in $(\mathbb{Z}/p\mathbb{Z})^n$.