# MacWilliams’ Extension Theorem for rank-metric codes

Elisa Gorla and Flavio Salizzoni

###### Abstract

The MacWilliams’ Extension Theorem is a classical result by Florence Jessie
MacWilliams. It shows that every linear isometry between linear block-codes
endowed with the Hamming distance can be extended to a linear isometry of the
ambient space. Such an extension fails to exist in general for rank-metric
codes, that is, one can easily find examples of linear isometries between
rank-metric codes which cannot be extended to linear isometries of the ambient
space. In this paper, we explore to what extent a MacWilliams’ Extension
Theorem may hold for rank-metric codes. We provide an extensive list of
examples of obstructions to the existence of an extension, as well as a
positive result.

## Introduction and motivation

Coding theory provides tools for the transmission and storage of data over an
imperfect channel, where the data may be altered or lost. One of the main
goals is being able to automatically correct errors in a received message,
without asking for a retransmission. This is done through the use of (error-
correcting) codes: The data to be sent is encoded, i.e., transformed into a
codeword by adding redundancy to it. The set of codewords is called a code.
The codeword travels over the channel, where part of the information may be
lost or corrupted. At the receiver’s end, the received information is decoded,
that is, the error is corrected and the redundancy eliminated. In the
mathematical formulation of error-correcting codes, we usually ignore the step
in which the redundancy is eliminated, since it does not present any
theoretical or practical challenges.

In many scenarios, error correction is done via minimum distance decoding. A
code is a subset of a finite metric space and a received message is decoded to
the closest codeword. Mathematically, if $(S,d)$ is a finite metric space and
$C\subseteq S$ a code, a received $r\in S$ is decoded to an $x\in C$ which
minimizes $d(-,r)$. Under suitable assumptions, the $x$ which minimizes
$d(-,r)$ is unique. One way to guarantee uniqueness is as follows: Define the
minimum distance of a code $C$ as

$d_{\min}(C)=\min\\{d(x,y)\mid x,y\in C,x\neq y\\}.$

It is easy to show that, given $r\in S$, if there is an $x\in C$ such that
$d(x,r)<(d_{\min}(C)-1)/2$, then $x$ is the unique codeword which minimizes
$d(-,r)$. The quantity $(d_{\min(C)}-1)/2$ is often called the error-
correction capability of the code.

This motivates the interest for isometries between codes, since these are the
maps that preserve the pairwise distances of codewords, therefore the metric
structure of the code, and in particular its error-correction capability.
However, one could also look at isometries of the ambient space
$\varphi:S\rightarrow S$. Such an isometry does not only preserve the metric
structure of the code, mapping $C$ to an isometric code $\varphi(C)$, but also
the distance between any pair of elements of $S$, that is
$d(x,r)=d(\varphi(x),\varphi(r))$ for any $x,r\in S$. In particular, $\varphi$
preserves the whole error correction procedure, in the sense that $r\in S$ is
decoded to $x\in C$ if and only if $\varphi(r)\in S$ is decoded to
$\varphi(x)\in\varphi(C)$. In some cases, we know that any isometry between
codes is the restriction of an isometry of the ambient space $S$, that is, any
isometry between codes can be extended to an isometry of the ambient space. In
this paper, we call this property the Extension Property.

Linear block codes endowed with the Hamming distance are used in point-to-
point communication. These are linear subspaces of $\mathbb{F}_{q}^{n}$, where
$\mathbb{F}_{q}$ denotes the finite field with $q$ elements. In [10] Florence
Jessie MacWilliams showed that every Hamming distance-preserving linear
isomorphism $\varphi:\mathcal{C}_{1}\rightarrow\mathcal{C}_{2}$ between two
codes in $\mathbb{F}_{q}^{n}$ can be extended to a Hamming distance-preserving
linear isomorphism $\mu:\mathbb{F}_{q}^{n}\rightarrow\mathbb{F}_{q}^{n}$. An
elementary proof of this fact was later given by Kenneth Bogart, Don Goldberg
and Jean Gordon in [2]. Nowadays, this theorem is known as the MacWilliams’
Extension Theorem.

######  MacWilliams’ Extension Theorem.

Every linear Hamming weight isometry $\varphi$ of linear codes over a finite
field $\mathbb{F}_{q}$ extends to a linear Hamming weight isometry $\mu$ of
the ambient space $\mathbb{F}_{q}^{n}$.

In the last decades, there has been an increasing interest in understanding
for which ambient spaces and for which weights a similar Extension Property
holds. In [14, 15] Jay Wood studied the case of finite rings and established
the Extension Property for codes over finite Frobenius rings with respect to
the Hamming distance. Aleams Barra and Heide Gluesing-Luerssen investigated
further the case of finite Frobenius rings with various distance functions in
[1]. Friedrich Martin Schneider and Jens Zumbrägel extended the work of Wood
to Artinian rings in [12]. Recently, the Extension Property was proved in [5,
9] for codes over $\mathbb{Z}_{m}$ endowed with the Lee distance.

In this paper, we explore the Extension Property in the setting of rank-metric
codes. These are linear spaces of matrices inside $\mathbb{F}_{q}^{m\times
n}$, where $\mathbb{F}_{q}$ is the finite field with $q$ elements. The rank
distance between two matrices is the rank of their difference. Rank-metric
codes are useful for correcting errors and increasing the efficiency of data
transmission over a network.

######  Extension Property.

Let $\mathcal{C}_{1},\mathcal{C}_{2}$ be two linear codes in
$\mathbb{F}_{q}^{m\times n}$. A linear isometry
$\varphi:\mathcal{C}_{1}\rightarrow\mathcal{C}_{2}$ satisfies the Extension
Property if and only if there exists a linear isometry
$\mu:\mathbb{F}_{q}^{m\times n}\rightarrow\mathbb{F}_{q}^{m\times n}$ such
that $\mu|_{\mathcal{C}_{1}}=\varphi$.

It is well known that there exist isometries of rank metric codes that do not
satisfy the Extension Property (see [1] and [3, Section 7]). We are interested
in understanding under which conditions it may be possible to extend an
isometry to the whole ambient space and when instead the Extension Property
fails. Very little is know in this direction. The results in [7] imply that
isometries between two rank support spaces are extendable. The same result for
$\mathbb{F}_{q^{m}}$-isometries between Galois closed linear subspaces of
$\mathbb{F}_{q^{m}}^{n}$ was proved by Umberto Martínez-Peñas in [11, Theorem
5].

In Section 1, we recall some definitions and results on rank-metric codes. In
Section 2 we present an extensive list of obstructions to the Extension
Property, providing multiple examples, while in Section 4 we establish the
Extension Property in a special case. Section 3 is dedicated to developing
some tools that are used in Section 4. Our Main Theorem states that the
Extension Property holds for certain isometries of codes generated by
elementary matrices. In the appendix, we establish some mathematical facts
connected to the proof of the Main Theorem in Section 4.

##  1 Preliminaries on rank-metric codes

Throughout this paper, $q$ is a prime power and $\mathbb{F}_{q}$ denotes the
finite field with $q$ elements. For positive integers $m,n$, we denote by
$\mathbb{F}_{q}^{m\times n}$ the set of $m\times n$ matrices with entries in
$\mathbb{F}_{q}$. We denote by $\mathrm{rank}(M)$ the rank of a matrix
$M\in\mathbb{F}_{q}^{m\times n}$ and by $\dim(V)$ the dimension of an
$\mathbb{F}_{q}$-linear space $V$.

######  Definition 1.1.

The rank distance of $A,B\in\mathbb{F}_{q}^{m\times n}$ is defined as

