数理解析研究所講究録
第 1889 巻 2014 年 7-12

7

On Critical Exponents of Matroids andLinear Codes
Keisuke Shiromoto (keisuke@kumamoto-u.ac.jp)
Department of Mathematics and Engineering,
Kumamoto University,
2-39-1, Kurokami, Kumamoto 860-8555, Japan
Abstract
The critical exponent of a matroid is one of the important parameters in matroid
theory which is related to the critical problem (cf. [6]).
representable matroid over
$GF(q)$ is corresponding to a linear code over $GF(q)$ . In this note, we give a bound on
critical exponents of linear codes and give a construction of linear codes which attainthe equality of the bound.
$A$1

Preliminaries

Let $E$ be a finite set and :if $M$ has the following properties:$\rho$(Rl) If$X\subseteq E$(R2) If$X\subseteq Y\subseteq E$$2^{E}arrow \mathbb{Z}^{+}\cup\{0\}$be a function. $M=(E, \rho)$ is called a matroid, then $0\leq\rho(X)\leq|X|.$, then $\rho(X)\leq\rho(Y)$ .

(R3) If $X$ and $Y$ are subsets of $E$ , then$\rho(X\cup Y)+\rho(X\cap Y)\leq\rho(X)+\rho(Y)$ .

We refer the reader to [9] and [11] for the basic definitions in matroid theory.
For a matroid $M=(\rho, E)$ , the characteristic polynomial $p(M;\lambda)$ of $M$ is defined by$p(M; \lambda)=\sum_{X\subseteq E}(-1)^{|X|}\lambda^{\rho(E)-\rho(X)}.$

