\documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.26}{23(1)}{2016} %\usepackage{show keys} \usepackage{latexsym} \usepackage{amsmath} \usepackage{amssymb} \usepackage{enumerate} \usepackage{amsthm} %\input{bordersquare} \sloppy %\setlength{\unitlength}{1mm} %\parskip=1em \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newcommand{\ba}{\backslash} \newcommand{\cl}{{\rm cl}} \newcommand{\cB}{{\mathcal B}} \newcommand{\cC}{{\mathcal C}} \newcommand{\cI}{{\mathcal I}} \newcommand{\co}{{\rm co}} \newcommand{\si}{{\rm si}} \title{\bf Determining a Binary Matroid \\ from its Small Circuits} \author{James Oxley \\ \small Department of Mathematics \\ [-0.8ex] \small Louisiana State University \\ [-0.8ex] \small Louisiana, USA \\ \small\tt oxley@math.lsu.edu \\ \and Charles Semple\thanks{Supported by the New Zealand Marsden Fund.} \\ \small School of Mathematics and Statistics \\ [-0.8ex] \small University of Canterbury \\ [-0.8ex] \small Christchurch, New Zealand \\ \small\tt charles.semple@canterbury.ac.nz \\ \and Geoff Whittle$^{*}$ \\ \small School of Mathematics, Statistics and Operations Research \\ [-0.8ex] \small Victoria University of Wellington \\ [-0.8ex] \small Wellington, New Zealand \\ \small\tt geoff.whittle@vuw.ac.nz } \date{\dateline{Jun 30, 2015}{Jan 28, 2016}{Feb 5, 2016} \\ \small Mathematics Subject Classifications: 05B35} \begin{document} \maketitle \begin{abstract} It is well known that a rank-$r$ matroid $M$ is uniquely determined by its circuits of size at most $r$. This paper proves that if $M$ is binary and $r\ge 3$, then $M$ is uniquely determined by its circuits of size at most $r-1$ unless $M$ is a binary spike or a special restriction thereof. In the exceptional cases, $M$ is determined up to isomorphism. \bigskip\noindent \textbf{Keywords:} binary matroids; circuit-hyperplane relaxations \end{abstract} \section{Introduction} A matroid $M$ {\em uses} an element $e$ or a set $X$ if $e\in E(M)$ or $X\subseteq E(M)$. Suppose $M$ is non-binary. Bixby~\cite{bix74} showed that if $M$ is $2$-connected and and $e\in E(M)$, then $M$ has a $U_{2,4}$-minor using $e$. Later, Seymour~\cite{sey81} showed that if $M$ is $3$-connected and $e, f\in E(M)$, then $M$ has a $U_{2,4}$-minor using $\{e, f\}$. In addition, he conjectured that if $M$ is $4$-connected and $e, f, g\in E(M)$, then $M$ has a $U_{2,4}$-minor using $\{e, f, g\}$. Kahn~\cite{kahn85} and Coullard~\cite{cou86} gave counterexamples to this conjecture leaving open the problem of characterising all $4$-connected non-binary matroids that have a $3$-element set that is not used by any $U_{2,4}$-minor (see~\cite[Problem~15.9.7]{ox11}). A rich class of counterexamples to Seymour's conjecture is provided by frame matroids with at least three joints $e$, $f$, and $g$. It is readily checked that, in this case, no circuit contains $e$, $f$, and $g$, and hence, such matroids have no $U_{2, 4}$-minor using $\{e, f, g\}$. A refinement of Seymour's conjecture is to conjecture that if a matroid $M$ is $4$-connected, $e, f, g\in E(M)$, and $M$ has a circuit containing $e$, $f$, and $g$, then $M$ has a $U_{2, 4}$-minor using $\{e, f, g\}$. However, this conjecture is also false. Counterexamples are given by Kahn~\cite{kahn85} and Coullard~\cite{cou86}. Their counterexamples are obtained from binary matroids by relaxing circuit-hyperplanes and, indeed, the only known counterexamples to the modified version of Seymour's conjecture are obtained from binary matroids by relaxing circuit-hyperplanes; Kahn's counterexample relaxes a single circuit-hyperplane; Coullard's example relaxes two circuit-hyperplanes. As a possible approach to solving the modified version of Seymour's conjecture, this paper considers the problem of whether a binary matroid $M$ is uniquely determined by a matroid obtained from $M$ by a sequence of circuit-hyperplane relaxations. Let $J_r$ and $\bf 1$ be the $r\times r$ and $r\times 1$ matrices of all ones. For $r\ge 3$, let $A_r$ be the $r\times (2r+1)$ matrix $[I_r|J_r-I_r|{\bf 1}]$ over $GF(2)$ whose columns are labelled, in order, $x_1, x_2, \ldots, x_r, y_1, y_2, \ldots, y_r, t$. The vector matroid $M[A_r]$ of this matrix is called the {\em rank-$r$ binary spike with tip $t$}. For each $i$ in $\{1, 2, \ldots, r\}$, the set $\{t, x_i, y_i\}$ is a triangle of $M[A_r]$. We call $\{t, x_1, y_1\}, \{t, x_2, y_2\}, \ldots, \{t,x_r, y_r\}$ the {\em legs} of $M[A_r]$. The matroid $M[A_r]\backslash t$ is called the {\em rank-$r$ tipless binary spike}. Its {\em legs} are the sets $\{x_1, y_1\}, \{x_2, y_2\}, \ldots, \{x_r, y_r\}$. Throughout this paper, we will use the term {\em binary spike} to include binary spikes with tips as well as tipless binary spikes. %The reader familiar with spikes will note that we have extended the usual definition of a binary spike to allow it to have rank~$2$. This will be convenient later in the paper. The following is the main result of the paper. As we shall see, most of the effort in proving this result is devoted to verifying the last sentence. \begin{theorem} For $r\ge 3$, let $M$ be a rank-$r$ binary matroid on a given ground set, and suppose that ${\rm si}(M)$ is not isomorphic to $U_{r-1, r}\oplus U_{1, 1}$ or $U_{r, r+1}$. Then $M$ is uniquely determined by its circuits of size at most $r-1$ unless ${\rm si}(M)$ is isomorphic to $M(K_{3,2})$ or can be obtained from a binary spike by deleting at most $r-1$ elements no two of which belong to the same leg. In the exceptional cases, $M$ is uniquely determined up to isomorphism. \label{binary} \end{theorem} Let $M$ be a rank-$r$ binary spike with $r$ in $\{3,4\}$. If $r = 3$ and $M$ has a tip, then any set of three lines through a common point can be chosen as the legs of the spike. If $r = 4$ and $M$ is tipless, then $M \cong AG(3,2)$ and again there are seven different choices for the sets of legs. In these, the only two, cases where there are choices for the sets of legs, the assertion in the theorem that the deleted elements can all be chosen from different legs means that there is a choice of legs for which this is true rather than that this is true for all choices of the legs. For arbitrary $r$ exceeding $2$, consider $M[A_r]$, the binary spike with tip. Let $i$ be an element of $\{1, 2, \ldots, r\}$ and let $\{u_i, v_i\}=\{x_i, y_i\}$. It is well known~\cite[p.66]{ox87} and easily checked that the dual of $M[A_r]\backslash u_i, t$ is isomorphic to the rank-$(r-1)$ binary spike with tip $v_i$. In each of $M[A_r]\backslash t, u_i$ and $M[A_r]\backslash u_i$, we call $v_i$ the {\em cotip}. The last two matroids, which are well known to be unique up to isomorphism, are called, respectively, the {\em rank-$r$ binary spike with a cotip and no tip}, and the {\em rank-$r$ binary spike with a tip and a cotip}. Theorem~\ref{binary} is a strengthening, for binary matroids, of the well-known fact that an arbitrary matroid is uniquely determined by its non-spanning circuits. Observe that, unless $n=1$ or $n=2$, an $n$-element rank-$1$ or rank-$2$ binary matroid is not uniquely determined by its set of circuits of size zero or size at most one, respectively. Also, for $r\ge 3$, the sets of circuits of size at most $r-1$ are the same in $U_{r, r+1}$ and $U_{r-1, r}\oplus U_{1, 1}$. Moreover, for all $r\ge 4$, no rank-$r$ binary spike is uniquely determined by its circuits of size at most $r-1$. To see this, fix $r\ge 4$, and let $M_1$ and $M_2$ be two rank-$r$ binary spikes with tip $t$ and legs $\{t, x_1, y_1\}, \{t, x_2, y_2\}, \ldots, \{t, x_r, y_r\}$ with the property that $\{x_1, x_2, \ldots, x_r\}$ is a basis of $M_1$ and $\{x_1, x_2, \ldots, x_{r-1}, y_r\}$ is a basis of $M_2$. Since $M_1$ and $M_2$ are binary, $\{x_1, x_2, \ldots, x_{r-1}, y_r\}$ is a circuit-hyperplane of $M_1$, and $\{x_1, x_2, \ldots, x_r\}$ is a circuit-hyperplane of $M_2$. Hence $M_1\neq M_2$, but $M_1$ and $M_2$ have the same sets of circuits of size at most $r-1$. Note that, for all $r\ge 4$, we see the same phenomenon when $M_1$ and $M_2$ are both spikes without tips, or are both spikes with tips and cotips, or are both tipless spikes with cotips. However, these exceptions can be eliminated when $r\ge 5$ if we know at least one circuit of size $r$ or $r+1$. \begin{theorem} For $r\ge 5$, let $M$ be a rank-$r$ binary matroid on a given ground set. Let $C^+$ be a fixed circuit of $M$ choosing $|C^+|\ge r$ if possible. Then $M$ is uniquely determined by the collection $$\{C: \mbox{$C\in \mathcal C(M)$ and $|C|\le r-1$}\}\cup \{C^+\}.$$ \label{onemore} \end{theorem} Note that $M(K_4)$ and $M(K_{3,2})$ show that Theorem~\ref{onemore} cannot be extended to allow $r$ to be in $\{3,4\}$. Neither matroid is uniquely determined by any one of its $4$-circuits. The proofs of Theorems~\ref{binary} and~\ref{onemore} are constructive and rely on the preliminary results in the next section. Indeed, the proof of Theorem~\ref{binary} is essentially no more than a packaging of these results. Section~\ref{proofs} consists of the proofs of the two theorems. %The proofs of Theorems~\ref{binary} and~\ref{onemore} are constructive. Briefly, we first find a basis $B$ of $M$. The fact that we can find such a basis is established in the next section. Then, using $B$, we construct a binary representation $[I_r|D]$ of $M$ in standard form. The objective is to determine the columns of $D$. Let $e$ be an element of $E(M)$ that is not in $B$. If the fundamental circuit $C(e, B)$ has size at most $r-1$, then the column of $D$ labelled by $e$ is determined. Thus the main part of the proof involves finding the precise value of each of the columns of $D$ that corresponds to an element $e$ for which $C(e, B)$ has size~$r$ or~$r+1$. In Section~\ref{proof}, we prove both Theorem~\ref{binary} for $r\ge 5$ and Theorem~\ref{onemore}. The proof of Theorem~\ref{binary} for $r\in \{3, 4\}$ is given in Section~\ref{smallrank}. The reason for breaking the proof of Theorem~\ref{binary} into two parts is that if $r\ge 5$, then we can decide if a $4$-element set is a circuit. Knowing which $4$-element sets are circuits is crucial in the analysis when $r\ge 5$. Throughout the paper, notation and terminology follows \cite{ox11}. We shall also freely use the properties of spikes noted there (see, in particular, pp. 41, 73, 74, and 111) as well as the well-known fact that if $C_1$ and $C_2$ are circuits of a binary matroid, then their symmetric difference, $C_1\bigtriangleup C_2$, is a disjoint union of circuits. For convenience, whenever we write ``determined'', we mean ``uniquely determined''. \section{Preliminaries} This section consists of five preliminary results. The first, due to Acketa~\cite{ack88}, lists all binary paving matroids. We denote by $M(K^-_4)$ the cycle matroid of the graph obtained from $K_4$ by deleting an edge. \begin{theorem} An $n$-element binary matroid is paving if and only if it is isomorphic to one of the following matroids: a loopless rank-$2$ matroid with at most three parallel classes, $U_{0, n}$, $U_{1, n}$, $U_{n, n}$, $U_{n-1, n}$, $U_{n-2, n-1}\oplus U_{1, 1}$, $M(K_4^-)$, $M(K_4)$, $M(K_{3, 2})$, $F_7$, $F_7^*$, or $AG(3, 2)$. \label{paving} \end{theorem} Observe that each of the matroids $M(K^-_4)$, $M(K_4)$, $F_7$, $F^*_7$, and $AG(3, 2)$ can be obtained from either a rank-$3$ or rank-$4$ binary spike by deleting at most two elements not belonging to the same leg. \begin{lemma} For $r\ge 4$, let $M$ be a matroid that is obtained from a rank-$r$ binary spike by deleting at most $r-1$ elements no two of which belong to the same leg. Then $M$ can be obtained from a binary spike with a cotip by adding elements in series with the cotip. Thus $M$ is unique up to isomorphism. \label{deleting} \end{lemma} \begin{proof} We prove the lemma when $M$ has a tip $t$. The case when $M$ has no tip is proved similarly. Let $N$ be the rank-$r$ binary spike with tip $t$ and legs $\{t, x_1, y_1\}, \{t, x_2, y_2\}, \ldots, \{t, x_r, y_r\}$. By symmetry, we may assume that $M=N\backslash Z$, where $Z=\{z_1, z_2, \ldots, z_q\}$ and $z_i\in \{x_i, y_i\}$ for all $i$ in $\{1, 2, \ldots, q\}$. Now $N$ has $\{x_j, y_j, x_k, y_k\}$ as a cocircuit for all distinct $j$ and $k$ in $\{1, 2, \ldots, r\}$. Thus, for all distinct $j$ and $k$ in $\{1, 2, \ldots, q\}$, the set $\{x_j, y_j, x_k, y_k\}-Z$ is a disjoint union of cocircuits and hence is a cocircuit. Hence the elements of $\{x_1, y_1, x_2, y_2, \ldots, x_q, y_q\}-Z$ are in series in $M$. By orthogonality, it follows that the last set is a series class in $M$. Contracting all but one element of this series class gives a rank-$(r-q+1)$ binary spike with a tip and a cotip. Hence $M$ is uniquely determined up to isomorphism. \end{proof} %For $r\ge 4$, the next result guarantees that we can find a basis of a simple, binary matroid of rank $r$ using certain subsets of its collection of circuits. % %\begin{lemma} %For $r\ge 4$, let $M$ be a simple rank-$r$ binary matroid on a given ground set. Let $C$ be a circuit of $M$ and let $f\in C$. Then, by using only $C$ and the circuits of $M$ of size at most $r-1$, a basis $B$ of $M$ containing $C-f$ can be found. %\label{basis} %\end{lemma} % %\begin{proof} %If $|C|=r+1$, then $C-f$ is a basis, in which case, choose $B$ to be this basis. We now describe how to find $B$ when $|C|\le r$. In that case, we augment the independent set $C-f$ to an independent set $I$ of size~$r-1$, and let %$$Z=\{z\in E(M): \mbox{$I\cup z$ does not contain a circuit of size at most $r-1$}\}.$$ %Since $M$ has rank~$r$, the set $Z$ is non-empty. If $|Z|=1$, then $I\cup z$ is a basis of $M$, where $Z=\{z\}$, and we take $B=I\cup z$. Thus we may assume that $|Z|\ge 2$. % %Let $z_1$ and $z_2$ be distinct elements in $Z$. If $I\cup z_1$ and $I\cup z_2$ are both dependent, then $I\cup z_1$ and $I\cup z_2$ are both circuits and so, as $M$ is binary, $\{z_1, z_2\}$, which equals $(I\cup z_1)\bigtriangleup (I\cup z_2)$, contains a circuit. This contradicts the hypothesis that $M$ is simple. Hence at least one of $I\cup z_1$ and $I\cup z_2$ is independent, and is therefore a basis of $M$. % %Choosing one of the elements in $\{z_1, z_2\}$, say $z_1$, let %$$Y=(I-C)\cup \{z_1, f\}.$$ %Since $|C|\ge 3$, we have $|Y|\le r-1$ and so we can decide if $Y$ is dependent or independent. Suppose $Y$ is dependent. Then $(I\cup z_1)\cup f$ contains two distinct circuits, namely, $C$ and a circuit contained in $Y$. If $I\cup z_1$ is independent, and therefore a basis, then $(I\cup z_1)\cup f$ contains a unique circuit. Thus $I\cup z_1$ must be dependent, and so $I\cup z_2$ is independent, in which case, we choose $B=I\cup z_2$. % %Now suppose that $Y$ is independent. In that case, we take $B=I\cup z_1$, for, if $I\cup z_1$ is a circuit, then, as $M$ is binary and %$$(I\cup z_1)\bigtriangleup C=(I-C)\cup \{z_1, f\},$$ %we see that $Y$ contains a circuit; a contradiction. %\end{proof} The next two lemmas deal with Theorem~\ref{binary} when the rank-$r$ binary matroid cannot be obtained from a binary spike by deleting at most $r-1$ elements no two of which belong to the same leg. In particular, they enable us to determine which $r$-element subsets of $E(M)$ are bases of $M$. \begin{lemma} For $r\ge 3$, let $M$ be a rank-$r$ binary matroid, and let $B$ be a basis of $M$. Suppose that $M$ is not a restriction of a rank-$r$ binary spike with tip. Then there is a circuit $C$ such that $|C|\le r-1$ and $|C-B|=1$. \label{circuit} \end{lemma} \begin{proof} Let $B=\{e_1, e_2, \ldots, e_r\}$, and construct a binary representation $[I_r|D]$ of $M$ with columns labelled, in order, $e_1, e_2, \ldots, e_r, e_{r+1}, \ldots, e_n$. If there is a $k$ in $\{r+1, r+2, \ldots, n\}$ such that the fundamental circuit $C(e_k, B)$ has size at most $r-1$, then choose $C$ to be $C(e_k, B)$. Otherwise each of the columns in $D$ has either $r-1$ ones or $r$ ones. Since $M$ is simple, it follows that $M$ is a restriction of a rank-$r$ binary spike with tip. \end{proof} \begin{lemma} For $r\ge 3$, let $M$ be a simple rank-$r$ binary matroid. Let $B$ be an $r$-element subset of $E(M)$, and let $C$ be a circuit of $M$ with $|C|\le r$ and $|C-B|=1$. Then $B$ is a basis of $M$ if and only if neither $B$ nor $B\bigtriangleup C$ contains a circuit of size at most $r-1$. \label{basistest} \end{lemma} \begin{proof} First suppose $B$ is a basis of $M$. If $B\bigtriangleup C$ contains a circuit $C'$, then $C'$ contains the element, $f$ say, in $C-B$. But then, as $f\in C\cap C'$, the set $(C\cup C')-\{f\}$ contains a circuit, a contradiction as $(C\cup C')-\{f\}\subseteq B$. Now suppose neither $B$ nor $B\bigtriangleup C$ contains a circuit of size at most $r-1$. It suffices to show that $B$ is not a circuit. Assume the contrary. Then $B\bigtriangleup C$ contains a circuit, which must have size $r$ or $r+1$. But, as $M$ is simple, $|C|\ge 3$ so $|B\bigtriangleup C|\le r-1$; a contradiction. %This completes the proof of the lemma. \end{proof} %A proof of the next lemma is given in~\cite{ox11}. %\begin{lemma} %For $r\ge 3$, a simple rank-$r$ binary matroid $M$ is a rank-$r$ binary spike with tip $t$ and legs $\{t, x_1, y_1\}, \{t, x_2, y_2\}, \ldots, \{t, x_r, y_r\}$ if and only if $E(M)$ is the union of the legs and its set of circuits consists of %\begin{enumerate}[{\rm (i)}] %\item $\{t, x_1, y_1\}, \{t, x_2, y_2\}, \ldots, \{t, x_r, y_r\}$; %\item all sets of the form $\{x_i, y_i, x_j, y_j\}$ with $1\le i< j\le r$; %\item a subset of $\big\{\{z_1, z_2, \ldots, z_r\}:~\mbox{$z_i\in \{x_i, y_i\}$ for all $i$}\big\}$ such that no two members of this subset have more than $r-2$ common elements; and %\item all $(r+1)$-element subsets of $E(M)$ that contain none of the sets in (i)--(iii). %\end{enumerate} %\label{spikecircuits} %\end{lemma} We now use the circuits of size at most $r-1$ to determine whether a simple rank-$r$ binary matroid is a certain restriction of a rank-$r$ binary spike. \begin{lemma} For $r\ge 4$, let $M$ be a simple rank-$r$ binary matroid, and suppose that $M$ is not paving. Then $M$ can be obtained from a rank-$r$ binary spike by deleting at most $r-1$ elements no two of which belong to the same leg if and only if, for some non-empty subset $K$ of $\{1, 2, \ldots, r\}$, the ground set of $M$ can be partitioned into parts $X=\{x_1, x_2, \ldots, x_r\}$, $Y=\{y_k: k\in K\}$, and $Z$, where $|Z|\le 1$, such that the collection of circuits of $M$ of size at most $r-1$ consists of \begin{enumerate}[{\rm (I)}] \item when $|Z| = 1$, all $3$-element sets of the form $\{t, x_k, y_k\}$ with $t\in Z$ and $k\in K$; \item when $r \ge 5$, all $4$-element sets of the form $\{x_k, y_k, x_{l}, y_{l}\}$ with $k, l\in K$; and \item when $r \ge 6$, no sets $D$ with $5\le |D|\le r-1$. \end{enumerate} \label{spiketest} \end{lemma} \begin{proof} The proof is based on \cite[Proposition~1.5.17]{ox11}, which identifies the set of circuits of a spike. It follows immediately from that result that if $M$ can be obtained from a rank-$r$ binary spike by deleting at most $r-1$ elements no two of which belong to the same leg, then $E(M)$ can be partitioned as described in the lemma. For the converse, suppose that $E(M)$ has such a partition. To show that $M$ can be obtained from a binary spike as asserted, first note that, for distinct $r$-element circuits $C$ and $C'$ of $M$, since $C\bigtriangleup C'$ contains a circuit, $|C\cap C'|\le r-2$. %By Lemma~\ref{spikecircuits}, it suffices to complete this part of the proof by showing that if $C$ is not an element in $\big\{\{z_1, z_2, \ldots, z_r\}:~\mbox{$z_i\in \{x_i, y_i\}$ for all $i$}\big\}$, then either $|Y|=1$, $|Z|=1$, and we interchange the roles of the element in $Y$ and the element in $Z$, or $|Y|=2$, $|Z|=0$, and we interchange the roles of the two elements in $Y$ to get the desired outcome. We break the rest of the argument into two cases depending on whether $r\ge 5$ or $r = 4$. Suppose first that $r \ge 5$. Assume that $C$ is not in $\big\{\{z_1, z_2, \ldots, z_r\}:~\mbox{$z_i\in \{x_i, y_i\}$ for all $i$}\big\}.$ Suppose $C\subseteq X\cup Y$. Then, as $|C|\ge 5$, there is a $k$ in $K$ with $x_k, y_k$ in $C$. If $|Z|=1$, then, as $\{t, x_k, y_k\}$ is a circuit, $C\bigtriangleup \{t, x_k, y_k\}$, which equals $(C-\{x_k, y_k\})\cup \{t\}$, contains a circuit containing $t$. But $|(C-\{x_k, y_k\})\cup \{t\}|\le r-1$, so there are no such circuits otherwise $C$ contains a $4$-element circuit of the form in (II). Thus $Z = \emptyset$. If $|Y|=1$, then $M$ is paving, so $|Y|\ge 2$. Suppose there is an $l$ in $K-\{k\}$ such that $x_{l}\in C$ or $y_{l}\in C$. Then, as $M$ is binary, $C\bigtriangleup \{x_k, y_k, x_{l}, y_{l}\}$ contains a circuit of size at most $r-2$. But neither $(C-\{x_k, y_k, x_{l}\})\cup \{y_{l}\}$ nor $(C-\{x_k, y_k, y_{l}\})\cup \{x_{l}\}$ contains a $3$-element or a $4$-element circuit of the form in (I) or (II); a contradiction. Thus, for all $l$ in $K - \{k\}$, the set $\{x_{l},y_{l}\}$ avoids $C$. Hence $|Y|=2$ and, letting $K=\{k, l\}$, we have $C=(X-\{x_{l}\})\cup \{y_k\}.$ Since $M$ is binary, $C\bigtriangleup \{x_k, y_k, x_{l}, y_{l}\}$, which equals $(X-\{x_k\})\cup \{y_{l}\}$, contains a circuit. As no subset of this last set is of the form in (I) or (II), $(X-\{x_k\})\cup \{y_{l}\}$ is a circuit. It is now easily checked that $M$ has exactly three circuits, namely, $\{x_k, y_k, x_{l}, y_{l}\}$, $(X-\{x_{l}\})\cup \{y_k\}$, and $(X-\{x_k\})\cup \{y_{l}\}$, and that $M$ can be obtained from a rank-$r$ tipless binary spike whose legs include $\{x_k, y_{l}\}$ and $\{x_{l}, y_k\}$ by deleting $r-2$ elements no two of which belong to the same leg. We may now assume that $t\in C$ and so $|Z|=1$. Let $k\in K$. Then $\{t, x_k, y_k\}$ is a circuit of $M$, and so, as $M$ is binary, $C\bigtriangleup \{t, x_k, y_k\}$ contains a circuit. If either $x_k\in C$ or $y_k\in C$, then $|C\bigtriangleup \{t, x_k, y_k\}|=r-1,$ and no subset of $C\bigtriangleup \{t, x_k, y_k\}$ is of the form in (I) or (II). Thus neither $x_k\in C$ nor $y_k\in C$. As $|C|=r$, we deduce that $|Y|=1$ and $C=(X-\{x_k\})\cup \{t\}.$ It is now easily checked that the circuits of $M$ are precisely $\{t, x_k, y_k\}$, $(X-\{x_k\})\cup \{t\}$, and $X\cup \{y_k\}$, in which case, $M$ can be obtained from a rank-$r$ binary spike with tip $y_k$ by deleting $r-1$ elements no two of which belong to the same leg. This competes the proof for $r\ge 5$. Now suppose that $r=4$. The approach is similar to that used for $r\ge 5$. Since $M$ is not paving, it has a $3$-circuit and so $|Z|=1$. First note that, by circuit elimination, if $k, l\in K$, then $\{x_k, y_k, x_{l}, y_{l}\}$ is a $4$-circuit as $\{t, x_k, y_k\}$ and $\{t, x_{l}, y_{l}\}$ are both circuits. Let $C$ be a $4$-circuit of $M$ that is not of the form in (II) and is not in $\big\{\{z_1, z_2, z_3, z_4\}:~\mbox{$z_i\in \{x_i, y_i\}$ for all $i$}\big\}.$ Suppose $t\in C$. If, for some $k$ in $K$, either $x_k\in C$ or $y_k\in C$, then, as $M$ is binary, $C\bigtriangleup \{t, x_k, y_k\}$ is a $3$-circuit avoiding $t$; a contradiction. Thus, $|Y|=1$ and so, letting $Y=\{k\}$, it is easily checked that $ {\mathcal C}(M) = \{\{t, x_k, y_k\}, (X-\{x_k\})\cup \{t\}, X\cup \{y_k\}\}$, in which case, $M$ can be obtained from a rank-$r$ binary spike with tip $y_k$ by deleting $r-1$ elements no two of which belong to the same leg. We may now assume that $t\not\in C$, and so, for some $k$ in $K$, we have $\{x_k, y_k\} \subseteq C$. But then $C\bigtriangleup \{t, x_k, y_k\}$ contains a $3$-circuit that is not of the form in (I); a contradiction. This completes the proof of the lemma. \end{proof} \section{Proofs of Theorems~\ref{binary} and~\ref{onemore}} \label{proofs} %This section consists of the proofs of Theorems~\ref{binary} and~\ref{onemore}. \begin{proof}[Proof of Theorem~\ref{binary}] Since $r\ge 3$, we can determine the loops and parallel classes of $M$. By deleting all loops and all but one element of each parallel class, we may assume that $M$ is simple. Moreover, we may assume that $|E(M)| > r$ otherwise $M \cong U_{r,r}$. Suppose $r = 3$. Then $M$ is paving. Since $M$ is isomorphic to neither $U_{3, 4}$ nor $U_{2, 3}\oplus U_{1, 1}$, Theorem~\ref{paving} implies that $M \cong M(K_4^-), M(K_4)$, or $F_7$. Each of these matroids can be obtained from a rank-$3$ binary spike by deleting at most two elements no two from the same leg. Up to isomorphism, the number of elements in $M$ distinguishes $M$. Thus the theorem holds when $r=3$. Suppose $r\ge 4$. Assume $M$ is paving. As $M$ is not isomorphic to $U_{r,r+1}$ or $U_{r-1,r} \oplus U_{1,1}$, Theorem~\ref{paving} implies that $r = 4$ and $M$ is isomorphic to $M(K_{3, 2})$, $F_7^*$, or $AG(3, 2)$. Each of the last two matroids can be obtained from a rank-$4$ binary spike by deleting at most two elements no two from the same leg. Thus, by Lemma~\ref{deleting}, $M$ is unique up to isomorphism. We may now assume that $M$ is not paving. By Lemma~\ref{spiketest}, we can determine when $M$ can be obtained from a rank-$r$ binary spike by deleting at most $r-1$ elements no two of which belong to the same leg. If $M$ can be obtained in this way, then, by Lemma~\ref{deleting}, $M$ is determined up to isomorphism. Therefore, assume that $M$ cannot be obtained in this way. Let $B$ be a subset of $E(M)$ with $|B|=r$. If there is no circuit $C$ with $|C|\le r-1$ and $|C-B|=1$, then, by Lemma~\ref{circuit}, $B$ is not a basis of $M$. But if there is such a circuit $C$, then, by Lemma~\ref{basistest}, $B$ is a basis of $M$ if and only if neither $B$ nor $B\bigtriangleup C$ contains a circuit of size at most $r-1$. Hence we can determine if $B$ is basis of $M$. Thus we can determine the collection of bases of $M$, thereby determining $M$. %This completes the proof of the theorem. \end{proof} \begin{proof}[Proof of Theorem~\ref{onemore}] It follows by Theorem~\ref{binary} that we may assume $M$ has a circuit $C^+$ with $|C^+|\ge r$. Let $f\in C^+$. We next determine a basis $B$ of $M$ with $C^+-\{f\}\subseteq B$. If $|C^+|=r+1$, then choose $B$ to be $C^+-\{f\}$. On the other hand, if $|C^+|=r$, then, by Lemma~\ref{basistest}, we can find a basis of $M$ containing $C^+-\{f\}$, in which case, choose $B$ to be this basis. Let $B=\{e_1, e_2, \ldots, e_r\}$, and construct a binary representation $[I_r|D]$ of $M$ with columns labelled, in order, $e_1, e_2, \ldots, e_r, e_{r+1}, \ldots, e_n$, where $n=|E(M)|$. We complete the proof by determining the columns of $D$. Let $k\in \{r+1, r+2, \ldots, n\}$. If the fundamental circuit $C(e_k, B)$ has size at most $r-1$, then the column $e_k$ is determined. Observing that such a column has at least two ones and at most $r-2$ ones, we see that the columns $e_k$ that are not immediately determined have either $r-1$ ones or $r$ ones. Since $M$ is binary and simple, there is at most one column $e_k$ of $D$ with $|C(e_k, B)|=r+1$. Let $e_l$ denote the column of $D$ corresponding to $f$. Then $e_l$ is determined. If $|C(e_l, B)|=r+1$, then, for $k \neq l$, the unique zero in column $e_k$ is in row $i$ if and only if $\{e_i, e_k, e_l\}$ is a circuit. Since $r(M)\ge 5$, we can decide if $\{e_i, e_k, e_l\}$ is a circuit, and so we can determine $e_k$, and thus determine $M$. Now suppose that $|C(e_{l}, B)|=r$. Then the column $e_l$ has exactly one zero, say in row~$i$. For $k \neq l$, the column $e_k$ has no zeros if and only if $\{e_i, e_k, e_l\}$ is a circuit. Furthermore, if the column $e_k$ has exactly one zero, then it is in row $j$ if and only if $\{e_i, e_j, e_k, e_l\}$ is a circuit, where $i\neq j$. Since $r(M)\ge 5$, we can decide if $\{e_i, e_k, e_l\}$ and $\{e_i, e_j, e_k, e_l\}$ are circuits, and so we can determine $e_k$. Hence $M$ is determined. %completing the proof of Theorem~\ref{onemore}. \end{proof} \section*{Acknowledgement} The authors thank an anonymous referee for suggesting a proof of Theorem~\ref{binary} that significantly shortened the original proof. %\section{When the Rank Exceeds Four} %\label{proof} % %In this section, we simultaneously prove Theorem~\ref{binary} for $r\ge 5$ and Theorem~\ref{onemore}. % %\begin{proof} %Since $r\ge 5$, we can determine the loops and parallel classes of $M$. By deleting all loops and all but one element of each parallel class, we may assume that $M$ is simple. Furthermore, if $n=r$, then $M$ is isomorphic to $U_{r, r}$, so we may assume that $n>r$. It now follows by Theorem~\ref{paving} that if $M$ is paving, then $M$ is isomorphic to either $U_{n-1, n}$ or $U_{n-2, n-1}\oplus U_{1, 1}$. For the proof of Theorem~\ref{onemore}, if $M$ is paving, then $M$ contains a unique circuit and the size of this circuit determines $M$ up to isomorphism. Thus we may assume that $M$ is not paving. % %We next find a basis $B$ of $M$. If we are given, as in the statement of Theorem~\ref{onemore}, a circuit of size $r$ or $r+1$, let $C$ be this circuit; otherwise, let $C$ be a circuit of size at most $r-1$. Let $f\in C$. By Lemma~\ref{basis}, we can find a basis of $M$ containing $C-f$. Choose $B$ to be this basis. % %Now construct a binary representation $[I_r|D]$ of $M$ with columns labelled, in order, $e_1, e_2, \ldots, e_r, e_{r+1}, \ldots, e_n$, where $n=|E(M)|$. Label the rows of $D$ by $e_1, e_2, \ldots, e_r$. Let $k\in \{r+1, r+2, \ldots, n\}$. If the fundamental circuit $C(e_k, B)$ has size at most $r-1$, then the column $e_k$ is determined. Observing that such a column has at least two ones and at most $r-2$ ones, we see that the columns $e_k$ that are not immediately determined have either $r-1$ ones or $r$ ones, in which case, $C(e_k, B)$ has size $r$ or $r+1$, respectively. Call a column $e_k$ of $D$ {\em big} if $|C(e_k, B)|\in \{r, r+1\}$. Since $M$ is binary and simple, there is at most one column $e_k$ of $D$ with $|C(e_k, B)|=r+1$. % %\begin{noname} %If a big column of $D$ has been determined, then $M$ is determined. %\label{big} %\end{noname} % %Let $e_k$ be a big column of $D$ that has been determined. Let $e_l$ be a big column of $D$ with $k\neq l$. Suppose first that $|C(e_k, B)|=r+1$. Then the unique zero in column $e_l$ is in row $i$ if and only if $\{e_i, e_k, e_l\}$ is a circuit. Since $r(M)\ge 5$, we can decide if $\{e_i, e_k, e_l\}$ is a circuit, and so we can determine column $e_l$, and thus determine $M$. % %Now suppose that $|C(e_k, B)|=r$. Then the column $e_k$ has exactly one zero, say in row~$i$. The column $e_l$ has no zeros if and only if $\{e_i, e_k, e_l\}$ is a circuit. Furthermore, if the column $e_l$ has exactly one zero, then it is in row $j$ if and only if $\{e_i, e_j, e_k, e_l\}$ is a circuit, where $i\neq j$. Since $r(M)\ge 5$, we can decide if $\{e_i, e_k, e_l\}$ and $\{e_i, e_j, e_k, e_l\}$ are circuits, and so we can determine $e_l$. Hence $M$ is determined. This completes the proof of~(\ref{big}). % %Theorem~\ref{onemore} now follows from (\ref{big}). In particular, if the circuit $C$ considered at the beginning of the proof has size $r$ or $r+1$, then the column corresponding to $f$ is immediately determined, and so, by~(\ref{big}), $M$ is determined. We now complete the proof of Theorem~\ref{binary} for $r\ge 5$. % %\begin{noname} %If there is a column $e_k$ of $D$ such that $5\le |C(e_k, B)|\le r-1$, then $M$ is determined. %\label{small} %\end{noname} % %Let $e_l$ be a big column of $D$. After possible row and column swaps, we may assume that the zeros in column $e_k$ are in rows $1, 2, \ldots, r-q$, where $q+1=|C(e_k, B)|$. Now column $e_l$ has no zeros if and only if %\begin{align*} %\{e_1, e_2, \ldots, e_{r-q}, e_k, e_l\} %\end{align*} %is a circuit. Since $q\ge 4$, we have $|\{e_1, e_2, \ldots, e_{r-q}, e_k, e_l\}|\le r-2$. Thus we can decide if $\{e_1, e_2, \ldots, e_{r-q}, e_k, e_l\}$ is a circuit, and so we decide if $e_l$ has no zeros. % %We may now assume that column $e_l$ has exactly one zero. Then, when $1\le i\le r-q$, this zero is in row~$i$ if and only if %\begin{align} %\{e_1, e_2, \ldots, e_{i-1}, e_{i+1}, \ldots, e_{r-q}, e_k, e_l\} %\label{set2} %\end{align} %is a circuit and, when $r-q+1\le j\le r$, this zero is in row~$j$ if and only if %\begin{align} %\{e_1, e_2, \ldots, e_{r-q}, e_j, e_k, e_l\} %\label{set3} %\end{align} %is a circuit. Since $q\ge 4$, we have %$$|\{e_1, e_2, \ldots, e_{i-1}, e_{i+1}, \ldots, e_{r-q}, e_k, e_l\}|\le r-3$$ %and %$$|\{e_1, e_2, \ldots, e_{r-q}, e_j, e_k, e_l\}|\le r-1,$$ and so we can decide if the sets~(\ref{set2}) and~(\ref{set3}) are circuits. Thus we can determine the column $e_l$ and so, by (\ref{big}), $M$ is determined. % %Next we establish that if $D$ has at least three big columns, $e_k$, $e_l$, and $e_m$, then $M$ is determined. Recall that at most one big column of $D$ has no zeros. % %\begin{noname} %For distinct $i$ and $j$, column $e_k$ has no zeros, and columns $e_l$ and $e_m$ have zeros in rows $i$ and $j$, respectively, if and only if $\{e_i, e_k, e_l\}$ and $\{e_j, e_k, e_m\}$ are both circuits. %\label{3big1} %\end{noname} % %To see this, suppose that $\{e_i, e_k, e_l\}$ and $\{e_j, e_k, e_m\}$ are both circuits. The circuit $\{e_i, e_k, e_l\}$ implies that either column $e_k$ or column $e_l$ has no zeros, while the circuit $\{e_j, e_k, e_m\}$ implies that either column $e_k$ or column $e_m$ has no zeros. Thus column $e_k$ has no zeros, and $e_l$ and $e_m$ have zeros in rows $i$ and $j$, respectively. The converse is immediate. % %A similar argument to that given for~(\ref{3big1}) establishes the following. % %\begin{noname} %For distinct $h$, $i$, and $j$, columns $e_k$, $e_l$, and $e_m$ have zeros in rows $h$, $i$, and $j$, respectively, if and only if each of $\{e_h, e_i, e_k, e_l\}$, $\{e_h, e_j, e_k, e_m\}$, and $\{e_i, e_j, e_l, e_m\}$ is a circuit. %\label{3big2} %\end{noname} % %Now, since $r(M)\ge 5$, we can decide if any $3$-element or $4$-element subset of $E(M)$ is a circuit. Thus, if $M$ has at least three big columns, then, by~(\ref{3big1}) and~(\ref{3big2}), we can determine all big columns of $D$, in which case, we can determine $M$. % %By~(\ref{small}) and the outcome of the previous argument, we may assume for the rest of the proof that $D$ has either one or two big columns, and each column of $D$ that is not big has exactly $2$ or $3$ ones. Since $M$ is non-paving, $D$ has at least one column with exactly $2$ or $3$ ones. Additionally, we can make assumptions on the location of any zero in a big column using the following, whose proof is similar to that used for~(\ref{3big1}). % %\begin{noname} %Let $e_k$ and $e_l$ be columns of $D$, and suppose that $e_l$ is big. %\begin{enumerate}[{\rm (i)}] %\item Suppose column $e_k$ has exactly two ones and these ones are in rows $h$ and $i$. For $j\not\in \{h, i\}$, column $e_l$ has a zero in row $j$ if and only if %$$(B-\{e_h, e_i, e_j\})\cup \{e_k, e_l\}$$ %is a circuit. % %\item Suppose column $e_k$ has exactly three ones and these ones are in rows $g$, $h$, and $i$. %\begin{enumerate}[{\rm (a)}] %\item For $j\not\in \{g, h, i\}$, column $e_l$ has a zero in row $j$ if and only if %$$(B-\{e_g, e_h, e_i, e_j\})\cup \{e_k, e_l\}$$ %is a circuit. % %\item Column $e_l$ has no zeros if and only if $(B-\{e_g, e_h, e_i\})\cup \{e_k, e_l\}$ is a circuit. %\end{enumerate} %\end{enumerate} %\label{2ones} %\end{noname} % %Now, suppose that $e_k$ has exactly two ones and these ones are in rows $h$ and $i$. By~(\ref{2ones})(i), for $j\not\in \{h, i\}$, a big column $e_l$ has a zero in row $j$ if and only if %\begin{align} %(B-\{e_h, e_i, e_j\})\cup \{e_k, e_l\} %\label{set4} %\end{align} %is a circuit. Since $r(M)\ge 5$ and %$$|(B-\{e_h, e_i, e_j\})\cup \{e_k, e_l\}|\le r-1,$$ %we can decide if set (\ref{set4}) is a circuit. In particular, we can decide if column $e_l$ has a zero in row $j$, in which case, we can determine column $e_l$ and so, by~(\ref{big}), we can determine $M$. Hence we may assume set~(\ref{set4}) is not a circuit for any $j\not\in \{h, i\}$. More particularly, we may assume that the following holds. % %\begin{noname} %If $e_k$ is a column of $D$ with exactly two ones and these ones are in rows $h$ and $i$, and $e_l$ is a big column of $D$, then column $e_l$ either has no zeros or has a zero in one of rows $h$ and $i$. %\label{moreones1} %\end{noname} % %It follows by~(\ref{2ones})(ii)(b) that, when $D$ has a column with exactly three ones, we can ascertain if $D$ has a column with no zeros. When $D$ has a column with no zeros, it follows by~(\ref{big}) that we can determine $M$. Thus, by applying~(\ref{2ones})(ii) instead of~(\ref{2ones})(i), a similar argument to that given for~(\ref{moreones1}) means that we may also make the following assumption. % %\begin{noname} %If $e_k$ is a column of $D$ with exactly three ones and these ones are in rows $g$, $h$, and $i$, and $e_l$ is a big column of $D$, then $e_l$ has a zero in one of rows $g$, $h$, and $i$. %\label{moreones2} %\end{noname} % %The rest of the proof is partitioned into two cases: %\begin{enumerate}[(I)] %\item There is a column $e_k$ of $D$ with exactly three ones; and % %\item all columns of $D$ that are not big have exactly two ones. %\end{enumerate} % %Consider (I). After possible row and column swaps, we may assume that column $e_k$ has ones in rows $r-2$, $r-1$, and $r$. Let $e_l$ be a big column of $D$. Then, by~(\ref{moreones2}), column $e_l$ has a zero in one of rows $r-2$, $r-1$, and $r$. Let $u$ and $u'$ be columns of $D$ that differ from $e_k$ and that each have exactly two ones or exactly three ones. As $M$ is simple, column $u$ does not have ones in each of rows $r-2$, $r-1$, and $r$. Furthermore, column $u$ does not have zeros in each of rows $r-2$, $r-1$, and $r$ otherwise, by~(\ref{moreones1}) and~(\ref{moreones2}), column $e_l$ is not big. If exactly one of rows $r-2$, $r-1$, and $r$ has a one in column $u$, then, by~(\ref{moreones1}) and~(\ref{moreones2}), $e_l$ has a zero in that row and so, by~(\ref{big}), we can determine $M$. Hence column $u$, and similarly column $u'$, has exactly two ones in rows $r-2$, $r-1$, and $r$. If these ones are in different pairs of rows, then, by~(\ref{moreones1}) and~(\ref{moreones2}), column $e_l$, and hence $M$, is determined. Thus, after possible row and column swaps, we may assume the following. % %\begin{noname} %If $u$ is a column of $D$ with exactly two ones or exactly three ones, and $u\neq e_k$, then $u$ has a zero in row $r-2$, and has ones in rows $r-1$ and $r$. %\label{whatones} %\end{noname} % %As $M$ is simple, (\ref{whatones}) implies that $D$ has at most one column with exactly two ones and, in addition to $e_k$, at most $r-2$ columns with exactly three ones. If a column of $D$ with exactly two ones exists, in which case, it has ones in rows $r-1$ and $r$, call it $t$. If, in addition to $e_k$, a column of $D$ with three ones exists, in which case, it has ones in rows $i$, $r-1$, and $r$ for some $i\in \{1, 2, \ldots, r-3\}$, call it $u_i$. Now, in addition to $e_l$, there is at most one other big column of $D$. If it exists, then, like column $e_l$, it has a zero in either row $r-1$ or row $r$. When such a column exists, call it $e_m$. Note that, if $e_m$ exists, then, as $M$ is simple, its zero is in a row different to that of $e_l$. It now follows that $D$ is a submatrix of the following matrix $D'$: %\[\bordersquare{ %& e_k & u_1 & u_2 & \cdots & u_{r-3} & t & e_l & e_m \cr %e_1 & 0 & 1 & 0 & \cdots & 0 & 0 & 1 & 1 \cr %e_2 & 0 & 0 & 1 & \cdots & 0 & 0 & 1 & 1 \cr %e_3 & 0 & 0 & 0 & \cdots & 0 & 0 & 1 & 1 \cr %\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \cr %e_{r-3} & 0 & 0 & 0 & \cdots & 1 & 0 & 1 & 1 \cr %e_{r-2} & 1 & 0 & 0 & \cdots & 0 & 0 & 1 & 1 \cr %e_{r-1} & 1 & 1 & 1 & \cdots & 1 & 1 & \alpha & \beta \cr %e_r & 1 & 1 & 1 & \cdots & 1 & 1 & \beta & \alpha \cr %},\] %where $\{\alpha, \beta\}=\{0, 1\}$. It is easily checked that the vector matroid of $[I_r|D']$ is a binary spike with tip $t$ and legs %$$\{t, e_{r-1}, e_r\}, \{t, e_{r-2}, e_k\}, \{t, e_1, u_1\}, \{t, e_2, u_2\}, \ldots, \{t, e_{r-3}, u_{r-3}\}, \{t, e_l, e_m\}.$$ % %First suppose that $t$ exists. Then $E(M)$ consists of $e_1, e_2, \ldots, e_r, e_k, t, e_l$ and the elements in an $(n-(r+3))$-element subset of $U=\{u_1, u_2, \ldots, u_{r-3}, e_m\}$. Regardless of which $(n-(r+3))$-element subset of $U$ that $E(M)$ contains, $M$ can be obtained from a rank-$r$ binary spike with tip $t$ by deleting $2r+1-n$ elements no two of which belong to the same leg. Thus, by Lemma~\ref{deleting}, $M$ is determined up to isomorphism. If $t$ does not exist, an analogous argument shows that $M$ is also determined up to isomorphism. %Now consider (II). The approach taken is similar to that used in~(I). Let $e_k$ be a column of $D$ with exactly two ones. After possible row and column swaps, we may assume that column $e_k$ has ones in rows $r-1$ and $r$. Let $e_l$ be a big column of $D$. By~(\ref{moreones1}), if column $e_l$ contains a zero, it is in either row $r-1$ or row $r$. By arguing as for~(\ref{whatones}), we may assume, after possible row and column swaps, the following holds. % %\begin{noname} %If $u$ is a column of $D$ with exactly two ones and $u\neq e_k$, then $u$ has a zero in row $r-1$ and a one in row $r$. %\label{lastrow} %\end{noname} % %Since $M$ is simple, it follows by~(\ref{lastrow}) that, in addition to $e_k$, the submatrix $D$ has at most $r-2$ columns with exactly two ones. Furthermore, if there is such a column of $D$, in which case, it has ones in rows $i$ and $r$ for some $i\in \{1, 2, \ldots, r-2\}$, call it $u_i$. Now, in addition to $e_l$, there is at most one other big column of $D$. If it exists, then, by~(\ref{moreones1}), it has ones in rows $1, 2, \ldots, r-1$. When such a column exists, call it $e_m$. As $M$ is simple, if $D$ contains two big columns, then one of these columns has no zeros, and the last entry of the other big column is zero. It follows that $D$ is a submatrix of the following matrix $D'$: %\[\bordersquare{ %& e_k & u_1 & u_2 & \cdots & u_{r-2} & e_l & e_m \cr %e_1 & 0 & 1 & 0 & \cdots & 0 & 1 & 1 \cr %e_2 & 0 & 0 & 1 & \cdots & 0 & 1 & 1 \cr %e_3 & 0 & 0 & 0 & \cdots & 0 & 1 & 1 \cr %\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \cr %e_{r-3} & 0 & 0 & 0 & \cdots & 0 & 1 & 1 \cr %e_{r-2} & 0 & 0 & 0 & \cdots & 1 & 1 & 1 \cr %e_{r-1} & 1 & 0 & 0 & \cdots & 0 & 1 & 1 \cr %e_r & 1 & 1 & 1 & \cdots & 1 & \alpha & \beta \cr %},\] %where $\{\alpha, \beta\}=\{0, 1\}$. It is easily checked that $[I_r|D']$ is a binary spike with tip $e_r$ and legs %$$\{e_r, e_{r-1}, e_k\}, \{e_r, e_1, u_1\}, \{e_r, e_2, u_2\}, \ldots, \{e_r, e_{r-2}, u_{r-2}\}, \{e_r, e_l, e_m\}.$$ % %The ground set of $M$ consists of $e_1, e_2, \ldots, e_r, e_k, e_l$ and the elements in an $(n-(r+2))$-element subset of $U=\{u_1, u_2, \ldots, u_{r-2}, e_m\}$. Regardless of which $(n-(r+2))$-element subset of $U$ that the ground set contains, $M$ can be obtained from a rank-$r$ binary spike with tip $e_r$ by deleting $n-(r+2)$ elements no two of which belong to the same leg. Hence, by Lemma~\ref{deleting}, $M$ is determined up to isomorphism. This completes the analysis of~(II), thereby completing the proof of Theorem~\ref{binary} when $r\ge 5$. %\end{proof} % %\section{When the Rank is Three or Four} %\label{smallrank} % %In this section, we complete the proof of Theorem~\ref{binary}. % %\begin{proof}[Proof of Theorem~\ref{binary} for $r\in \{3, 4\}$] %Since $r\ge 3$, we can decide if an element is a loop or a pair of elements are in parallel. Thus the loops and parallel classes of $M$ are determined. Hence, by deleting all loops as well as all but one element of each parallel class of $M$, we may assume that $M$ is simple. % %If $r=3$, then, as $M$ is simple, $M$ is paving. Since $M$ is isomorphic to neither $U_{3, 4}$ nor $U_{2, 3}\oplus U_{1, 1}$, a straightforward check using Theorem~\ref{paving} shows that, up to isomorphism, the number of elements in $M$ distinguishes $M$. Thus $M$ is determined up to isomorphism, thereby establishing Theorem~\ref{binary} for $r=3$. % %Now suppose that $r=4$. If $M$ is paving, then, as $M$ is isomorphic to neither $U_{4, 5}$ nor $U_{3, 4}\oplus U_{1, 1}$, it follows by Theorem~\ref{paving} that $M$ is isomorphic to $M(K_{3, 2})$, $F_7^*$, or $AG(3, 2)$. Since these matroids have different numbers of elements, $M$ is determined up to isomorphism. % %Assume that $M$ is not paving. Let $C$ be a circuit of $M$ of size at most three and let $f\in C$. Since $M$ is simple, $|C|=3$. By Lemma~\ref{basis}, we can find a basis $B$ of $M$ containing $C-f$. Now consider a binary representation $[I_4|D]$ of $M$ with columns labelled in order $e_1, e_2, \ldots, e_n$, where $n=|E(M)|$. Label the rows of $D$ by $e_1$, $e_2$, $e_3$, and $e_4$. After possible row and column swaps, we may assume that $B=\{e_1, e_2, e_3, e_4\}$ and column $f$ has ones only in rows $e_1$ and $e_2$. Observe that the columns of $D$ that are not determined have either three ones or four ones. As $M$ is simple, there are at most five columns not yet determined. Call a column of $D$ {\em big} if it has either three or four ones. We may assume that $D$ has at least one big column; otherwise $M$ is determined. Specialising the argument that we used to show~(\ref{big}) gives the following. % %\begin{noname} %If a column of $D$ with four ones has been determined, then $M$ is determined. %\label{4ones1} %\end{noname} % %\begin{noname} %If a column of $D$ with exactly three ones has been determined, then it can be determined if there is a column of $D$ with four ones. %\label{4ones2} %\end{noname} % %\begin{noname} %Let $f_{ij}$ be a column of $D$ with zeros in exactly rows $i$ and $j$, where $i\neq j$. Let $g$ be a column of $D$ with exactly three ones. Then $g$ has its unique zero in row $j$ if and only if $\{e_i, f_{ij}, g\}$ is a circuit. %\label{uniquezero} %\end{noname} % %Since $r(M)=4$, we can decide if any $3$-element set is a circuit. In particular, as column $f$ is determined, we can decide if a big column of $D$ has a zero in row $e_3$ or $e_4$. More generally, if amongst the columns of $D$ with exactly two ones, we have at least one zero in each of rows $e_1$, $e_2$, $e_3$, and $e_4$, then, by repeated applications of~(\ref{uniquezero}), we can determine the columns of $D$ with exactly three ones. In turn, as there is at most one column with four ones, it follows that we can determine $M$. % %By~(\ref{uniquezero}) and the previous paragraph, we may now assume that, amongst the columns of $D$ with exactly two ones, one row has no zeros. After possible row and column swaps, we may assume that this row is $e_1$. Let $\gamma$ denote the number of columns of $D$ with exactly two ones and let $\delta$ denote the number of big columns of $D$. Note that $1\le \gamma\le 3$ and $1\le \delta\le 5$. The next assertion follows by the same argument that was used to prove~(\ref{3big1}). % %\begin{noname} %Suppose that $\delta=3$ and no big column of $D$ has a zero in row three or row four. Then it can be determined which big column has no zeros. %\label{delta3} %\end{noname} % %Using (\ref{delta3}) and repeated applications of~(\ref{4ones1}), (\ref{4ones2}), and~(\ref{uniquezero}) it is straightforward to establish the following. % %\begin{noname} %If $\gamma\in \{2, 3\}$, then $M$ is determined unless $\delta\le 2$ and each of the big columns of $D$ either has a unique zero in row $e_1$ or has no zeros. %\label{gamma2} %\end{noname} % %\begin{noname} %If $\gamma=1$, then $M$ is determined unless one of the following holds: %\begin{itemize} %\item[(i)] $\delta\in \{3, 4\}$ and each of the big columns of $D$ has exactly three ones. % %\item[(ii)] $\delta=2$ and one of the big columns of $D$ has a zero either in row $e_1$ or row $e_2$. % %\item[(iii)] $\delta=1$ and the unique big column of $D$ does not have a zero either in row $e_3$ or row $e_4$. %\end{itemize} %\label{gamma1} %\end{noname} % %To complete the proof of Theorem~\ref{binary} when $r=4$, we now identify the situations when $M$ is not uniquely determined. For all $i\in \{1, 2, 3, 4\}$, if a big column of $D$ with a unique zero in row $e_i$ exists, call it $g_i$ and let ${\bf g_i}$ denote the associated column vector. If a big column of $D$ with no zeros exists, call it $h$ and let ${\bf h}$ denote the associated column vector. % %Suppose that $\gamma\in \{2, 3\}$. By~(\ref{gamma2}), we may assume that $D$ has either one or two big columns, and each of these columns either has a unique zero in row $e_1$ or has no zeros. Since $\gamma\ge 2$, there exists a column, $f'$ say, of $D$ in addition to $f$ with exactly two ones. Furthermore, if $\gamma=3$, there exists an additional column, $f''$ say, distinct from $f$ and $f'$ with exactly two ones. After possible row and column swaps, we may assume that $f'$ has ones in rows $e_1$ and $e_3$ and, if it exists, $f''$ has ones in rows $e_1$ and $e_4$. % %Let $D'$ denote the submatrix of $D$ consisting of columns with exactly two ones. First assume that $\gamma=3$. It is easily checked that if $g_1$ and $h$ exist, then $M$ is a binary spike with tip $e_1$. Furthermore, the vector matroids of $[I_4|D'|{\bf g_1}]$ and $[I_4|D'|\bf h]$ are isomorphic to a rank-$4$ binary spike with tip $e_1$ and with cotip $g_1$ and $h$, respectively. Thus, by Lemma~\ref{deleting}, $M$ is determined up to isomorphism. A similar argument holds if $\gamma=2$. % %Now suppose that $\gamma=1$. First assume that $\delta\in \{3, 4\}$. Then, by~(\ref{gamma1}), we may assume that $h$ does not exist. If $\delta=4$, then $M$ is a binary spike with tip $f$ and no cotip. Also, as each of the vector matroids of $[I_4|D'|{\bf g_2}|{\bf g_3}|{\bf g_4}]$, $[I_4|D'|{\bf g_1}|{\bf g_3}|{\bf g_4}]$, $[I_4|D'|{\bf g_1}|{\bf g_2}|{\bf g_4}]$, and $[I_4|D'|{\bf g_1}|{\bf g_2}|{\bf g_3}]$ is isomorphic to a rank-$4$ binary spike with tip $f$ and a cotip, it follows by Lemma~\ref{deleting} that $M$ is determined up to isomorphism when $\delta=3$. % %Next assume that $\delta=2$. Then, by~(\ref{gamma1}), either $g_1$ or $g_2$ exists and $M$ can be obtained from a rank-$4$ binary spike with tip $f$, $e_1$, or $e_2$ by deleting two elements not belonging to the same leg. Thus, by Lemma~\ref{deleting}, $M$ is determined up to isomorphism. % %Lastly, assume that $\delta=1$. Then, by~(\ref{gamma1}), exactly one of $g_1$, $g_2$ and $h$ exists and $M$ can be obtained from a rank-$4$ binary spike with tip $f$ by deleting three elements no two of which belong to the same leg. Again, by Lemma~\ref{deleting}, $M$ is determined up to isomorphism. This completes the proof of Theorem~\ref{binary} for $r=4$. %\end{proof} \begin{thebibliography}{99} \bibitem{ack88} D.~M.\ Acketa. \newblock On binary paving matroids. \newblock {\em Discrete Math.}, 70:109--110, 1988. \bibitem{bix74} R.~E.\ Bixby. \newblock $l$-matrices and a characterization of non-binary matroids. \newblock {\em Discrete Math.}, 8:139--145, 1974. \bibitem{cou86} C.~R.\ Coullard. \newblock Counterexamples to conjectures on $4$-connected matroids. \newblock {\em Combinatorica}, 6:315--320, 1986. \bibitem{kahn85} J.\ Kahn. \newblock A problem of P.\ Seymour on non-binary matroids. \newblock {\em Combinatorica}, 5:319--323, 1985. \bibitem{ox87} J.~G.\ Oxley. \newblock The binary matroids with no $4$-wheel minor. \newblock {\em Trans.\ Amer.\ Math.\ Soc.}, 301:63--75, 1987. \bibitem{ox11} J.\ Oxley. \newblock {\em Matroid Theory, Second edition}. \newblock Oxford Univ.\ Press, New York, 2011. \bibitem{sey81} P.~D.\ Seymour. \newblock On minors of non-binary matroids. {\em Combinatorica}, 1:387--394, 1981. \end{thebibliography} \end{document}