$\displaystyle d:\mathbb{F}_{q}^{m\times n}\times\mathbb{F}_{q}^{m\times n}$
$\displaystyle\longrightarrow\mathbb{N}$ $\displaystyle(A,B)\qquad$
$\displaystyle\longmapsto\mathrm{rank}(A-B).$

A rank-metric code $\mathcal{C}\subseteq\mathbb{F}_{q}^{m\times n}$ is an
$\mathbb{F}_{q}$-linear subspace endowed with the rank distance.

In order to properly state the Extension Property in the context of rank-
metric codes, we briefly recall the notion of isometric and equivalent codes.

######  Definition 1.2.

Let $\mathcal{C}_{1},\mathcal{C}_{2}$ be two linear codes in
$\mathbb{F}_{q}^{m\times n}$. An $\mathbb{F}_{q}$-linear isomorphism
$\varphi:\mathcal{C}_{1}\rightarrow\mathcal{C}_{2}$ such that
$\mathrm{rank}(C)=\mathrm{rank}(\varphi(C))$ for all $C\in\mathcal{C}_{1}$ is
called isometry and $\mathcal{C}_{1},\mathcal{C}_{2}$ are isometric.

The following classification of the linear isometries of
$\mathbb{F}_{q}^{m\times n}$ is due to Hua [8] for odd characteristic and to
Wan [13] for characteristic 2. The statement can also be found in [6, Theorem
11.1.9].

######  Theorem 1.3.

Let $\varphi:\mathbb{F}_{q}^{m\times n}\rightarrow\mathbb{F}_{q}^{m\times n}$
be an $\mathbb{F}_{q}$-linear isometry with respect to the rank metric.

  1. (a)

If $m\neq n$ then there exist matrices $A\in\mathrm{GL}_{m}(\mathbb{F}_{q})$
and $B\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ such that $\varphi(M)=AMB$ for all
$M\in\mathbb{F}_{q}^{m\times n}$.

  2. (b)

If $m=n$ then there exist matrices $A,B\in\mathrm{GL}_{n}(\mathbb{F}_{q})$
such that either $\varphi(M)=AMB$ for all $M\in\mathbb{F}_{q}^{n\times n}$, or
$\varphi(M)=AM^{t}B$ for all $M\in\mathbb{F}_{q}^{n\times n}$.

######  Definition 1.4.

Two codes $\mathcal{C}_{1},\mathcal{C}_{2}\leq\mathbb{F}_{q}^{m\times n}$ are
equivalent if there exists a linear rank-metric isometry
$\varphi:\mathbb{F}_{q}^{m\times n}\rightarrow\mathbb{F}_{q}^{m\times n}$ such
that $\phi(\mathcal{C}_{1})=\mathcal{C}_{2}$.

According to these definitions and Theorem 1.3, we can formulate the Extension
Property for rank-metric linear codes as follows.

######  Extension Property.

Let $\mathcal{C}_{1},\mathcal{C}_{2}$ be two linear codes in
$\mathbb{F}_{q}^{m\times n}$. An isometry
$\varphi:\mathcal{C}_{1}\rightarrow\mathcal{C}_{2}$ satisfies the Extension
Property if and only if there exist two matrices
$A\in\mathrm{GL}_{m}(\mathbb{F}_{q})$ and
$B\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ such that either $\varphi(M)=AMB$ for
all $M\in\mathcal{C}_{1}$, or $\varphi(M)=AM^{t}B$ for all
$M\in\mathcal{C}_{1}$, where the latter case can only happen if $m=n$.

##  2 Obstructions to the Extension Property

In this section we discuss several obstructions to the Extension Property in
the rank-metric case. A first problem arises from the fact that the
transposition is an isometry of the ambient space only in the square case.
This makes the composition of the transposition with the natural inclusion of
$\iota:\mathbb{F}_{q}^{m\times m}\hookrightarrow\mathbb{F}_{q}^{m\times n}$,
$m\leq n$, into an $\mathbb{F}_{q}$-linear isometry of
$\iota(\mathbb{F}_{q}^{m\times m})\subseteq\mathbb{F}_{q}^{m\times n}$ with
itself, which cannot be extended to $\mathbb{F}_{q}^{m\times n}$. This is a
way of looking at the next example, due to Aleams Barra and Heide Gluesing-
Luerssen.

######  Example 2.1 ([1], Example 2.9).

Let
$\mathcal{C}=\\{\begin{pmatrix}A&0\end{pmatrix}:A\in\mathbb{F}_{q}^{2\times
2}\\}\leq\mathbb{F}_{q}^{2\times 3}$ and let
$\varphi:\mathcal{C}\rightarrow\mathcal{C}$ be the isometry given by
$\varphi(\begin{pmatrix}A&0\end{pmatrix})=\begin{pmatrix}A^{t}&0\end{pmatrix}$
for all $A\in\mathbb{F}_{q}^{2\times 2}$. It is easy to see that it is not
possible to extend $\varphi$ to an isometry of the whole ambient space.

A similar phenomenon happens in the next example, also due to Barra and
Gleusing-Luerssen.

######  Example 2.2 ([1], Example 2.9).

Let $\mathcal{C}\leq\mathbb{F}_{q}^{4\times 4}$ be the code given by

$\mathcal{C}=\left\\{\begin{pmatrix}A&0\\\
0&B\end{pmatrix}:A,B\in\mathbb{F}_{q}^{2\times 2}\right\\}$

and consider the isometry $\varphi:\mathcal{C}\rightarrow\mathcal{C}$ given by

$\varphi\left(\begin{pmatrix}A&0\\\
0&B\end{pmatrix}\right)=\begin{pmatrix}A&0\\\ 0&B^{t}\end{pmatrix}$

As before, one can check that $\varphi$ cannot be extended to an isometry of
$\mathbb{F}_{q}^{4\times 4}$.

In general, the natural inclusion $\iota:\mathbb{F}_{q}^{m\times
m}\times\mathbb{F}_{q}^{n\times
n}\hookrightarrow\mathbb{F}_{q}^{(m+n)\times(m+n)}$ is an isometry with
respect to the sum-rank metric in the domain and the rank metric in the
codomain. When composed with the product of the identity on
$\mathbb{F}_{q}^{m\times m}$ and the transposition on $\mathbb{F}_{q}^{n\times
n}$, it yields an isometry of $\iota(\mathbb{F}_{q}^{m\times
m}\times\mathbb{F}_{q}^{n\times n})\subseteq\mathbb{F}_{q}^{(m+n)\times(m+n)}$
with itself, which does not extend to $\mathbb{F}_{q}^{(m+n)\times(m+n)}$.

We stress that, in both examples there is a smaller, natural ambient space to
which the isometry can be extended. In fact even more, in those specific
examples the isometries are already defined on a smaller ambient space (on
which therefore they can be trivially extended). In the first example, the
isometry is defined on $\mathbb{F}_{q}^{2\times 2}$ while in the second
example it is defined on $\mathbb{F}_{q}^{2\times
2}\times\mathbb{F}_{q}^{2\times 2}$, naturally endowed with the sum-rank
metric. In order to avoid such problems, one may want to consider codes that
cannot be contained in a smaller ambient space, that is, such that
$\operatorname{rowsp}(\mathcal{C})=\mathbb{F}_{q}^{n}$ and
$\operatorname{colsp}(\mathcal{C})=\mathbb{F}_{q}^{m}$.

We now discuss a different obstruction to the Extension Property. Let
$\varphi$ be an isometry of $\mathbb{F}_{q}^{m\times n}$. Then for every
$\mathcal{C}\leq\mathbb{F}_{q}^{m\times n}$ we have that

$\dim(\mathrm{rowsp}(\mathcal{C}))=\dim(\mathrm{rowsp}(\varphi(\mathcal{C})))\text{
and
}\dim(\mathrm{colsp}(\mathcal{C}))=\dim(\mathrm{colsp}(\varphi(\mathcal{C}))).$
(1)

