%% A Latex2e (Textures for the Mac) with amssymb package (AMS-Latex) file for %% a 4 page document. \documentclass[12pt]{article} %\usepackage{amssymb,psfig} \usepackage{amssymb} \headsep .3in \topmargin -\headheight \oddsidemargin 0in \textheight 8.8in \textwidth 6in \pagestyle{plain} \parindent= 20pt %\input psfig.tex \title{On a conjecture concerning dyadic oriented matroids} \author{Matt Scobee\\ Department of Mathematics,\\ University of Louisville.\\ \small\texttt{scobee@louisville.edu} } \date{Submitted: January 7, 1999; Accepted: March 30, 1999} \renewcommand{\chi}{{\mathcal{X}}} \newcommand{\K}{{\Sigma}} \newcommand{\om}{{M}} \newcommand{\F}{{\bf F}} \newcommand{\D}{{\bf D}} \newcommand{\DZ}{{\bf D}_0} \newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} \newtheorem{theorem}{Theorem} \newtheorem{proposition}{Proposition} \newtheorem{obs}{Observation} \newtheorem{question}{Question} \renewcommand{\Box}{\square} \begin{document} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 6 (1999), \#R23\hfill} \thispagestyle{empty} \maketitle \begin{abstract} A rational matrix is {\em totally dyadic} if all of its nonzero subdeterminants are in $\{\pm 2^k\ :\ k \in {\bf Z}\}$. An oriented matriod is {\em dyadic} if it has a totally dyadic representation $A$. A dyadic oriented matriod is {\em 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} \le \left| \frac{\det(A_1)}{\det(A_2)}\right|\le 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)). \end{abstract} A rational matrix is {\em totally dyadic} if all of its nonzero subdeterminants are in $\{\pm 2^k\ :\ k \in {\bf Z}\}$. An oriented matriod is {\em dyadic} if it has a totally dyadic representation $A$. A dyadic oriented matriod is {\em 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} \le \left| \frac{\det(A_1)}{\det(A_2)}\right|\le 2^k.\] In (Lee (1990)) it is shown that the order of a dyadic oriented matroid provides a {\em 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 {\em sufficient} (Conjecture 5.2, Lee (1990)). \section{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 ${\cal C} (M)$ (resp., ${\cal C}^* (M)$) denote the set of circuits (cocircuits) of a matroid $M$. Orientations of a matroid $M$ arise by partitioning (or {\em signing}) each circuit $X$ (resp., cocircuit $Y$) as $X^+$, $X^-$ ($Y^+$, $Y^-$) so that \[\perp\ :\qquad (X^+\cap Y^+) \cup (X^- \cap Y^-) \neq \emptyset\ \Longleftrightarrow\ (X^+\cap Y^-) \cup (X^- \cap Y^+) \neq \emptyset\] holds for all $X \in {\cal C}(M)$, $Y \in {\cal C}(M^*)$. We note that {\em negating} any signed circuit (or cocircuit) by interchanging $X^+$ and $X^-$ (resp., $Y^+$ and $Y^-$) preserves $\perp$ 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 {\em identical}. An {\em oriented matroid} $M$ is a matroid $\underline{M}$ equipped with a signing that satisfies $\perp$. We say that $\underline{M}$ is the {\em 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 $\sum_{e\in X} \lambda_e (I|A)_e=0$ ($\sum_{e\in Y} \lambda_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 {\em 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$ {\em represents} $M$ over $\F$. Two rational representations of an oriented matroid over an ordered field $\F$ are {\em 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. \begin{proposition}[Lee (1990), Proposition 5.3] Any two dyadic representations of the same oriented matroid are equivalent. \label{lee} \end{proposition} The {\em $2$-sum of the matrices} $A=\bordermatrix{ & &e \cr &A'& 0 \cr &a & 1 \cr }$ and $B=\bordermatrix{ &e & \cr &1 &b \cr &0 &B'\cr}$ {\em on $e$}, denoted $S(A,B,e)$, is the matrix \[\bordermatrix{ & & \cr &A'& 0 \cr &a & b \cr &0 & B' \cr}\ .\] \begin{proposition}[Lee (1990), Proposition 2.2] If $A$ and $B$ are totally dyadic matrices, then $S(A,B,e)$ is a totally dyadic matrix. \label{2-sum-lee} \end{proposition} \section{The conjecture} \noindent{\bf Conjecture (Conjecture 5.2 of Lee (1990))} {\em A dyadic oriented matroid $M$ is dyadic of order $k$ if and only if \[4^{-k} \le \frac{|(X_+ \cap Y_{+}) \cup (X_- \cap Y_-)|}{|(X_+ \cap Y_-) \cup (X_- \cap Y_+)|} \le 4^k\] for each circuit $X$ and cocircuit $Y$ such that $(X_+ \cap Y_-) \cup (X_- \cap Y_+) \neq \emptyset$.} \medskip \noindent 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 ${\cal 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$. \section{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}=\left\{\begin{array}{rl} 1, & \mbox{ if } j=1; \\ 1, & \mbox{ if } i=j-1 \mbox{ and } j\ge 2;\\ 2, & \mbox{ if } j=2 \mbox{ and } i\ge 2; \\ 2, & \mbox{ if } i=j=2k+2; \\ -1, & \mbox{ if } i\ge j \mbox{ and } 3\le j \le 2k+1; \\ 0, & \mbox{otherwise.} \end{array}\right.\] Let $e_1,e_2,\ldots, e_{2(k+1)}$ denote the columns of $D_k$. For example, if $k=2$, then \[D_2=\bordermatrix{ &e_1 & e_2& e_3& e_4&e_5& e_6 \cr &1 &1 & 0 & 0 & 0 & 0 \cr &1 &2 & 1 & 0 & 0 & 0 \cr &1 &2 &-1 & 1 & 0 & 0 \cr &1 &2 &-1 & -1 & 1 & 0 \cr &1 &2 &-1 & -1 & -1& 1 \cr &1 &2 &-1 & -1 & -1& 2 \cr}\ .\] 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}=\left\{\begin{array}{rl} 1, & \mbox{ if } i=j; \\ -1, & \mbox{ if } j=i-1 \mbox{ and } 2 \le i \le 2(k+1);\\ 0, & \mbox{otherwise.} \end{array}\right.\] The matrix $S_{2k+1}$ is the result of the following recursion: \begin{eqnarray*} S_2 &=& S(M_1,M_2,e_2), \mbox{ and}\\ S_i &=& S(S_{i-1},M_i,e_i) \mbox{ for $i=3,4,\ldots,2k+1$,} \end{eqnarray*} where \[M_i=\left\{\begin{array}{ll} \parbox[h]{2in}{$\bordermatrix{ &e_i & & & e_{i+1} \cr &1 &1 & 1 & 0 \cr &0 &1 & -1 & 1 \cr},$} & \mbox{ if $i\in \{1,2k+1\}$};\\ \parbox[h]{2in}{$\bordermatrix{ &e_i & & & e_{i+1} \cr &1 &1 & 1 & 0 \cr &0 &-1 & -2 & 1 \cr},$} & \mbox{ if $i\in \{2,3,\ldots,2k\}$}.\\ \end{array}\right.\] By Proposition \ref{2-sum-lee}, $S_i$ is totally dyadic for $i=2,3,\ldots,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 {\em 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} \le \frac{1}{2(k+1)} \le \frac{|(X_+ \cap Y_{+}) \cup (X_- \cap Y_-)|}{|(X_+ \cap Y_-) \cup (X_- \cap Y_+)|} \le \frac{2(k+1)}{1} \le 4^k,\] for all $X \in {\cal C}$ and $Y \in {\cal 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{array}{lcl} B_1 & = & \{e_{2(k+1)+1},e_2,e_3,\ldots,e_{2k+1},e_{4(k+1)}\}\\ B_2 & = & \{e_{2(k+1)+1},e_{4(k+1)-1},e_3,\ldots,e_{2k+1},e_{4(k+1)}\}\\ \end{array}\] and \[\begin{array}{lcl} B_3 & = & \{e_1,e_2,e_{2(k+1)},e_{2(k+1)+2},\ldots,e_{4(k+1)-2}\}\\ B_4 & = & \{e_1,e_{4(k+1)-1},e_{2(k+1)},e_{2(k+1)+2},\ldots,e_{4(k+1)-2}\}.\\ \end{array}\] Routine calculations %%(using induction) 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)}= \pm 4^k \mbox{ and } \frac{\det(B_3)}{\det(B_4)}=\frac{1}{2}.\] Next, we assume that $M_k$ is dyadic of order $k$ and that $A_k^{'}=(\tilde{D}_k|I)$ is a representation of $M_k$ that realizes this order. Since $A_k$ and $A_k^{'}$ represent the same oriented matroid, we apply Proposition \ref{lee} and conclude that $A_k$ and $A_k^{'}$ 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 $A_k^{''}$ that represents $M_k$ and realizes the order $k$ also. We use $c_1,c_2,\ldots,c_{4(k+1)} \in {\bf Q}$ to denote the column scalars. Scaling the columns of $A_k$ (to produce $A_k^{''}$) has the following effect on $\displaystyle \frac{\det(B_1)}{\det(B_2)}$ and $\displaystyle \frac{\det(B_3)}{\det(B_4)}$: \[\frac{\det(B_1)}{\det(B_2)}=\pm \frac{4^kc_2}{c_{4(k+1)-1}} \mbox{ and } \frac{\det(B_3)}{\det(B_4)}=\frac{c_2}{2c_{4(k+1)-1}}.\] Now, we have the following inequalities: \begin{eqnarray} 2^{-k} \le \frac{4^k|c_2|}{|c_{4(k+1)-1}|},\frac{|c_2|}{2|c_{4(k+1)-1}|} \le 2^k. \end{eqnarray} In particular, \[ 2^{-k} \le \frac{|c_2|}{2|c_{4(k+1)-1}|} \Longrightarrow 2^{-k+1} \le \frac{|c_2|}{|c_{4(k+1)-1}|}.\] But multiplying by $4^k$ yields \begin{eqnarray*} 2^{k+1} \le \frac{4^k|c_2|}{|c_{4(k+1)-1}|}, \end{eqnarray*} which is a direct violation of $(1)$. We conclude that $M_k$ is {\em not } dyadic of order $k$. \hfill $\Box$ \section{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. \begin{question} Is Lee's conjecture true if we assume that the dyadic oriented matroid is $3$-connected? \end{question} The following related question is also of interest. \begin{question} 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? \end{question} 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$. \begin{question} Is there an efficient combinatorial algorithm for determining the order of a dyadic oriented matroid? \end{question} \begin{thebibliography}{99} \bibitem{om} Bjorner, A., M. Las Vergnas, B. Sturmfels, N. White and G. Ziegler (1993), ``Oriented Matroids'', Cambridge University Press. \bibitem{bland} Bland, R.G. and M. Las Vergnas (1978), Orientability of matroids, {\em Journal of Combinatorial Theory, Series B} {\bf 23}, 94-123. \bibitem{leej1} Lee, J. (1986), ``Subspaces with Well-Scaled Frames'', Doctoral Dissertation, Cornell University. \bibitem{leej2} Lee, J. (1990), The incidence structure of subspaces with well--scaled frames. {\em Journal of Combinatorial Theory, Series B}, {\bf 50}, 265--287. \bibitem{oxley} Oxley, J.G. (1992), ``Matroid Theory'', Oxford University Press. \end{thebibliography} \end{document}