Minimum supports of functions on the Hamming graphs with spectral constraints

Abstract

We study functions defined on the vertices of the Hamming graphs $H(n,q)$. The adjacency matrix of $H(n,q)$ has $n+1$ distinct eigenvalues $n(q-1)-q\cdot i$ with corresponding eigenspaces $U_i(n,q)$ for $0\le i\le n$. In this work, we consider the problem of finding the minimum possible support (the number of nonzeros) of functions belonging to a direct sum $U_i(n,q)\oplus U_{i+1}(n,q)\oplus \dots \oplus U_j(n,q)$ for $0\le i\le j\le n$. For the case $n\ge i+j$ and $q\ge 3$ we find the minimum cardinality of the support of such functions and obtain a characterization of functions with the minimum cardinality of the support. In the case $n<i+j$ and $q\ge 4$ we also find the minimum cardinality of the support of functions, and obtain a characterization of functions with the minimum cardinality of the support for $i=j$, $n<2i$ and $q\ge 5$. In particular, we characterize eigenfunctions from the eigenspace $U_i(n,q)$ with the minimum cardinality of the support for cases $i\le \frac{n}{2}$,$q\ge 3$ and $i>\frac{n}{2}$,$q\ge 5$.

17 pages, 3 figures

References in corpus (3)

• The extended 1-perfect trades in small hypercubes
• On eigenfunctions and maximal cliques of Paley graphs of square order
• The minimum volume of subspace trades

Cited by in corpus (4)

• On existence of perfect bitrades in Hamming graphs
• On the number of relevant variables for discrete functions
• On weight spectrum of linear codes
• On extended 1-perfect bitrades