Skip to main content
added 180 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

$\newcommand{\F}{{\mathbb F}}$ Let's focus on the case $q=2$ which you are primarily interested in. Suppose that $v_1,\dotsc,v_m\in\F_2^n$, and let $V$ be the matrix over $\F_2$ of size $n\times m$ with $v_1,\dotsc,v_m$ (written in the standard basis) as its columns. It is readily seen that for $v_1,...,v_m$$v_1,\dotsc,v_m$ to be $k$-wise linearly independent, it is necessary and sufficient that the kernel of $V$ doesdid not contain any vector of weight $k$ or less. ThereforeYou are thus asking how large can the length $m$ of a linear code be given that the minimum distance of the code is at least $k+1$, your questionand that the code has co-dimension $n$. This is essentially equivalent to, arguably, the central problem of coding theory: what is the largest possible dimension of a linear code of given length and minimum distance ($m$ with the minimal distance at leastand $k+1$, respectively, in our case)?

$\newcommand{\F}{{\mathbb F}}$ Let's focus on the case $q=2$ which you are primarily interested in. Suppose that $v_1,\dotsc,v_m\in\F_2^n$, and let $V$ be the matrix over $\F_2$ of size $n\times m$ with $v_1,\dotsc,v_m$ (written in the standard basis) as its columns. It is readily seen that for $v_1,...,v_m$ to be $k$-wise linearly independent, it is necessary and sufficient that the kernel of $V$ does not contain any vector of weight $k$ or less. Therefore, your question is equivalent to, arguably, the central problem of coding theory: what is the largest possible dimension of a linear code of length $m$ with the minimal distance at least $k+1$?

$\newcommand{\F}{{\mathbb F}}$ Let's focus on the case $q=2$ which you are primarily interested in. Suppose that $v_1,\dotsc,v_m\in\F_2^n$, and let $V$ be the matrix over $\F_2$ of size $n\times m$ with $v_1,\dotsc,v_m$ (written in the standard basis) as its columns. It is readily seen that for $v_1,\dotsc,v_m$ to be $k$-wise linearly independent, it is necessary and sufficient that the kernel of $V$ did not contain any vector of weight $k$ or less. You are thus asking how large can the length $m$ of a linear code be given that the minimum distance of the code is at least $k+1$, and that the code has co-dimension $n$. This is essentially equivalent to the central problem of coding theory: what is the largest possible dimension of a linear code of given length and minimum distance ($m$ and $k+1$, respectively, in our case)?

added 137 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

$\newcommand{\F}{{\mathbb F}}$ Let's focus on the case $q=2$ which you are primarily interested in. Suppose that $v_1,...,v_m\in\F^n$. Let$v_1,\dotsc,v_m\in\F_2^n$, and let $V$ be the matrix over $\F_2$ of size $n\times m$ with $v_1,...,v_m$$v_1,\dotsc,v_m$ (written in the standard basis) as its columns. ThenIt is readily seen that for $v_1,...,v_m$ areto be $k$-wise linearly independent if, it is necessary and only ifsufficient that the kernel of $V$ does not contain any vector of weight at most $k$ or less. Therefore, your question is equivalent to, arguably, the central problem of coding theory: what is the largest possible dimension of a linear code which doesof length $m$ with the minimal distance at least $k+1$?

$\newcommand{\F}{{\mathbb F}}$ Let's focus on the case $q=2$. Suppose that $v_1,...,v_m\in\F^n$. Let $V$ be the matrix over $\F_2$ with $v_1,...,v_m$ as its columns. Then $v_1,...,v_m$ are $k$-wise linearly independent if and only if the kernel of $V$ does not contain any vector of weight at most $k$. Therefore, your question is equivalent to, arguably, the central problem of coding theory: what is the largest possible dimension of a linear code which does with the minimal distance at least $k+1$?

$\newcommand{\F}{{\mathbb F}}$ Let's focus on the case $q=2$ which you are primarily interested in. Suppose that $v_1,\dotsc,v_m\in\F_2^n$, and let $V$ be the matrix over $\F_2$ of size $n\times m$ with $v_1,\dotsc,v_m$ (written in the standard basis) as its columns. It is readily seen that for $v_1,...,v_m$ to be $k$-wise linearly independent, it is necessary and sufficient that the kernel of $V$ does not contain any vector of weight $k$ or less. Therefore, your question is equivalent to, arguably, the central problem of coding theory: what is the largest possible dimension of a linear code of length $m$ with the minimal distance at least $k+1$?

Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

$\newcommand{\F}{{\mathbb F}}$ Let's focus on the case $q=2$. Suppose that $v_1,...,v_m\in\F^n$. Let $V$ be the matrix over $\F_2$ with $v_1,...,v_m$ as its columns. Then $v_1,...,v_m$ are $k$-wise linearly independent if and only if the kernel of $V$ does not contain any vector of weight at most $k$. Therefore, your question is equivalent to, arguably, the central problem of coding theory: what is the largest possible dimension of a linear code which does with the minimal distance at least $k+1$?