  Finding the minimum distance of linear codes is an NP-hard problem.
Traditionally, this computation has been addressed by means of the design of
algorithms that find, by a clever exhaustive search, a linear combination of
some generating matrix rows that provides a codeword with minimum weight.
Therefore, as the dimension of the code or the size of the underlying finite
field increase, so it does exponentially the run time. In this work, we prove
that, given a generating matrix, there exists a column permutation which leads
to a reduced row echelon form containing a row whose weight is the code
distance. This result enables the use of permutations as representation scheme,
in contrast to the usual discrete representation, which makes the search of the
optimum polynomial time dependent from the base field. In particular, we have
implemented genetic and CHC algorithms using this representation as a proof of
concept. Experimental results have been carried out employing codes over fields
with two and eight elements, which suggests that evolutionary algorithms with
our proposed permutation encoding are competitive with regard to existing
methods in the literature. As a by-product, we have found and amended some
inaccuracies in the MAGMA Computational Algebra System concerning the stored
distances of some linear codes.
