Projection-Forcing Multisets of Weight Changes

Abstract

Let $F$ be a finite field. A multiset $S$ of integers is projection-forcing if for every linear function $\varphi :F^n\to F^m$ whose multiset of weight changes is $S$, $\varphi$ is a coordinate projection up to permutation and scaling of entries. The MacWilliams Extension Theorem from coding theory says that $S=\{0,0,...,0\}$ is projection-forcing. We give a (super-polynomial) algorithm to determine whether or not a given $S$ is projection-forcing. We also give a condition that can be checked in polynomial time that implies that $S$ is projection-forcing. This result is a generalization of the MacWilliams Extension Theorem and work by the first author.

11 Pages