Therefore, in order to be extendable, an isometry must satisfy this property.
The next example shows that not all linear isometries do.

######  Example 2.3.

Let $\mathcal{C}_{1},\mathcal{C}_{2}\in\mathbb{F}_{2}^{2\times 3}$ be the
codes

$\mathcal{C}_{1}=\left\langle\begin{pmatrix}1&1&0\\\
0&1&0\end{pmatrix},\begin{pmatrix}0&1&0\\\
1&0&0\end{pmatrix}\right\rangle\,\,\,\,\,\,\,\mathcal{C}_{2}=\left\langle\begin{pmatrix}0&0&1\\\
0&1&0\end{pmatrix},\begin{pmatrix}0&1&0\\\ 1&0&0\end{pmatrix}\right\rangle$

and let $\varphi:\mathcal{C}_{1}\rightarrow\mathcal{C}_{2}$ be the
$\mathbb{F}_{2}$-linear map given by

$\varphi\left(\begin{pmatrix}1&1&0\\\
0&1&0\end{pmatrix}\right)=\begin{pmatrix}0&0&1\\\
0&1&0\end{pmatrix}\,\,\,\,\,\,\,\varphi\left(\begin{pmatrix}0&1&0\\\
1&0&0\end{pmatrix}\right)=\begin{pmatrix}0&1&0\\\ 1&0&0\end{pmatrix}\,.$

Since $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ are codes of constant rank 2,
then $\varphi$ is an isometry. Notice that
$\dim(\mathrm{rowsp}(\mathcal{C}_{1}))=2$ while
$\dim(\mathrm{rowsp}(\mathcal{C}_{2}))=3$. In particular, $\varphi$ cannot be
extended to an isometry of $\mathbb{F}_{2}^{2\times 3}$.

The last example motivates us to look at isometries
$\varphi:\mathcal{C}_{1}\rightarrow\mathcal{C}_{2}\leq\mathbb{F}_{q}^{m\times
n}$ with the following property, which implies (1).

######  Property 1.

There exist $A\in\mathrm{GL}_{m}(\mathbb{F}_{q})$ and
$B\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ such that

$\mathrm{rowsp}(\varphi(C))=\mathrm{rowsp}(CB)\mbox{ and
}\mathrm{colsp}(\varphi(C))=\mathrm{colsp}(AC)$

for all $C\in\mathcal{C}_{1}$.

Notice that none of the isometries considered in Examples 2.1, 2.2 and 2.3
satisfy Property 1. While Property 1 is necessary for the Extension Property
to hold, it is not sufficient, as the next example shows.

######  Example 2.4.

In [4, Example 1] the authors exhibit three distinct equivalence classes of
MRD codes in $\mathbb{F}_{2}^{4\times 4}$ with minimum distance $4$. Any
$\mathbb{F}_{2}$-linear map between codes in different equivalent classes is
an isometry, since each nonzero element has rank 4. Moreover, each of these
maps satisfy Property 1 with $A=B=\mathrm{Id}$. A proof that these codes do
not satisfy the Extension Property appeared in the first arXiv version of the
same paper as [3, Example 7.1].

The obstruction to the Extension Property in Example 2.4 can be seen as coming
from the interaction between the linear structure of the code and the group
structure of the code without the zero matrix. More precisely, if
$\mathcal{C}$ is a vector space of square matrices and
$\mathcal{C}\setminus\\{0\\}$ is a subgroup of the general linear group, then
every $\mathbb{F}_{q}$-linear isomorphism from $\mathcal{C}$ to itself is a
linear isometry. Moreover, if it fixes the identity and it has the Extension
Property, then it is a group homomorphism. Therefore, any
$\mathbb{F}_{q}$-linear isomorphism from $\mathcal{C}$ to itself which fixes
the identity and is not a group homomorphism cannot have the Extension
Property.

######  Example 2.5.

Let $P\in\operatorname{GL}_{n}(\mathbb{F}_{q})$ of order $q^{n}-1$, let
$Q=P^{q-1}$. Let $\mathcal{C}=\mathbb{F}_{q}[P]=\langle
P\rangle\cup\\{0\\}\subseteq\mathbb{F}_{q}^{n\times n}$. Every nonzero element
of $\mathcal{C}$ has rank $n$, hence any injective $\mathbb{F}_{q}$-linear
isomorphism of $\mathcal{C}$ with itself is an isometry. Both $P$ and $Q$ are
linearly independent from the identity matrix $\mathrm{Id}$, so there is a
linear isometry $\varphi:\mathcal{C}\rightarrow\mathcal{C}$ with
$\varphi(\mathrm{Id})=\mathrm{Id}$ and $\varphi(P)=Q$. If $\varphi$ has the
Extension Property, then either $\varphi(M)=AMA^{-1}$ or
$\varphi(M)=AM^{t}A^{-1}$ for some
$A\in\operatorname{GL}_{n}(\mathbb{F}_{q})$. Therefore
$Q=\varphi(P)\in\\{APA^{-1},AP^{t}A^{-1}\\}$, however $Q$ has order
$q^{n-1}+q^{n-2}+\ldots+1$, while $APA^{-1}$ and $AP^{t}A^{-1}$ have order
$q^{n}-1$.

Even when $\mathcal{C}\setminus\\{0\\}$ is not a group, an isometry on a set
of square matrices which fixes the identity and for which the Extension
Property holds needs to be multiplicative. This constitutes an obstruction to
the Extension Property, since not every linear isometry is multiplicative.

######  Example 2.6.

Let $\mathcal{C}\in\mathbb{F}_{2}^{3\times 3}$ be the code given by

$\mathcal{C}=\left\\{0,\mathrm{Id},\begin{pmatrix}1&0&0\\\ 1&1&0\\\
0&0&0\end{pmatrix},\begin{pmatrix}0&0&0\\\ 1&0&0\\\
0&0&1\end{pmatrix}\right\\}$

and let $\varphi:\mathcal{C}\rightarrow\mathcal{C}$ be the isometry of
$\mathcal{C}$ with itself that fixes the identity matrix and swaps the other
two matrices.

Suppose that $\varphi$ can be extended to an isometry of the whole ambient
space. Then, there are $A,B\in\operatorname{GL}_{3}(\mathbb{F}_{2})$ such that
either $\varphi(C)=ACB$ for all $C\in\mathcal{C}$ or $\varphi(C)=AC^{t}B$ for
all $C\in\mathcal{C}$. Since $\varphi(\mathrm{Id})=\mathrm{Id}$, we have that
$AB=\mathrm{Id}$ and so $B=A^{-1}$. Therefore, we obtain that

$\begin{split}\varphi\left(\begin{pmatrix}1&0&0\\\ 0&1&0\\\
0&0&0\end{pmatrix}\right)&=\varphi\left(\begin{pmatrix}1&0&0\\\ 1&1&0\\\
0&0&0\end{pmatrix}\begin{pmatrix}1&0&0\\\ 1&1&0\\\
0&0&0\end{pmatrix}\right)=\varphi\left(\begin{pmatrix}1&0&0\\\ 1&1&0\\\
0&0&0\end{pmatrix}\right)\varphi\left(\begin{pmatrix}1&0&0\\\ 1&1&0\\\
0&0&0\end{pmatrix}\right)=\\\ &=\begin{pmatrix}0&0&0\\\ 1&0&0\\\
0&0&1\end{pmatrix}\begin{pmatrix}0&0&0\\\ 1&0&0\\\
0&0&1\end{pmatrix}=\begin{pmatrix}0&0&0\\\ 0&0&0\\\
0&0&1\end{pmatrix}\,.\end{split}$

