Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Let $C$ be a $[n,k]$ linear code over $\mathbb{F}_q$.
Suppose that $\rho$ is the covering radius .
I want to show that $\rho \leq n-k$.
Could you give me a hint how we could show this?
The covering radius is defined as follows:
$$\rho=\max_{x \in \mathbb{F}_q^n} d(x,C) \\ d(x,C)=\min_{c \in C} d(x,c)$$
You need to show that every vector is at distance at most $n-k$ from a codeword. The code is the collection of all vectors $x$ satisfying $Ax = 0$, where $A$ is an $(n-k) \times n$ matrix, which without loss of generality has the form $A = \begin{bmatrix} I_{n-k} & B \end{bmatrix}$ (use Gaussian elimination, possibly permuting coordinates to avoid zero columns). Let $v$ be a completely arbitrary vector, and suppose that $Av = s$. Extend $s$ to a vector of length $n$ by adding zeroes at the end. Then $A(s + v) = 0$, i.e., $v + s$ is a codeword, which is at distance at most $|s| \leq n-k$ from $v$.
