Skip to main content
added 9 characters in body
Source Link
aleph
  • 503
  • 3
  • 9

Consider $\mathbb{Z}_q \equiv \mathbb{Z}/q\mathbb{Z}$, where $q \geqslant 2$. A set of vectors in $\mathbb{Z}_q^n$ is said to be linearly independent if no nontrivial linear combination of them produces the zero vector. When $q$ is a prime (and hence $\mathbb{Z}_q$ is a field), the following is true: Given any $k$ distinct nonzero vectors in $\mathbb{Z}_q^n$, we are guaranteed to find $\lceil\log_qk\rceil$ linearly independent vectors among them. This does not seem to be true when $q$ is not a prime; for example, even just one vector $(3,3)$ is not linearly independent in $\mathbb{Z}_6^2$. My question is then the following: is there an obvious lower bound, perhaps not too different from the above, on the number of linearly independent vectors that we are guaranteed to find among any given $k$ distinct nonzero vectors in $\mathbb{Z}_q^n$, but such that it holds for arbitrary $q$?

Consider $\mathbb{Z}_q \equiv \mathbb{Z}/q\mathbb{Z}$, where $q \geqslant 2$. A set of vectors in $\mathbb{Z}_q^n$ is said to be linearly independent if no nontrivial linear combination of them produces the zero vector. When $q$ is a prime (and hence $\mathbb{Z}_q$ is a field), the following is true: Given any $k$ distinct nonzero vectors in $\mathbb{Z}_q^n$, we are guaranteed to find $\lceil\log_qk\rceil$ linearly independent vectors among them. This does not seem to be true when $q$ is not a prime; for example, even just one vector $(3,3)$ is not linearly independent in $\mathbb{Z}_6^2$. My question is then the following: is there an obvious lower bound on the number of linearly independent vectors that we are guaranteed to find among any given $k$ distinct nonzero vectors in $\mathbb{Z}_q^n$, for arbitrary $q$?

Consider $\mathbb{Z}_q \equiv \mathbb{Z}/q\mathbb{Z}$, where $q \geqslant 2$. A set of vectors in $\mathbb{Z}_q^n$ is said to be linearly independent if no nontrivial linear combination of them produces the zero vector. When $q$ is a prime (and hence $\mathbb{Z}_q$ is a field), the following is true: Given any $k$ distinct nonzero vectors in $\mathbb{Z}_q^n$, we are guaranteed to find $\lceil\log_qk\rceil$ linearly independent vectors among them. This does not seem to be true when $q$ is not a prime; for example, even just one vector $(3,3)$ is not linearly independent in $\mathbb{Z}_6^2$. My question is then the following: is there an obvious lower bound, perhaps not too different from the above, on the number of linearly independent vectors that we are guaranteed to find among any given $k$ distinct nonzero vectors in $\mathbb{Z}_q^n$, but such that it holds for arbitrary $q$?

Source Link
aleph
  • 503
  • 3
  • 9

Linear independence in $\mathbb{Z}_q^n$

Consider $\mathbb{Z}_q \equiv \mathbb{Z}/q\mathbb{Z}$, where $q \geqslant 2$. A set of vectors in $\mathbb{Z}_q^n$ is said to be linearly independent if no nontrivial linear combination of them produces the zero vector. When $q$ is a prime (and hence $\mathbb{Z}_q$ is a field), the following is true: Given any $k$ distinct nonzero vectors in $\mathbb{Z}_q^n$, we are guaranteed to find $\lceil\log_qk\rceil$ linearly independent vectors among them. This does not seem to be true when $q$ is not a prime; for example, even just one vector $(3,3)$ is not linearly independent in $\mathbb{Z}_6^2$. My question is then the following: is there an obvious lower bound on the number of linearly independent vectors that we are guaranteed to find among any given $k$ distinct nonzero vectors in $\mathbb{Z}_q^n$, for arbitrary $q$?