The map $\varphi$ sends an element of rank $2$ to an element of rank $1$,
contradicting the assumption that $\varphi$ is an isometry. We conclude that
$\varphi$ does not have the Extension Property. Notice however that $\varphi$
satisfies Property 1 with

$A=\begin{pmatrix}0&0&1\\\ 1&1&1\\\ 1&0&0\end{pmatrix}\text{ and
}B=\begin{pmatrix}1&0&0\\\ 1&0&1\\\ 1&1&0\end{pmatrix}\,.$

Property 1 suggests to look at codes generated by rank-one elements. In fact,
if $C$ is a rank-one element with row space $\langle u\rangle$ and column
space $\langle v\rangle$, then $\varphi(C)$ is a rank-one element with row
space $\langle uB\rangle$ and column space $\langle Av\rangle$. Therefore,
$\varphi$ determines $Av$ and $uB$ up to a scalar multiple. This simple
observation allows us to prove the next result.

######  Proposition 2.7.

Let $\mathcal{C}_{1},\mathcal{C}_{2}\leq\mathbb{F}_{2}^{m\times n}$ and let
$\varphi:\mathcal{C}_{1}\rightarrow\mathcal{C}_{2}$ be an isometry which
satisfies Property 1. If $\mathcal{C}_{1}$ is generated by elements of rank 1,
then $\varphi$ is extendable.

###### Proof.

Since $\varphi$ has Property 1, then $\varphi(C)$ and $ACB$ have the same row
and column space for all $C\in\mathcal{C}$. Over $\mathbb{F}_{2}$ this give
that $A^{-1}\varphi(C)B^{-1}=C$ for every $C\in\mathcal{C}_{1}$ of rank 1. If
$\mathcal{C}_{1}$ is generated by elements of rank 1, we conclude by linearity
that $A^{-1}\varphi(C)B^{-1}=C$ for all $C\in\mathcal{C}_{1}$. ∎

Even for $\mathcal{C}$ generated by elements of rank $1$, the Extension
Property may fail if we do not require Property 1.

######  Example 2.8.

Let $\mathcal{C}\subseteq\mathbb{F}_{2}^{2\times 3}$ be the linear code
generated by

$C_{1}=\begin{pmatrix}1&0&0\\\
0&0&0\end{pmatrix},\;\;C_{2}=\begin{pmatrix}0&0&0\\\
0&1&0\end{pmatrix},\;\;C_{3}=\begin{pmatrix}0&0&1\\\
0&0&1\end{pmatrix},\;\;C_{4}=\begin{pmatrix}1&1&0\\\ 1&1&0\end{pmatrix}.$

Let $\varphi:\mathcal{C}\rightarrow\mathcal{C}$ be the linear map given by
$\varphi(C_{i})=C_{i}$ for $i=1,2,3$ and $\varphi(C_{4})=C_{4}+C_{3}$. One can
verify that $\varphi$ is an isometry that cannot be extended to the whole
ambient space, since it does not satisfy Property 1.

One may wonder whether the failure of the Extension Property is due to the
fact that the code is small compared to the ambient space. The next example
shows that this is not the case.

######  Example 2.9.

Starting from the code $\mathcal{C}$ from the previous example, for each $n>3$
we construct a code $\mathcal{C}_{n}\in\mathbb{F}_{2}^{2\times n}$ given by

$\mathcal{C}=\left\\{\begin{pmatrix}A&C\end{pmatrix}:A\in\mathbb{F}_{2}^{2\times(n-3)},\,C\in\mathcal{C}\right\\}.$

Let $\varphi_{n}:\mathcal{C}_{n}\rightarrow\mathcal{C}_{n}$ be the linear map
given by $\varphi_{n}\begin{pmatrix}A&0\end{pmatrix}=A$ for
$A\in\mathbb{F}_{2}^{2\times(n-3)}$ and
$\varphi_{n}\begin{pmatrix}0&C\end{pmatrix}=\varphi(C)$. Again, $\varphi_{n}$
is an isometry that cannot be extended to the whole ambient space. Moreover,
notice that

$\lim_{n\to\infty}\frac{\dim(\mathcal{C}_{n})}{\dim\left(\mathbb{F}_{2}^{2\times
n}\right)}=\lim_{n\to\infty}\frac{2n-2}{2n}=1.$

This show that there exist non-extendable isometries defined on codes, whose
dimension comes arbitrarily close to that of the ambient space.

We state the analogous result of Proposition 2.7 for arbitrary $q$ as an open
question.

######  Question 2.10.

Let $\mathcal{C}_{1},\mathcal{C}_{2}\leq\mathbb{F}_{q}^{m\times n}$ and let
$\varphi:\mathcal{C}_{1}\rightarrow\mathcal{C}_{2}$ be an isometry which
satisfies Property 1. If $\mathcal{C}_{1}$ is generated by elements of rank 1,
then the same is true for $\mathcal{C}_{2}$. If this is the case, does
$\varphi$ have the Extension Property?

Our Main Theorem provides a positive answer to Question 2.10, for codes which
are generated by elementary matrices.

Let $1\leq i\leq m$ and $1\leq j\leq n$. We denote by $E_{i,j}$ the matrix in
$\mathbb{F}_{q}^{m\times n}$ that has $1$ in position $(i,j)$ and $0$
everywhere else. We call these matrices elementary. We now state our main
result, which we will prove in Section 4.

######  Main Theorem.

Let $\mathcal{C}=\langle
E_{i_{1},j_{1}},\dots,E_{i_{k},j_{k}}\rangle\leq\mathbb{F}_{q}^{m\times n}$ be
a code generated by $k$ elementary matrices. Let
$\varphi:\mathcal{C}\rightarrow\mathcal{C}$ be an isometry such that for all
$1\leq h\leq k$ one has $\varphi(E_{i_{h},j_{h}})=\alpha_{h}E_{i_{h},j_{h}}$
for some $\alpha_{h}\in\mathbb{F}_{q}^{*}$. Then $\varphi$ satisfies the
Extension Property.

The next example shows that the statement of the Main Theorem fails, if the
code is generated by non-elementary, rank-one matrices.

######  Example 2.11.

Let $q\neq 2$ and let $\mathcal{C}\in\mathbb{F}_{q}^{2\times 4}$ the code
generated by the following elements of rank 1:

$\begin{split}&C_{1}=\begin{pmatrix}1&0&0&0\\\
0&0&0&0\end{pmatrix},\;\;\;C_{2}=\begin{pmatrix}0&0&0&0\\\
0&1&0&0\end{pmatrix},\\\ &C_{3}=\begin{pmatrix}0&0&1&0\\\
0&0&2&0\end{pmatrix},\;\;\;C_{4}=\begin{pmatrix}0&0&0&1\\\
0&0&0&1\end{pmatrix},\;\;\;C_{5}=\begin{pmatrix}0&0&0&0\\\
1&1&1&1\end{pmatrix}.\end{split}$

Let $\alpha\in\mathbb{F}_{q}\setminus\\{0,1\\}$ and let
$\varphi:\mathcal{C}\rightarrow\mathcal{C}$ be the linear map given by
$\varphi(C_{i})=C_{i}$ for $1\leq i\leq 4$ and $\varphi(C_{5})=\alpha C_{5}$.
One can check that $\varphi$ is an isometry and that it does not have the
Extension Property. In fact, $\varphi$ does not satisfies Property 1, since
$\mathrm{rowsp}(C_{5}-C_{2})\leq\mathrm{rowsp}(\sum_{i=1}^{5}C_{i})$ but
$\mathrm{rowsp}(\varphi(C_{5}-C_{2}))\cap\mathrm{rowsp}(\varphi(\sum_{i=1}^{5}C_{i}))=\\{0\\}$.
Notice that, since $\varphi$ does not satisfies Property 1, it does not yield
a negative answer to Question 2.10. In addition, this example shows that it
does not suffice in general to check Property 1 on a system of generators of
the code.

