# Upper bound on the covering radius of a code

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)$$

• Please ask only one question per post. – Yuval Filmus Mar 23 '16 at 21:12

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$.
• With $A$ do you mean the parity matrix? If so , isn't its dimension $(n-k) \times n$ ? @YuvalFilmus – Evinda Mar 23 '16 at 20:28
• Also we have $Av-s=0$. How do we deduce from this that $A(s+v)=0$ ? @YuvalFilmus – Evinda Mar 23 '16 at 20:36
• Using the fact that $A=\begin{bmatrix} I_{n-k} & B \end{bmatrix}$. Try an example. – Yuval Filmus Mar 23 '16 at 20:37
• In this case $|x|$ is the Hamming weight of $x$. Evinda, try to be more resourceful. – Yuval Filmus Mar 23 '16 at 21:00