On a conjecture concerning dyadic oriented matroids

Matt Scobee Department of Mathematics, University of Louisville.

                           scobee@louisville.edu

Submitted: January 7, 1999; Accepted: March 30, 1999

Abstract

A rational matrix is totally dyadic if all of its nonzero subdeterminants are in {±2^{k} : k ∈ Z}. An oriented matriod is dyadic if it has a totally dyadic representation A. A dyadic oriented matriod is dyadic of order k if it has a totally dyadic representation A with full row rank and with the property that for each pair of adjacent bases A_{1} and A_{2}

2^{−k} ≤ |\frac{det(A_{1})}{det(A_{2})}| ≤ 2^{k}.

In this note we present a counterexample to a conjecture on the relationship between the order of a dyadic oriented matroid and the ratio of agreement to disagreement in sign of its signed circuits and cocircuits (Conjecture 5.2, Lee (1990)).

A rational matrix is totally dyadic if all of its nonzero subdeterminants are in {±2^{k} : k ∈ Z}. An oriented matriod is dyadic if it has a totally dyadic representation A. A dyadic oriented matriod is dyadic of order k if it has a totally dyadic representation A with full row rank and with the property that for each pair of adjacent bases A_{1} and A_{2}

2^{−k} ≤ |\frac{det(A_{1})}{det(A_{2})}| ≤ 2^{k}.

In (Lee (1990)) it is shown that the order of a dyadic oriented matroid provides a necessary condition on the ratio of agreement to disagreement in sign of its signed circuits and cocircuits. It is the point of this note to show that this necessary condition is not sufficient (Conjecture 5.2, Lee (1990)).

1 Background

We assume some familiarity with matroid theory (see Oxley (1992)). The ground set of a matroid M is denoted by E(M). For a matrix A over a field F, let M[A] denote the matroid represented by A. Let C(M) (resp., C^{∗}(M)) denote the set of circuits (cocircuits) of a matroid M.

Orientations of a matroid M arise by partitioning (or signing) each circuit X (resp., cocircuit Y) as X^{+}, X^{−} (Y^{+}, Y^{−}) so that

⊥ : (X^{+} ∩ Y^{+}) ∪ (X^{−} ∩ Y^{−}) ≠ ∅ ⟺ (X^{+} ∩ Y^{−}) ∪ (X^{−} ∩ Y^{+}) ≠ ∅

holds for all X ∈ C(M), Y ∈ C(M^{∗}). We note that negating any signed circuit (or cocircuit) by interchanging X^{+} and X^{−} (resp., Y^{+} and Y^{−}) preserves ⊥ for all pairs of signed circuits and cocircuits. If two orientations of the same matroid are related by negating some signed circuits and cocircuits, then we consider the orientations to be identical.

An oriented matroid M is a matroid \underline{M} equipped with a signing that satisfies ⊥. We say that \underline{M} is the matroid underlying M.

Let (I|A) be a matrix over an ordered field F. Each circuit X (resp. cocircuit Y) of M[I|A] naturally partitions into two sets X^{+} and X^{−} (Y^{+} and Y^{−}) depending on the signs of the coefficients in the essentially unique linear-dependence relation ∑_{e∈X} λ_{e}(I|A)_{e} = 0 (∑_{e∈Y} λ_{e}(−A^{T} |I)_{e} = 0) (the uniqueness is up to a nonzero multiple, so the partition can be reversed). The resulting orientation of M[A] is said to be induced by A over F.

Let A be a matrix over an ordered field F, and let M be an oriented matroid. If \underline{M} = M[A] and the orientation of M is identical to the orientation induced by A, then A represents M over F.

Two rational representations of an oriented matroid over an ordered field F are equivalent if one can be obtained from the other through a sequence of elementary row operations, nonzero column scaling, interchanging columns with their labels, and appending or deleting 0-rows.

Proposition 1 (Lee (1990), Proposition 5.3) Any two dyadic representations of the same oriented matroid are equivalent.

The 2-sum of the matrices A = ( \begin{matrix}& e \\ A′ & 0 \\ a & 1 \end{matrix} ) and B = ( \begin{matrix}e \\ 1 & b \\ 0 & B′ \end{matrix} ) on e, denoted

S(A, B, e), is the matrix

( \begin{matrix}A′ & 0 \\ a & b \\ 0 & B′ \end{matrix} ) .

Proposition 2 (Lee (1990), Proposition 2.2) If A and B are totally dyadic matrices, then S(A, B, e) is a totally dyadic matrix.

2 The conjecture

Conjecture (Conjecture 5.2 of Lee (1990)) A dyadic oriented matroid M is dyadic of order k if and only if