##  3 Matrix paths

In this section we establish some preliminary result which we will use in the
proof of the Main Theorem. We start by introducing the notion of path in a
matrix. From here on, let $m,n\geq 2$.

######  Definition 3.1.

Let $M\in\mathbb{F}_{q}^{m\times n}$ be a matrix. A path $\pi$ of length
$k\in\mathbb{N}$ in $M$ is a finite ordered sequence of positions of nonzero
entries $\left((i_{1},j_{1}),(i_{2},j_{2}),\dots(i_{k},j_{k})\right)$ such
that two consecutive elements share either the first or the second component
and $(i_{h},j_{h})\neq(i_{s},j_{s})$ for $h\neq s$.

A path $\pi$ of length at least $4$ is closed if the first and the last
entries share a component. The support $\mathrm{supp}(\pi)$ of a path $\pi$ is
the set of elements of $\pi$. A path $\pi$ is simple if no three entries of
$\pi$ share a component.

These definitions are borrowed from graph theory. Indeed, one can naturally
associate to every $M\in\mathbb{F}_{q}^{m\times n}$ a finite graph
$G_{M}=(V_{M},E_{M})$, such that $V_{M}$ is the set of positions of the
nonzero entries of $M$ and two vertices in $V_{M}$ are connected by an edge in
$E_{M}$ if and only if the corresponding entries lay on a common line (that
is, a common row or column). The notions of path and closed path from
Definition 3.1 correspond to the usual definitions in graph theory. A path is
simple if the subgraph of $G_{M}$ induced by the set of vertices in the path
does not contain any clique.

We are mainly interested in closed simple paths. We begin by establishing some
of their basic properties. First notice that, up to a cyclic permutation and
to reversing the order, every simple path is determined by its support.
Moreover, in the next lemma we see that the entries corresponding to the
elements of a closed simple path are contained in a square submatrix with
exactly two nonzero elements in each row and column.

######  Lemma 3.2.

Let $M\in\mathbb{F}_{q}^{m\times n}$ be a matrix. The entries of $M$
corresponding to the elements of a closed simple path are contained in a
square submatrix with exactly two nonzero elements in each row and column.

###### Proof.

Let $\pi=\left((i_{1},j_{1}),(i_{2},j_{2}),\dots(i_{k},j_{k})\right)$ be a
closed path in $M$. By definition, each line of $M$ contains at most two
nonzero entries whose position belongs to the support of $\pi$. Suppose by
contradiction that there exists a line in $M$ which contains exactly one
nonzero entry in position $(i_{h},j_{h})$. If $1<h<k$, then the three elements
$(i_{h-1},j_{h-1}),(i_{h},j_{h}),(i_{h+1},j_{h+1})$ have either the first or
the second coordinate in common. If $h=1$, the same is true for
$(i_{1},j_{1}),$ $(i_{2},j_{2}),(i_{k},j_{k})$. If $h=k$, the same holds for
$(i_{1},j_{1}),(i_{k-1},j_{k-1}),(i_{k},j_{k})$. In each case, $\pi$ is not
simple. We conclude that the entries of $M$ corresponding to the elements of a
closed simple path are contained in a square submatrix with exactly two
nonzero elements in each row and column. In particular, it must be that
$2m=2n$ and so $m=n$. ∎

The next proposition ensures that in every matrix with enough nonzero entries
there is a closed simple path.

######  Proposition 3.3.

Let $m,n\geq 2$ and let $M\in\mathbb{F}_{q}^{m\times n}$ be a matrix with at
least $m+n$ nonzero entries. Then there is a closed simple path in $M$.

###### Proof.

We proceed by induction on $m+n$. If $m+n=4$ then $m=n=2$ and all the entries
of the matrix are nonzero and so trivially we have a closed simple path.

Suppose now that $m+n>4$. If there exists a row in which there is at most one
nonzero entry, then $m>2$. By Lemma 3.2 no close simple path can contain the
position of that entry. Therefore, one may erase that row from $M$ and obtain
a matrix of size $(m-1)\times n$ which contains the same paths as $M$.
Similarly, one may erase any column of $M$ which contain a single nonzero
entry without affecting the paths contained in $M$.

By eliminating all rows and columns of $M$ which contain at most one nonzero
entry, we reduce to a matrix which contains at least two nonzero entries in
each row and column. Notice that the operation of canceling any rows and
columns of $M$ which contain at most one nonzero entry preserves the property
that the matrix has at least as many nonzero entries as the sum of its number
of rows and its number of columns. We can now build a closed simple path as
follows. Starting from an arbitrary nonzero entry, move along the
correspondent row and select another nonzero entry. Then move along the column
of last nonzero entry picked and select another nonzero entry. Proceed in this
way, alternating between rows and columns. At every step, we find a nonzero
entry different from the last one that was picked, since we supposed that in
each line we have at least two nonzero entries. Since the number of lines is
finite, after $k$ steps we must choose an entry on a line where there is
already one entry which was picked at a step $h$ with $1\leq h<k-1$. As soon
as that happens, we choose that entry. The positions of the entries that we
have picked are the support of a closed simple path in $M$. ∎

######  Remark 3.4.

The result in Proposition 3.3 is optimal, in the sense that there are matrices
in $\mathbb{F}_{q}^{m\times n}$ with $m+n-1$ nonzero entries that do not
contain any closed simple path. An example is given by

$M=\begin{pmatrix}1&1&\dots&1\\\ 1&0&\dots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
1&0&\dots&0\end{pmatrix}\in\mathbb{F}_{q}^{m\times n}.$

######  Definition 3.5.

Let $m,n\geq 2$ and $M\in\mathbb{F}_{q}^{m\times n}$. We say that a matrix
$M^{\prime}\in\mathbb{F}_{q}^{m\times n}$ is a path-reduction \- or just a
reduction \- of $M$ if it is obtained from $M$ by changing to zero a nonzero
entry that belong to a closed simple path.

A matrix $M\in\mathbb{F}_{q}^{m\times n}$ is path-irreducible \- or just
irreducible \- if does not contain any closed simple path.

Let $M_{1},\dots,M_{\ell}\in\mathbb{F}_{q}^{m\times n}$. We say that
$(M_{1},\dots,M_{\ell})$ is a path-reduction chain if for every $1\leq
i<\ell$, $M_{i+1}$ is a reduction of $M_{i}$ and $M_{\ell}$ is irreducible.

Since in a closed simple path there are at least four entries and a matrix may
have more than one closed simple path, a matrix may have several path-
reductions. We illustrate the situation in the next simple example.

######  Example 3.6.

Consider the matrix $M\in\mathbb{F}_{2}^{3\times 5}$ given by

$M=\begin{pmatrix}1&0&0&1&0\\\ 0&1&0&1&0\\\ 1&1&0&0&0\end{pmatrix}\,.$

The path $((1,1),(1,4),(2,4),(2,2),(3,2),(3,1))$ is closed and simple.
Replacing any of the ones in $M$ yields a reduction of $M$. In particular

$M^{\prime}=\begin{pmatrix}0&0&0&1&0\\\ 0&1&0&1&0\\\
1&1&0&0&0\end{pmatrix}\qquad M^{\prime\prime}=\begin{pmatrix}1&0&0&0&0\\\
0&1&0&1&0\\\ 1&1&0&0&0\end{pmatrix}\,$

are reductions of $M$. Notice that both $M^{\prime}$ and $M^{\prime\prime}$
are irreducible.

The next corollary is an immediate consequence of Proposition 3.3.

######  Corollary 3.7.

Let $M\in\mathbb{F}_{q}^{m\times n}$. If $M$ is irreducible, than $M$ has at
most $m+n-1$ nonzero entries.