Let $M$ be a matroid representable over $GF(q)=\mathbb{F}_{q}$ . It is well known that $p(M;q^{k})\geq 0,$for all. Then the critical exponent $c(M;q)$ of $M$ is defined by$k\in \mathbb{Z}^{+}$$c(M;q)=\{\begin{array}{ll}\infty, if M has a loop;\min\{j\in \mathbb{Z}^{+}:p(M;q^{j})>0\}, otherwise.\end{array}$8Thus if $M$ has no loops, then $p(M;q^{k})>0$ for all $k\geq c(M;q)$ . For a matroid $M$ which isrepresentable over , one of the critical problems is the problem of determining the criticalexponent $c(M;q)$ (cf. [6, 1]). However, this is difficult in general.
The support and weight of each vector
is given by$\mathbb{F}_{q}$$x=(x_{1}, x_{2}, \ldots, x_{n})\in \mathbb{F}_{q}^{n}$$supp(x):=\{i:x_{i}\neq 0\}$ ;wt $(x):=|supp(x)|.$Similarly, the support and weight of each subset$B\subseteq \mathbb{F}_{q}^{n}$are defined as follows:$Supp(B):=\bigcup_{x\in B}supp(x)$;$wt(B):=|Supp(B)|.$be an $[n, k]$ code over , that is, a -dimensional subspace of the vector space. Let be a generator matrix of , that is, amatrix overwhose rows form abasis for . Set $E$ $:=\{1,2, \ldots, n\}$ . For each subset $X\subseteq E$ , the punctured code, denoted, is the linear code obtained by deleting the coordinate $X$ from each codeword inby
. It is easy to check that if we define a function by $\rho(X)=\dim C\backslash (E-X)$ , for any, then $M_{C}=(E, \rho)$ is a matroid, conversely, if $M$ is a representable matroid overthen there exists a linear code $C$ such that $M=M_{C}$ (cf. [11, 9]). Thus, for an $[n, k]$ code
of $C$ is defined byover , the characteristic polynomial
Let$C$$\mathbb{F}_{q}^{n}$$k$$\mathbb{F}_{q}$$k\cross n$

$C$

$G$

$\mathbb{F}_{q}$$C$$C\backslash X$$C$$\rho$$X\subseteq E$$\mathbb{F}_{q},$$p(C;\lambda)$$\mathbb{F}_{q}$$p(C; \lambda)=\sum_{X\subseteq E}(-1)^{|X|}\lambda^{k-\dim C\backslash X},$and the critical exponent $c(C;q)$ of$C$

is defined by$c(C;q)=\{\begin{array}{ll}\infty, if Supp(C)\neq E;\min\{j\in \mathbb{Z}^{+}:p(C;q^{j})>0\}, otherwise.\end{array}$, the shortened code, denoted by $C/X$ , is the linear code obtained
For any subset
by deleting the (zero) coordinates $X$ from each codewords $x\in C$ with $supp(x)\cap X=\emptyset.$
Crap and Rota ([4]) prove the following theorem widely known as the Critical Theorem (cf.
Theorem 2 in [1] .
$X\subseteq E$$0$$)$Lemma 1 (The Critical Theorem) Let be an $[n, k]$ code over . For any, the number of ordered -tuples
anyof codewords
with $supp(v_{1})\cup\cdots\cup supp(v_{m})=X$ is $p(C/X;q^{m})$ .
$C$$m\in \mathbb{Z}^{+}$$m$$\mathbb{F}_{q}$$(v_{1}, \ldots, v_{m})$$v_{1},$$X\subseteq E$$\ldots,$$v_{m}$

andin

$C$

From Lemma 1, if there exists at least one set of $m$ codewords $V=\{v_{1}, \ldots, v_{m}\}$ in $C$
with $Supp(V)=E$ , then $p(C;q^{m})>0$ and so $c(C;q)\leq m$ . For $0\leq r\leq k$ and any $X\subseteq E,$
letbe the number of -dimensional subcodes $D$ of $C$ with $Supp(D)=X$ . We note that$\mathcal{A}_{X}^{(r)}$$r$the polynomial$W_{C}^{(r)}(x, y)= \sum_{i=0}^{n}A_{i}^{(r)}x^{n-i}y^{i}$is the r-th support weight enumerator of $C$ , where
Then we have the following result:$A_{i}^{(r)} \sum_{X\in(\begin{array}{l}E\end{array})}A_{X}^{(r)}$(cf. [5]).

9Proposition 2 Let $C$ be an $[n, k]$ code over$\{1,2, \ldots, n\}$ .
The following are equivalent:

having generator matrix$\mathbb{F}_{q}$$G$and set $E=$

(1) $c(C;q)=m.$(2) $\min\{r : 0\leq r\leq k, A_{E}^{(r)}\neq 0\}=m.$(3) $m$ is the smallest positive integer such that there exists $a(k-m)$ -dimensional subspaceof which does not contain any of the column vectors of $G.$
$U$$n$$\mathbb{F}_{q}^{k}$Bounds on Critical Exponents

2

be amatrix overwhich contains as columns exactly one multiple of eachnonzero vector in . Then the $[n=(q^{k}-1)/(q-1), k]$ code having generator matrix
is a dual Hamming code andis a $[n, n-k, 3]$ Hamming code. It is also known that, for
any $1\leq r\leq k,$
Let$G$$k\cross n$$\mathbb{F}_{q}$$C$$\mathbb{F}_{q}^{k}$$G$$C^{\perp}$$r,$$\sum A_{X}^{(r)}=\{\begin{array}{ll}[Matrix]_{q} i=(q^{k}-q^{k-r})/(q-1) ,0 otherwise,\end{array}$$X\in(\begin{array}{l}Ei\end{array})$

wheredenotes the Gaussian binomial coefficient (cf. [5]). So we have that $i=n$ if andonly if $r=k.$$\{\begin{array}{l}kr\end{array}\}$Proposition 3 If $C$ is a dual Hamming $[n, k]$ code over$\min\{r :$\mathbb{F}_{q}$, then0\leq r\leq k, A_{E}^{(r)}\neq 0\}=k.$

A maximum distance separable (MDS) code overis an $[n, k]$ code overwhoseminimum Hamming weight is $n-k+1$ . According to Theorem 6, p. 321, in [7], the numberof codewords of weight in an MDS $[n, k]$ code overis given by$\mathbb{F}_{q}$$A_{w}$$w$$\mathbb{F}_{q}$$\mathbb{F}_{q}$$A_{w}= (\begin{array}{l}nw\end{array})(q-1)\sum_{j=0}^{w-d}(-1)^{j}(\begin{array}{ll}w -1 j\end{array})q^{w-d-j}$,(1)

for $d\leq w\leq n$ , where $d=n-k+1.$

Theorem 4 Let $C$ be an $MDS[n, k]$ code over$\mathbb{F}_{q}$. Then$c(C;q)\leq 2.$

Remark 5 From Proposition 3, for a $[q+1,2]$ MDS code
So the bound is sharp.

$C$over$\mathbb{F}_{q}$, we have that $c(C;q)=2.$

It is known that a uniform matroid
representable overis corresponding to amatroid obtained by an MDS $[n, m]$ code over(cf. [9]). As a corollary of the above
theorem, we have the following.
$U_{n,m}$$\mathbb{F}_{q}$$\mathbb{F}_{q}$10Corollary 6$c(U_{n,m};q)\leq 2.$

In general, we have the following bound on critical exponents for linear codes over finitefields.

Theorem 7 Let$C$

be an $[n, k]$ code over$\mathbb{F}_{q}$having generator matrix G. If$d^{\perp}>q$, then$c(C;q)\leq k-d^{\perp}+2,$

except when is a binary codes such that $d^{\perp}=n$ is odd or such that $n=2^{k}-1$ and $d^{\perp}=3$denotes the minimum Hamming weight of thein which case $c(C;q)=k-d^{\perp}+3$ , where
dual code$C$$C^{\perp}$$C^{\perp}.$

As a corollary of the above theorem, we have the following $bo$ und on critical exponents
for representable matroids over finite fields.
Corollary 8 Let $M$ be a rank
then$k$representable simple matroid over$\mathbb{F}_{q}$with girth . If $g>q,$$g$$c(M;q)\leq k-g+2,$

except when $M$ is a binary matroid isomorphic to$c(M;q)=k-g+3.$
Example 9 Let$C$$U_{2l+1,2l}$

or $PG(k-1,2)$ in which casebe the ternary [11, 5] code having generator matrix$G=(00001000010000100001000012201122111 20222 02211 02111 20111)$

Then the dual code
have that$C^{\perp}$

is an [11, 6, 5] quadratic residue code. By a Magma calculation, we$A_{E}^{(1)}=0, A_{E}^{(2)}=330, A_{E}^{(3)}=825, A_{E}^{(4)}=110, A_{E}^{(5)}=1,$

is the vector matroid obtained from
where $E=\{1,2, \ldots, 11\}$ . Ifholds the equality in Theorem 7.
$2(=5-5+2)$ and so$M_{C}$$G$, then $c(M_{C};3)=$$M_{C}$

3$A$

construction of tangential blocks

As defined in [3, 6], for $1\leq r\leq k-1$ , a set $M$ of points of the projective geometry
if every $(k-r)$ -dimensional subspace in $PG(k-1, q)$$PG(k-1, q)$ is an -block over
$X$ is a flat in $M$ , a tangent of $X$ is $a(k-r)$ -dimensional$M$.
Ifpointin
one
contains at least
subspace in $PG(k-1, q)$ such that$r$$\mathbb{F}_{q}$$U$$M\cap U=X.$

An -block $M$ is called to be minimal if every point in $M$ has a tangent, and to be tangential
if every proper nonempty flat in $M$ of rank not exceeding $k-r$ has a tangent.
if the following conditions hold:
Alternatively, a matroid $M$ is a tangential -block over
$r$

$r$

$\mathbb{F}_{q}$11(i) $M$ is simple and representable over$\mathbb{F}_{q}.$(ii) $p(M;q^{r})=0.$(iii) $p(M/F;q^{r})>0$ whenever $F$ is a proper nonempty flat of $M.$

Proposition 10 For any positive integer , set $K$ $:=\{1,2, \ldots, k\}$ . For an $m(1\leq m\leq$, we take an $m$ elements subset
and a familyof $(m-1)$ distinct points$v_{m-1}\in PG(k-1, q)$ with $supp(v_{i})\cap T=\emptyset,$ $i=1,2,$$m-1$ . Define$k$$k)$$T\in(\begin{array}{l}Km\end{array})$$v_{1},$ $v_{2},$$\ldots,$$X^{T}$$Y_{\nu}^{T}$$\mathcal{V}$$\ldots,$$:=\{x\in PG(k-1, q) :$:=\{x\in PG(k-1, q) :supp(x)\cap T=\emptyset\},$|supp(x)\cap T|=1\}\backslash \{v_{i}+\lambda e_{j} :v_{i}\in \mathcal{V}, \lambda\in \mathbb{F}_{q}-\{0\}, j\in T\},$$Z^{T}:=\{x\in PG(k-1, q):supp(x)\in(\begin{array}{l}T2\end{array})\}.$

Then $M:=X^{T}\cup Y_{\nu}^{T}\cup Z^{T}$ is $a(k-m)$ -block over$\mathbb{F}_{q}.$Then we can give a construction of tangential blocks as follows:
Theorem 11 Let $M$ be the set of points in $PG(k-1, q)$ defined in Proposition 10.
$m-1\leq q^{k-m-1_{l}}$ then $M$ is a tangential $(k-m)$ -block over $GF(q)$ .

IfFrom the definition, $M$ is a minimal -block over
if and only if $c(C;q)=r+1$ for thelinear code having generator matrix whose column vectors are all points in $M$ (cf. p. 168
in [3] .
$r$$\mathbb{F}_{q}$$G$$)$

Corollary 12 Let $M$ be the set of points defined in Proposition 10. If $m=2$ , then the linear
code $C$ overwhose generator matrix obtained from $M$ attains the bound in Theorem 7.
$\mathbb{F}_{q}$Proof. From the definition of $M$ , it finds that $d^{\perp}=3$ , since there exist three column
vectors in which are linearly dependent. Thus we have that$G$

$k-2+1=k-1=c(C;q)\leq k-3+2=k-1.$$\square$Example 13 Let$C$

be the binary [22, 5] code over$\mathbb{F}_{q}$having generator matrix$G=(00001 00001 0000100001 00001 0001100111 00011 00011 00111 00111 00111 00111 00011 00011 00011 00101 01111 01111 00111 00111 00011)$

From Theorem 11,$G$

forms a binary tangentia13-block. Moreover, we have that$p(M_{C};\lambda)=\lambda^{5}-22\lambda^{4}+175\lambda^{3}-610\lambda^{2}+9-4\lambda-448$$=(\lambda-1)(\lambda-2)(\lambda-4)(\lambda-7)(\lambda-8)$

Ifis the vector matroid obtained fromholds the equality in Theorem 7.
$M_{C}$$G$.

, then $c(M_{C};2)=4(=5-3+2)$ and so$M_{C}$

12References[1] T. Britz, Extensions of the critical theorem, Discrete Mathematics 305 (2005), pp.5573.
[2] T. Britz, Higher support matroids, Discrete Mathematics 307 (2007), pp.2300-2308.

[3] T. Brylawski and J. Oxley, The Tutte polynomial and its applications; Matroid applications, pp. 123-225, Cambridge Univ. Press, Cambridge, 1992.
[4] H. Crapo and G.-C. Rota, On the Foundations of Combinatorial Theory: Combinatorial
geometries, MIT Press, Cambridge, MA, London, 1970 (Preliminary Edition).
, Support weight distribution of linear codes, Discrete Mathematics 106/107[5] T.
(1992), pp. 311-316.
$Kl\emptyset ve$[6] J. P. S. Kung, Critical problems, in: Matroid Theory, Seattle, WA, 1995, Contemporary
Mathematics, 197, American Mathematical Society, Providence, RI, 1996, pp. 1-127.
[7] F. J. MacWilliams and N. J. A. Sloane, TheTheory of Error-Correcting Codes, Amsterdam, The Netherlands: North-Holland, 1977.

[8] J. Oxley, Colouring, packing and the critical problem, Quart. J. Math. Oxford (2), 29(1978), pp. 11-22.
[9] J. Oxley, Matroid Theory, Oxford University Press, New York, 1992.
[10] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge

University Press, 2003.
[11] D. J. A. Welsh, Matroid Theory, Academic Press, London, 1976.