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

  • 1
    $\begingroup$ Please ask only one question per post. $\endgroup$ Mar 23, 2016 at 21:12

1 Answer 1


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

  • $\begingroup$ With $A$ do you mean the parity matrix? If so , isn't its dimension $(n-k) \times n$ ? @YuvalFilmus $\endgroup$
    – Evinda
    Mar 23, 2016 at 20:28
  • $\begingroup$ Also we have $Av-s=0$. How do we deduce from this that $A(s+v)=0$ ? @YuvalFilmus $\endgroup$
    – Evinda
    Mar 23, 2016 at 20:36
  • $\begingroup$ Using the fact that $A=\begin{bmatrix} I_{n-k} & B \end{bmatrix}$. Try an example. $\endgroup$ Mar 23, 2016 at 20:37
  • $\begingroup$ In this case $|x|$ is the Hamming weight of $x$. Evinda, try to be more resourceful. $\endgroup$ Mar 23, 2016 at 21:00
  • $\begingroup$ If you're interested in that, you're welcome to ask a new question. $\endgroup$ Mar 23, 2016 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.