Given a matrix $M\in\mathbb{F}_{q}^{m\times n}$, it is always possible to find
a path-reduction chain starting from $M$. In fact, one can simply apply
consecutive reductions. Since $M$ has a finite number of nonzero entries, one
obtains an irreducible matrix in a finite number of steps.

######  Proposition 3.8.

Let $M\in\mathbb{F}_{q}^{m\times n}$. Then there exists a path-reduction chain
$(M_{1},\dots,M_{\ell})$ such that $M_{1}=M$.

Notice that one can find more than one path-reduction chain starting with the
same matrix $M$. In Appendix A we prove that each path-reduction chain with
$M_{1}=M$ has the same length.

######  Example 3.9.

Let $M\in\mathbb{F}_{2}^{3\times 3}$ be the matrix

$M=\begin{pmatrix}1&1&0\\\ 1&1&1\\\ 0&1&1\end{pmatrix}\,.$

Both

$\left(\begin{pmatrix}1&1&0\\\ 1&1&1\\\
0&1&1\end{pmatrix},\begin{pmatrix}0&1&0\\\ 1&1&1\\\
0&1&1\end{pmatrix},\begin{pmatrix}0&1&0\\\ 1&1&1\\\
0&1&0\end{pmatrix}\right),$

and

$\left(\begin{pmatrix}1&1&0\\\ 1&1&1\\\
0&1&1\end{pmatrix},\begin{pmatrix}1&1&0\\\ 1&0&1\\\
0&1&1\end{pmatrix},\begin{pmatrix}1&1&0\\\ 1&0&1\\\ 0&1&0\end{pmatrix}\right)$

are path-reduction chains starting with $M$.

##  4 Proof the Main Theorem

In order to clarify the structure of the proof of the Main Theorem, we enclose
part of it in two technical lemmas. The first one shows under which conditions
two maps coincide on a closed simple path.

######  Lemma 4.1.

Let $M\in\mathbb{F}_{q}^{m\times n}$ and let
$((i_{1},j_{1}),\dots,(i_{k},j_{k}))$ be a closed simple path in $M$. Let
$\varphi,\psi:\langle
E_{i_{1},j_{1}},\dots,E_{i_{k},j_{k}}\rangle\rightarrow\langle
E_{i_{1},j_{1}},\dots,E_{i_{k},j_{k}}\rangle$ two rank-preserving linear maps
such that $\varphi(E_{i_{h},j_{h}})=s_{h}E_{i_{h},j_{h}}$ and
$\psi(E_{i_{h},j_{h}})=t_{h}E_{i_{h},j_{h}}$, where
$s_{1},\dots,s_{k},t_{1},\dots,t_{k}\in\mathbb{F}_{q}^{*}$. If $s_{h}=t_{h}$
for $1\leq h<k$, then $s_{k}=t_{k}$.

###### Proof.

For $a\in\mathbb{F}_{q}^{*}$, consider the matrix

$M_{a}=\left(\sum_{h=1}^{k-1}E_{i_{h},j_{h}}\right)+aE_{i_{k},j_{k}}.$

Since $((i_{1},j_{1}),\dots,(i_{k},j_{k}))$ is a closed simple path, by Lemma
3.2, $k$ is even and the nonzero entries of $M_{a}$ are contained in a square
submatrix of size $k/2$, whose determinant is a linear function of $a$. Hence
there exists $\bar{a}\in\mathbb{F}_{q}^{*}$ such that
$\mathrm{rank}(M_{\bar{a}})=k/2-1$ and $\mathrm{rank}(M_{a})=k/2$ for all
$a\in\mathbb{F}_{q}\setminus\\{\bar{a}\\}$.

Let $M$ be the matrix given by

$M=\left(\sum_{h=1}^{k-1}s_{h}^{-1}E_{i_{h},j_{h}}\right)+\bar{a}s_{k}^{-1}E_{i_{k},j_{k}}.$

By assumption
$\mathrm{rank}(\psi(M))=\mathrm{rank}(M)=\mathrm{rank}(\varphi(M))=k/2-1$.
Moreover, if $s_{h}=t_{h}$ for $1\leq h<k$, then

$\psi(M)=\left(\sum_{h=1}^{k-1}E_{i_{h},j_{h}}\right)+t_{k}\bar{a}s_{k}^{-1}E_{i_{k},j_{k}}\,.$

By the uniqueness of $\bar{a}$ we conclude that
$\bar{a}=t_{k}\bar{a}s_{k}^{-1}$, hence $t_{k}=s_{k}$. ∎

The next lemma establish the Extension Property in a special case.

######  Lemma 4.2.

Let $\varphi:\langle
E_{i_{1},j_{1}},\dots,E_{i_{k},j_{k}}\rangle\rightarrow\langle
E_{i_{1},j_{1}},\dots,E_{i_{k},j_{k}}\rangle\subseteq\mathbb{F}_{q}^{m\times
n}$ be a rank-preserving linear map such that
$\varphi(E_{i_{h},j_{h}})=s_{h}E_{i_{h},j_{h}}$, where
$s_{1},\dots,s_{k}\in\mathbb{F}_{q}$. If the matrix
$M=\sum_{h=1}^{k}E_{i_{h},j_{h}}$ is irreducible, then there are two diagonal
invertible matrices $A\in\mathbb{F}_{q}^{m\times m}$ and
$B\in\mathbb{F}_{q}^{n\times n}$ such that

$\varphi(C)=ACB$

for all $C\in\langle E_{i_{1},j_{1}},\dots,E_{i_{k},j_{k}}\rangle$.

###### Proof.

We build the matrices $A=(a_{i,j})$ and $B=(b_{i,j})$ step by step. Let $h=1$
and set $a_{i_{1},i_{1}}=1$ and $b_{j_{1},j_{1}}=s_{1}$. This guarantees that
$AE_{i_{1},j_{1}}B=s_{1}E_{i_{1},j_{1}}$. At each subsequent step, choose
$h\in\\{1,\ldots,k\\}$ among those that have not been previously chosen and
such that either $a_{i_{h},i_{h}}$ or $b_{i_{h},i_{h}}$ has been assigned a
value, if such an $h$ exists. If $a_{i_{h},i_{h}}$ was already assigned a
value, set $b_{j_{h},j_{h}}=a_{i_{h},i_{h}}^{-1}s_{h}$. If $b_{j_{h},j_{h}}$
was already assigned a value, set $a_{i_{h},i_{h}}=b_{j_{h},j_{h}}^{-1}s_{h}$.

Notice that at most one among $a_{i_{h},i_{h}}$ and $b_{j_{h},j_{h}}$ can
already have an assigned value. Indeed, assume by contradiction that both
$a_{i_{h},i_{h}}$ and $b_{j_{h},j_{h}}$ are fixed. Then there exist two simple
paths $(\alpha_{1},\dots,\alpha_{u})$ and $(\beta_{1},\dots,\beta_{v})$ such
that $\alpha_{1}=\beta_{1}=(i_{1},j_{1})$,
$\alpha_{u}=\beta_{v}=(i_{h},j_{h})$ and $\alpha_{u-1}\neq\beta_{v-1}$. Let
$z>1$ be the smallest index such that $\alpha_{z}\neq\beta_{z}$. Let $N$ be
the inclusion-minimal submatrix of $M$ whose support contains
$\\{\alpha_{z-1},\dots,\alpha_{u},\beta_{z},\dots,\beta_{v-1}\\}$. Let $d,e$
be such that $N$ has size $d\times e$. Notice that $d,e\geq 2$, since
$\alpha_{z-1},\alpha_{z}$, and $\alpha_{u}$ are not aligned. If $\beta_{z}$
and $\alpha_{z}$ are not aligned, then every line of $N$ contains at least two
nonzero entries. Otherwise, $\alpha_{z-1},\alpha_{z}$, and $\beta_{z}$ are
aligned, then any line that does not pass through the position $\alpha_{z-1}$
contains at least two nonzero entries of $N$. Therefore, in both cases, we
have $2\max\\{d,e\\}$ nonzero entries in a submatrix of size $d\times e$.
Since $d+e\leq 2\max\\{d,e\\}$, by Proposition 3.3 there exists a closed
simple path in $N$, contradicting the irreducibility of $M$.