4^{−k} ≤ \frac{|(X_{+} ∩ Y_{+}) ∪ (X_{−} ∩ Y_{−})|}{|(X_{+} ∩ Y_{−}) ∪ (X_{−} ∩ Y_{+})|} ≤ 4^{k}

for each circuit X and cocircuit Y such that (X_{+} ∩ Y_{−}) ∪ (X_{−} ∩ Y_{+}) ≠ ∅.

Lee’s conjecture was motivated by (i) the fact that it is true for k = 0, (ii) his short proof of the “only if” direction (see Lemma 5.1, Lee (1990)), and (iii) some evidence for the “if” direction in the case of k = 1. His tangible evidence consisted of his rank-5 10-element matroid J which (i) is dyadic of order 2, (ii) is a (minor) minimal matroid that is not dyadic of order 1, (iii) every orientation has a circuit/cocircuit pair for which the ratio of agreement to disagreement in sign is 5 : 1 (note that this is a smallest matroid that could possibly have this property), and (iv) has a rank-4 8-element minor where the ratio is 4 : 1 (again, this is a smallest matroid that could possibly have this property). In this note we give a counterexample to the “if” direction of this conjecture for each positive integer k.

3 The counterexample

For a fixed positive integer k we define a square matrix D_{k} of order 2(k+1) as follows:

(D_{k})_{ij} = \{ \begin{matrix}1, & if j = 1; \\ 1, & if i = j − 1 and j ≥ 2; \\ 2, & if j = 2 and i ≥ 2; \\ 2, & if i = j = 2k + 2; \\ −1, & if i ≥ j and 3 ≤ j ≤ 2k + 1; \\ 0, & otherwise. \end{matrix}

Let e_{1}, e_{2}, …, e_{2(k+1)} denote the columns of D_{k}. For example, if k = 2, then

D_{2} = ( \begin{matrix}e_{1} & e_{2} & e_{3} & e_{4} & e_{5} & e_{6} \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 \\ 1 & 2 & −1 & 1 & 0 & 0 \\ 1 & 2 & −1 & −1 & 1 & 0 \\ 1 & 2 & −1 & −1 & −1 & 1 \\ 1 & 2 & −1 & −1 & −1 & 2 \end{matrix} ) .

The matrices B_{k} and S_{2k+1} defined below will be used to show that (D_{k}|I) is totally dyadic. The square matrix B_{k} of order 2(k + 1) is defined as follows:

(B_{k})_{ij} = \{ \begin{matrix}1, & if i = j; \\ −1, & if j = i − 1 and 2 ≤ i ≤ 2(k + 1); \\ 0, & otherwise. \end{matrix}

The matrix S_{2k+1} is the result of the following recursion:

S_{2} = S(M_{1}, M_{2}, e_{2}), and
S_{i} = S(S_{i−1}, M_{i}, e_{i}) for i = 3, 4, …, 2k + 1,

where

M_{i} = \{ \begin{matrix}( \begin{matrix}e_{i} & & & e_{i+1} \\ 1 & 1 & 1 & 0 \\ 0 & 1 & −1 & 1 \end{matrix} ), & if i ∈ \{1, 2k + 1\}; \\ ( \begin{matrix}e_{i} & & & e_{i+1} \\ 1 & 1 & 1 & 0 \\ 0 & −1 & −2 & 1 \end{matrix} ), & if i ∈ \{2, 3, …, 2k\}. \end{matrix}

By Proposition 2, S_{i} is totally dyadic for i = 2, 3, …, 2k + 1; in particular, S_{2k+1} is totally dyadic.

Now the columns of B_{k}(D_{k}|I) can be reordered to produce the matrix S_{2k+1}, hence B_{k}(D_{k}|I) is totally dyadic. Next we note that the determinant of a nonsingular square submatrix of (D_{k}|I) is equal to the product of det(B_{k}^{−1}) and the determinant of a square submatrix of B_{k}(D_{k}|I). Since B_{k}(D_{k}|I) is totally dyadic this product is a signed power of 2; hence, (D_{k}|I) is totally dyadic. We let M_{k} denote the dyadic oriented matroid represented by A_{k} = (D_{k}|I).

In what follows we will show that the oriented matroid M_{k} is not dyadic of order k. After establishing this fact we only need note that the rank of the matrix A_{k} is 2(k +1); hence the size of each circuit of M_{k} is bounded by 2(k +1)+1, and therefore

4^{−k} ≤ \frac{1}{2(k + 1)} ≤ \frac{|(X_{+} ∩ Y_{+}) ∪ (X_{−} ∩ Y_{−})|}{|(X_{+} ∩ Y_{−}) ∪ (X_{−} ∩ Y_{+})|} ≤ \frac{2(k + 1)}{1} ≤ 4^{k},

for all X ∈ C and Y ∈ C^{∗}. Hence, M_{k} satisfies the hypothesis of the “if” direction of the conjecture, yet M_{k} is not dyadic of order k.

We begin our proof by considering the following pairs of adjacent bases:

\begin{aligned}B_{1} & = & \{e_{2(k+1)+1}, e_{2}, e_{3}, …, e_{2k+1}, e_{4(k+1)}\} \\ B_{2} & = & \{e_{2(k+1)+1}, e_{4(k+1)−1}, e_{3}, …, e_{2k+1}, e_{4(k+1)}\} \end{aligned}

and

\begin{aligned}B_{3} & = & \{e_{1}, e_{2}, e_{2(k+1)}, e_{2(k+1)+2}, …, e_{4(k+1)−2}\} \\ B_{4} & = & \{e_{1}, e_{4(k+1)−1}, e_{2(k+1)}, e_{2(k+1)+2}, …, e_{4(k+1)−2}\}. \end{aligned}

Routine calculations show that det(B_{1}) = −4^{k}, det(B_{2}) = 1, det(B_{3}) = 1 and det(B_{4}) = 2. Hence, we have the following adjacent base ratios:

\frac{det(B_{1})}{det(B_{2})} = ±4^{k} and \frac{det(B_{3})}{det(B_{4})} = \frac{1}{2}.

Next, we assume that M_{k} is dyadic of order k and that Ak^{′} = (D̃_{k}|I) is a representation of M_{k} that realizes this order. Since A_{k} and Ak^{′} represent the same oriented matroid, we apply Proposition 1 and conclude that A_{k} and Ak^{′} are equivalent representations of M_{k}. Each representation is in standard form with respect to the same base, so we conclude that the columns of A_{k} can be scaled to result in a dyadic matrix Ak^{′′} that represents M_{k} and realizes the order k also. We use c_{1}, c_{2}, …, c_{4(k+1)} ∈ Q to denote the column scalars.

Scaling the columns of A_{k} (to produce Ak^{′′}) has the following effect on \frac{det(B_{1})}{det(B_{2})}

and \frac{det(B_{3})}{det(B_{4})}:

\frac{det(B_{1})}{det(B_{2})} = ±\frac{4^{k}c_{2}}{c_{4(k+1)−1}} and \frac{det(B_{3})}{det(B_{4})} = \frac{c_{2}}{2c_{4(k+1)−1}} .

Now, we have the following inequalities:

2^{−k} ≤ \frac{4^{k}|c_{2}|}{|c_{4(k+1)−1}|}, \frac{|c_{2}|}{2|c_{4(k+1)−1}|} ≤ 2^{k}.  (1)

In particular,

2^{−k} ≤ \frac{|c_{2}|}{2|c_{4(k+1)−1}|} ⟹ 2^{−k+1} ≤ \frac{|c_{2}|}{|c_{4(k+1)−1}|}.

But multiplying by 4^{k} yields

2^{k+1} ≤ \frac{4^{k}|c_{2}|}{|c_{4(k+1)−1}|},

which is a direct violation of (1). We conclude that M_{k} is not dyadic of order k. □

4 Open Questions

The oriented matroid M_{k} is 2-connected but it is not 3-connected as the partition of E(M_{k}) into {e_{1}, e_{2}, e_{2(k+1)+1}} and its complement is a 2-separation of E(M_{k}). This fact motivates the first question.

Question 1 Is Lee’s conjecture true if we assume that the dyadic oriented matroid is 3-connected?

The following related question is also of interest.

Question 2 Is it possible to get a nontrivial bound on the order of a dyadic oriented matroid based on a bound on the ratio of agreement to disagreement in sign for circuit/cocircuit pairs?

Finally, a positive answer to the following question would facilitate further study of the class of dyadic oriented matroids that are dyadic of order k.

Question 3 Is there an efficient combinatorial algorithm for determining the order of a dyadic oriented matroid?

References

[1] Bjorner, A., M. Las Vergnas, B. Sturmfels, N. White and G. Ziegler (1993), “Oriented Matroids”, Cambridge University Press.

[2] Bland, R.G. and M. Las Vergnas (1978), Orientability of matroids, Journal of Combinatorial Theory, Series B 23, 94-123.

[3] Lee, J. (1986), “Subspaces with Well-Scaled Frames”, Doctoral Dissertation, Cornell University.

[4] Lee, J. (1990), The incidence structure of subspaces with well–scaled frames. Journal of Combinatorial Theory, Series B, 50, 265–287.

[5] Oxley, J.G. (1992), “Matroid Theory”, Oxford University Press.