If no such $h$ exists, choose any $h$ among those that have not been
previously chosen and set $a_{i_{h},i_{h}}=1$ and $b_{j_{h},j_{h}}=s_{h}$.
When all values of $h$ have been considered, set to $1$ all the entries on the
diagonal of $A$ and $B$ which have not been assigned a value yet. ∎

######  Remark 4.3.

The matrix $M$ in Lemma 4.2 is irreducible, which by Corollary 3.7 implies
that $\dim(\langle E_{i_{1},j_{1}},\dots,E_{i_{k},j_{k}}\rangle)\leq m+n-1$.
Notice that $m+n-1$ is the number of degree of freedom of the pair of matrices
$A,B$.

We conclude the section with the proof of the Main Theorem.

###### Proof of the Main Theorem.

If $m=1$ or $n=1$, any injective linear map is a linear isometry and the
statement holds. Suppose therefore that $m,n\geq 2$ and let
$M=\sum_{h=1}^{k}E_{i_{h},j_{h}}$. By Proposition 3.8 there exists a path-
reduction chain $(M,M_{2},\dots,M_{\ell})$ with $M_{\ell}$ irreducible.
Consider the subset $R\subseteq\\{1,\dots,k\\}$ such that $M_{\ell}=\sum_{r\in
R}E_{i_{r},j_{r}}$. By Lemma 4.2 there are two invertible matrices $A,B$ such
that

$AE_{i_{r},j_{r}}B=\varphi(E_{i_{r},j_{r}}),$

for all $r\in R$. Following the path-reduction chain and applying $\ell-1$
times Lemma 4.1, we have that $AE_{i_{h},j_{h}}B=\varphi(E_{i_{h},j_{h}})$,
for $1\leq h\leq k$. By linearity we conclude that $\varphi(C)=ACB$ for all
$C\in\mathcal{C}$. ∎

##  Appendix A Length of path-reduction chains

In this appendix, we prove that every path-reduction chain of a matrix
$M\in\mathbb{F}_{q}^{m\times n}$ has the same length.

######  Remark A.1.

Let $M\in\mathbb{F}_{q}^{m\times n}$ and let
$\sigma_{1}=((i_{1},j_{1}),\dots,(i_{k},j_{k}))$ and
$\sigma_{2}=((i^{\prime}_{1},j^{\prime}_{1}),\dots,(i^{\prime}_{h},j^{\prime}_{h}))$
be two closed simple paths. Notice that if
$\mathrm{supp}(\sigma_{1})\neq\mathrm{supp}(\sigma_{2})$, then
$\mathrm{supp}(\sigma_{1})\nsubseteq\mathrm{supp}(\sigma_{2})$ and vice versa.

In the next lemma, we prove that if $M$ contains two distinct closed single
paths, than a path-reduction chain of $M$ has length at least 3.

######  Lemma A.2.

Let $M=(m_{ij})\in\mathbb{F}_{q}^{m\times n}$, let
$\sigma_{1}=((i_{1},j_{1}),\dots,(i_{k},j_{k}))$ and
$\sigma_{2}=((i^{\prime}_{1},j^{\prime}_{1}),\dots,(i^{\prime}_{h},j^{\prime}_{h}))$
be two closed simple paths such that
$\mathrm{supp}(\sigma_{1})\neq\mathrm{supp}(\sigma_{2})$. If
$(i_{1},j_{1})=(i^{\prime}_{1},j^{\prime}_{1})$, then for each
$(i_{s},j_{s})\in\mathrm{supp}(\sigma_{1})\setminus\mathrm{supp}(\sigma_{2})$
there is a closed simple path in $M-m_{i_{1},j_{1}}E_{i_{1},j_{1}}$ that
contains $(i_{s},j_{s})$.

###### Proof.

Up to reversing the order of $\sigma_{2}$ and to a transposition, we may
suppose without loss of generality that
$j_{1}^{\prime}=j_{2}^{\prime}=j_{k}=j_{1}$. As a consequence, also
$i_{1}=i_{2}=i_{h}^{\prime}=i_{1}^{\prime}$. Consider the list of positions

$\gamma=(\gamma_{1},\dots,\gamma_{h+k-2})=((i_{2},j_{2}),\dots,(i_{k},j_{k}),(i^{\prime}_{2},j^{\prime}_{2}),\dots,(i^{\prime}_{h},j^{\prime}_{h})).$

Notice that $\gamma$ is not always a path, since it can contain more than two
entries with the same first or second coordinate, as well as repeated entries.
Fix an $s$ such that
$(i_{s},j_{s})\in\mathrm{supp}(\sigma_{1})\setminus\mathrm{supp}(\sigma_{2})$
and let $\gamma_{x}=(i_{s},j_{s})$. We now recursively build a finite sequence
of simple paths $\pi_{n}$, whose support is contained in that of $\gamma$ and
which start with $\gamma_{x}$. Let $\pi_{1}=(\gamma_{x})$. Suppose that we
have constructed $\pi_{n-1}=(p_{1},\dots,p_{\ell})$ with $p_{1}=\gamma_{x}$
and $p_{\ell}=\gamma_{y}$, with $y=x+n-2$ mod. $h+k-2$ and $\ell\geq 2$. Let
$z=y+1$ mod. $h+k-2$ and define $\pi_{n}$ as follows:

  * •

If no two entries of $\pi_{n-1}$ have either the first or the second
coordinate in common with $\gamma_{z}$, then let
$\pi_{n}=(p_{1},\ldots,p_{\ell},\gamma_{z})$.

  * •

If there exists $1\leq r<t\leq\ell$ such that $p_{r},p_{t}$ and $\gamma_{z}$
share either the first or the second component, then let
$\pi_{n}=(p_{1},\ldots,p_{r},\gamma_{z})$ if $t=r+1$. Notice that if $t\neq
r+1$, then $\pi_{n-1}$ is a closed simple path.

For $n\geq 2$, $\pi_{n}$ is a simple path of length at least $2$. If for some
$n$ we find a closed simple path, then we are done. Else, $\pi_{h+k-2}$ is a
closed simple path, since $\gamma_{x-1}$ and $\gamma_{x}$ lay on a common line
and $\gamma_{x-2}$ and $\gamma_{x+1}$ do not. ∎

The next lemma shows that the length of a path-reduction chain is independent
of the order of the reductions.

######  Lemma A.3.

Let $M\in\mathbb{F}_{q}^{m\times n}$ and let $M,M_{2},\dots,M_{k+1}$ be a
path-reduction chain for $M$. Let $\alpha_{1},\ldots,\alpha_{k}$ be the
ordered list of positions of the entries that we set to zero during the path-
reduction chain. Any permutation of the sequence
$\alpha_{1},\ldots,\alpha_{k}$ still yields a path-reduction chain for $M$.

###### Proof.

Since the group of permutation of $k$ elements is generated by the $k-1$
transpositions $(1,2),(2,3),\ldots,(k-1,k)$, it suffices to prove that setting
to zero the entries in position

$\alpha_{1},\ldots,\alpha_{i-2},\alpha_{i},\alpha_{i-1},\alpha_{i+1},\ldots,\alpha_{k}$

in the given order gives a path-reduction chain for $M$, for $i=2,\ldots,k$.
This corresponds to the sequence of matrices

$M_{1},M_{2},\ldots,M_{i-1},\bar{M}_{i},M_{i+1},M_{i+2},\ldots,M_{k+1}$

where we let $M_{1}=M$. By assumption, $M_{k+1}$ is irreducible and $M_{j}$ is
a reduction of $M_{j-1}$ for $j=2,\ldots,i-1,i+2,\ldots,k$.

The matrix $\bar{M}_{i}$ is obtained from $M_{i-1}$ by setting to zero the
entry in position $\alpha_{i}$. Since $\alpha_{i}$ belongs to a closed simple
path $\pi$ in $M_{i}$ and every nonzero entry in $M_{i}$ is also a nonzero
entry in $M_{i-1}$, then $\pi$ is also a closed simple path in $M_{i-1}$.
Therefore, $\bar{M}_{i}$ is a reduction of $M_{i-1}$. In order to prove that
$M_{i+1}$ is a reduction of $\bar{M}_{i}$, we need to show that there is a
closed simple path in $\bar{M}_{i}$ which contains $\alpha_{i-1}$. Notice that
$\bar{M}_{i}$ is equal to $M_{i}$, except for the entries in position
$\alpha_{i-1}$ and $\alpha_{i}$. By assumption, there are closed simple paths
$\sigma_{1}$ and $\sigma_{2}$ such that $\sigma_{1}$ contains $\alpha_{i-1}$
and $\sigma_{2}$ contains $\alpha_{i}$, but not $\alpha_{i-1}$. If
$\sigma_{1}$ does not contain $\alpha_{i}$, then it is a closed simple path in
$\bar{M}_{i}$ which contains $\alpha_{i-1}$. If instead $\sigma_{1}$ contains
$\alpha_{i}$, then by Lemma A.2 there is a closed simple path in $M_{i}$ which
contains $\alpha_{i-1}$ but not $\alpha_{i}$. This gives a closed simple path
in $\bar{M}_{i}$ which contains $\alpha_{i-1}$. ∎

We are now ready to prove that every path reduction chain of a given matrix
has the same length.

######  Theorem A.4.

Let $M\in\mathbb{F}_{q}^{m\times n}$ be a matrix. Every path-reduction chain
of $M$ has the same length.

###### Proof.

We proceed by induction on the maximum length $\ell$ of a path-reduction chain
of $M$. Notice that $\ell\geq 1$ and equality holds if and only if $M$ is
irreducible. If $\ell=2$, then $M$ needs to have at least one closed simple
path. Moreover, there is an $\alpha$ in the path such every closed simple path
in $M$ contains $\alpha$. If $M$ contains two distinct closed simple paths
through $\alpha$, then by Lemma A.2 it also contains a closed simple path that
does not pass through $\alpha$. It follows that $M$ contains exactly one
closed simple path and every path-reduction chain has length two and is
obtained by replacing with zero one of the entries of $M$ in one of the
positions on the closed simple path.

Let $M,M_{2},\dots,M_{\ell}$ and $M,M_{2}^{\prime},\dots,M_{k}^{\prime}$ be
two path-reduction chains for $M$, $\ell\geq k$. Let
$\alpha_{1},\dots,\alpha_{k-1}$ and $\beta_{1},\dots,\beta_{\ell}$ be the
positions of the entries of $M$ that we replace with zero to obtain the path-
reduction chains $M,M_{2}^{\prime},\dots,M_{k}^{\prime}$ and
$M,M_{2},\dots,M_{\ell}$, respectively. Notice that $M_{2},\dots,M_{\ell}$ is
a path-reduction chain for $M_{2}$ and, by the induction hypothesis, every
path reduction chain for $M_{2}$ has length $\ell-1$. Starting from $M_{2}$,
we construct a path-reduction chain $M_{2},\bar{M}_{3},\ldots,\bar{M}_{\ell}$
as follows. At each step $i=1,\ldots,k-1$, if there is a closed simple path
that contains $\alpha_{i}$, we replace the entry in position $\alpha_{i}$ by
zero. We claim that we delete at most $k-2$ entries of $M_{2}$. In fact, if
setting to zero the entries in position
$\beta_{1},\alpha_{1},\ldots,\alpha_{k-1}$ in the prescribed order yields a
path-reduction chain of $M$, by Lemma A.3 so does setting to zero the entries
in position $\alpha_{1},\ldots,\alpha_{k-1},\beta_{1}$. This contradicts the
assumption that $M,M_{2}^{\prime},\dots,M_{k}^{\prime}$ is a path-reduction
chain. So we have obtained a path-reduction chain for $M_{2}$ of length
$\ell-1\leq k-1$. It follows that $\ell=k$. ∎

## References

  * [1] Aleams Barra and Heide Gluesing-Luerssen.  MacWilliams Extension theorems and the local-global property for codes over Frobenius rings.  Journal of Pure and Applied Algebra, 219(4):703–728, 2015.
  * [2] Kenneth Bogart, Don Goldberg, and Jean Gordon.  An elementary proof of the MacWilliams theorem on equivalence of codes.  Information and control, 37(1):19–22, 1978.
  * [3] Javier de la Cruz, Michael Kiermaier, Alfred Wassermann, and Wolfgang Willems.  Algebraic structures of MRD codes.  Preprint, available at https://arxiv.org/abs/1502.02711v1.
  * [4] Javier de la Cruz, Michael Kiermaier, Alfred Wassermann, and Wolfgang Willems.  Algebraic structures of MRD codes.  Advances in Mathematics of Communications, 10(3):499–510, 2016\.
  * [5] Sergey Dyshko.  The extension theorem for Lee and Euclidean weight codes over integer residue rings.  Designs, Codes and Cryptography, 87(6):1253–1269, 2019.
  * [6] Elisa Gorla.  Rank-metric codes.  In W. Cary Huffman, Jon-Lark Kim, and Patrick Solé, editors, Concise Encyclopedia of Coding Theory, pages 227–250. Chapman and Hall/CRC, 2021\.
  * [7] Marcus Greferath, Thomas Honold, Cathy Mc Fadden, Jay A. Wood, and Jens Zumbrägel.  MacWilliams’ Extension Theorem for bi-invariant weights over finite principal ideal rings.  Journal of Combinatorial Theory, Series A, 125:177–193, 2014.
  * [8] Loo-Keng Hua.  A theorem on matrices over a sfield and its applications.  Acta Mathematica Sinica, Chinese Series, 1(2):109–163, 1951.
  * [9] Philippe Langevin and Jay A. Wood.  The Extension Theorem for the Lee and Euclidean Weights over $\mathbb{Z}/p^{k}\mathbb{Z}$.  Journal of Pure and Applied Algebra, 223(3):922–930, 2019.
  * [10] Florence Jessie MacWilliams.  Combinatorial problems of elementary Abelian groups.  PhD thesis, Harvard University, 1962.
  * [11] Umberto Martínez-Peñas.  On the similarities between generalized rank and Hamming weights and their applications to network coding.  IEEE Transactions on Information Theory, 62(7):4081–4095, 2016\.
  * [12] Friedrich Martin Schneider and Jens Zumbrägel.  MacWilliams’ extension theorem for infinite rings.  Proceedings of the American Mathematical Society, 147:947–961, 2019\.
  * [13] Zhe-Xian Wan.  A proof of the automorphisms of linear groups over a field of characteristic 2.  Scientia Sinica, 11:1183–1194, 1962.
  * [14] Jay A. Wood.  Extension theorems for linear codes over finite rings.  In Teo Mora and Harold Mattson, editors, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes”, pages 329–340, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg.
  * [15] Jay A. Wood.  Duality for modules over finite rings and applications to coding theory.  American Journal of Mathematics, 121(3):555–575, 1999.