%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2021}
\articlenumber{75}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

%\newtheorem{thm}{Theorem}
%\newtheorem{lem}{Lemma}

\usepackage{lipsum}

%\usepackage{hyperref}
%\usepackage[sort&compress,capitalise]{cleveref}

%% Enter additionally required packages below this comment.
%% * Please be conservative and only require common packages.
%% * Do not use any packages, which alter the page/font layout.
%% * For the inclusion of graphics, use the graphicx package.
%% * Please use .eps graphics only (no .jpg, .png or .pdf).
%% Note that the tex source has to be compilable to .dvi format.

\usepackage{graphicx}
\usepackage{subcaption}
%\usepackage{enumerate}
\usepackage{enumitem}
\usepackage{mathtools}
\usepackage{float}
\usepackage{arydshln}
\usepackage{wrapfig}
\usepackage{blkarray, bigstrut}

\newtheorem{theorem}{Theorem}
\newtheorem{rmrk}[theorem]{Remark}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{exmp}[theorem]{Example}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lemm}[theorem]{Lemma}


\newcommand\A{\mathcal{A}}
\newcommand\B{\mathcal{B}}
\newcommand\C{\mathbb{C}}
\newcommand\F{\mathbb{F}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\cP}{\mathcal{P}}

\DeclareMathOperator{\codim}{codim}

%% define your title in the usual way
\title{The Universality of the Resonance Arrangement and its Betti Numbers}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Lukas K\"uhne\thanks{\href{mailto:lukas.kuhne@mis.mpg.de}{lukas.kuhne@mis.mpg.de}. Lukas K\"uhne was partially supported by ERC StG 716424 - CASe, a Minerva fellowship of the Max-Planck-Society and the Studienstiftung des deutschen Volkes.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Max Planck Institute for Mathematics in the Sciences, Inselstr. 22, 04103, Leipzig, Germany}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
\revised{\today}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
	The resonance arrangement $\A_n$ is the arrangement of hyperplanes which has all non-zero $0/1$-vectors in $\R^n$ as normal vectors.
	It is the adjoint of the Braid arrangement and is also called the all-subsets arrangement.
	The first result of this article shows that any rational hyperplane arrangement is the minor of some large enough resonance arrangement.
	
	Its chambers appear as regions of polynomiality in algebraic geometry, as generalized retarded functions in mathematical physics and as maximal unbalanced families that have applications in economics.
	One way to compute the number of chambers of any real arrangement is through the coefficients of its characteristic polynomial which are called Betti numbers.
	We show that the Betti numbers of the resonance arrangement are determined by a fixed combination of Stirling numbers of the second kind.
	Lastly, we develop exact formulas for the first two non-trivial Betti numbers of the resonance arrangement.
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{matroids, resonance arrangement, all-subsets arrangement, maximal unbalanced families, Betti numbers}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{75Kuehne.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above




\section{Introduction}

\subsection{The Resonance Arrangement}
The main object considered in this article is the resonance arrangement:
\begin{defn}
	For a fixed integer $n\ge1$ we define the hyperplane arrangement $\A_n$ as the \emph{resonance arrangement} in $\R^n$ by setting
	$
	\A_n:=\{H_I\mid \emptyset \neq I\subseteq [n]\},
	$
	where the hyperplanes~$H_I$ are defined by
	$
	H_I := \left\{ \sum_{i\in I}x_i = 0 \right\}.
	$
\end{defn}

\begin{figure}[h]
	\begin{center}
	\includegraphics[width=.3\linewidth]{A3.pdf}
	\caption{The resonance arrangement $\A_3$ projected onto the hyperplane $H_{\{1,2,3\}}$.
		There are $16$ chambers visible and another $16$ antipodal chambers hidden. Thus, $\A_3$ has $32$ chambers in total.}
	\label{fig:A3}
		\end{center}
\end{figure}

The term resonance arrangement was coined by Shadrin, Shapiro, and Vainshtein in their study of double Hurwitz numbers stemming from algebraic geometry~\cite{SSV08}.
Billera, Billey, Rhoades, and Tewari proved that the product of the defining linear equations of~$\A_n$ is Schur positive via a so-called Chern phletysm from representation theory~\cite{BBT18,BRT19}.
Recently, Gutekunst, M{\'e}sz{\'a}ros, and Petersen established a connection between the resonance arrangement and the type $A$ root polytope~\cite{GMP19}.

The arrangement $\A_n$ is also the \emph{adjoint of the braid arrangement}~\cite[Section 6.3.12]{AM17}.
It was studied under this name by Liu, Norledge, and Ocneanu in its relation to mathematical physics~\cite{LNO19}.
The relevance of the resonance arrangement in physics was also demonstrated by Early in his work on so-called \emph{plates}, cf.~\cite{Ear17}.

In earlier work, the arrangement $\A_n$ was called \emph{(restricted) all-subsets arrangement} by Kamiya, Takemura, and Terao who established its relevance for applications in psychometrics and economics~\cite{KTT11,KTT12}.

A first contribution of this article is a universality result of the resonance arrangement for rational hyperplane arrangements:

\begin{theorem}\label{thm:universality}
	Let $\B$ be any hyperplane arrangement defined over $\Q$.
	Then $\B$ is a minor of $\A_n$ for some large enough $n$, that is $\B$ arises from $\A_n$ after a suitable sequence of restriction and contraction steps.
	Equivalently, any matroid that is representable over $\Q$ is a minor of the matroid underlying $\A_n$ for some large enough $n$.
\end{theorem}

The proof is constructive and the size of the required $\A_n$ depends on the size of the entries in an integral representation of $\B$.

\subsection{Chambers of $\A_n$}

The \emph{chambers of $\A_n$} are the connected components of the complement of the hyperplanes in $\A_n$ within $\R^n$.
We denote by $R_n$ the number of chambers of the arrangement $\A_n$.
The arrangement $\A_3$ for instance has $32$ chambers as shown in~\Cref{fig:A3}.


These chambers appear in various contexts, such as quantum field theory where these regions correspond to generalized retarded functions~\cite{Eva95}.
Cavalieri, Johnson, and Markwig proved that the chambers of $\A_n$ are the domains of polynomiality of the double Hurwitz number~\cite{CJM11}.
Subsequently, Gendron and Tahar demonstrated the significance of the chambers of the resonance arrangement in geometric topology~\cite{GT20}.

Billera, Tatch Moore, Dufort Moraites, Wang, and Williams observed that the chambers of $\A_n$ are also in bijection with \emph{maximal unbalanced families} of order $n+1$.
These are systems of subsets of $[n+1] $ that are maximal under inclusion such that no convex combination of their characteristic functions is constant~\cite{BTDWW12}.
Equivalently, the convex hull of their characteristic functions viewed in the $n+1$-dimensional hypercube does not meet the main diagonal.
Such families were independently studied by Bj\"orner as \emph{positive sum systems}~\cite{Bjo15}.


The values of $R_n$ are only known for $n\le 8$, see for instance~\cite[\href{https://oeis.org/A034997}{A034997}]{OEIS}.
There is no exact formula known for $R_n$.
The work of Odlyzko and Zuev~\cite{Odl88,Zue92} together with the recent one by Gutekunst, M{\'e}sz{\'a}ros, and Petersen~\cite{GMP19} gives the bounds
\begin{equation}\label{eq_rn}
n^2 -10n^2/\ln(n)-n+\log_2(n+1)<\log_2(R_n) < n^2-1,
\end{equation}
which in turn yields the asymptotic behavior $\log_2 (R_n) \sim n^2$.
Deza, Pournin, and Rakotonarivo obtained the improved upper bound of $\log_2(R_n) < n^2-3n+2+\log_2(2n+8)$~\cite{DPR21}.

Due to a theorem of Zaslavsky the number of chambers of any arrangement over $\R$ equals the sum of all Betti numbers of the arrangement~\cite{Zas75}.
The Betti numbers can be defined via the characteristic polynomial of an arrangement:

\begin{defn}
	For any arrangement of hyperplanes $\A$ in $\F^n$ for any field $\F$ its \emph{characteristic polynomial}~$\chi(\A;t)$ is defined to be
	\[
	\chi(\A;t) := \sum_{S\subseteq \A} (-1)^{|S|}t^{r(\A)-r(S)},
	\]
	where for any subset $S\subseteq \A$ we set $r(S):=\codim \cap_{H\in S} H$.
	The absolute value of the coefficient of $t^{n-i}$ in the characteristic polynomial $\chi(\A;t)$ is called $i$-th \emph{Betti number}.
	One always has $b_0(\A)=1$ and $b_1(\A)=|\A|$.
\end{defn}

In the case of a complex arrangement of hyperplanes, the Betti numbers coincide with the topological Betti numbers of the complement of the arrangement $\C^n \setminus (\cup_{H\in\A}H)$ with coefficients in $\Q$, cf.~\cite[Chapter 5]{OT92} for an overview of the topological study of arrangement complements.


A formula for $\chi(\A_n;t)$ would also yield a formula for $R_n$.
Unfortunately, there is also no such formula known for $\chi(\A_n;t)$.
In fact, the polynomial $\chi(\A_n;t)$ itself is only known for $n\le 7$ as computed in~\cite{KTT11}.

The next result of this article proves that the Betti numbers $b_i(\A_n)$ for any fixed $i>0$ can be computed for all $n>0$ from a fixed finite combination of \emph{Stirling numbers of the second kind} $S(n,k)$ which count the number of partitions of $n$ labeled objects into $k$ non-empty blocks.
The proof is based on Brylawski's broken  circuit complex~\cite{Bry77}.

\begin{theorem}\label{thm:betti_stirling}
	There exist some positive integers $c_{i,k}$ for all $i\ge 0$ and $i+1\le k \le 2^i$ such that for all $n\ge 1$,
	\[
	b_i(\A_n) = \sum_{k=1}^{2^i} c_{i,k} S(n+1,k).
	\]
	Moreover, the constants $c_{i,k}$ are bounded by $c_{i,k} \leq  \binom{2^i-1}{k-1} \frac{(k-1)!}{i!}$.
\end{theorem}
The first two trivial cases of this theorem are 
\[
b_0(A_n) = S(n+1,1), \quad b_1(\A_n) = S(n+1,2).
\]
One can obtain exact formulas for the higher Betti numbers $b_i(\A_n)$ from \Cref{thm:betti_stirling} if one knows $b_i(\A_n)$ for all $1\le n \le 2^i$ since the matrix of Stirling numbers $(S(n,k))_{n,k=1,\dots, 2^i}$ is invertible.
Unfortunately, this already fails for $b_3(\A_n)$ since $\chi(\A_n;t)$ is only known for $n\le 7$.

Analyzing the triangles in the broken circuit in detail we obtain exact formulas for the first two non-trivial coefficients of $\chi(\A_n,t)$, namely $b_2(\A_n)$ and $b_3(\A_n)$,  in terms of Stirling numbers of the second kind.
That is, we determine the exact constants $c_{2,k}$ and $c_{3,k}$ for all relevant $k$.

\begin{theorem}\label{thm:betti}
	For any $n\ge 1$ it holds that
	\begin{align*}
	(i)\quad b_2(\A_n) = &  2S(n+1,3) + 3S(n+1,4), \\
	=&\frac{1}{2} (4^n - 3^n - 2^n + 1) \mbox{ and}	\\
	(ii) \quad b_3(\A_n) =  & 9S(n+1,4)+80S(n+1,5) + 345 S(n+1,6) \\
	&+ 840 S(n+1,7) +840S(n+1,8) ,\\
	=&\frac{1}{4!} (4\cdot8^n -15\cdot 6^n +15\cdot 5^n - 14 \cdot 4^n + 18 \cdot 3^n - 7\cdot 2^n-1).
	\end{align*}
\end{theorem}

\begin{exmp}
	Using~\Cref{thm:betti} we can compute $\chi(\A_3;t)$ as
	\[
	\chi(\A_3;t) = t^3 - 7t^2 + 15t-9.
	\]
	Thus, the above mentioned result by Zaslavsky again yields $R_3=1+7+15+9=32$.
\end{exmp}

\begin{rmrk}
	The formula for $b_2(\A_n)$ in~\Cref{thm:betti} $(i)$ was also found earlier by Billera (personal communication).
\end{rmrk}

This article is an extended abstract of the full article~\cite{Kue20} and it is organized as follows.
After reviewing necessary definitions of matroids and their minors in~\Cref{sec:matroids} we will prove~\Cref{thm:universality} in~\Cref{sec:universality}.
Subsequently, we state the necessary facts on broken circuit complexes in~\Cref{sec:bc} and prove~\Cref{thm:betti_stirling} in~\Cref{sec:stirling}.
For the proof of~\Cref{thm:betti} we refer to the full article~\cite{Kue20}.

\acknowledgments{
I would like to thank Karim Adiprasito for his mentorship and for introducing me to the topic of resonance arrangements.
Furthermore, I am grateful to Louis J. Billera, Michael Joswig, and Jos\'e Alejandro Samper for helpful conversations and feedback on earlier version of this manuscript.
Moreover, I am indebted to the graphics department of the Max Planck Institute for Mathematics in the Sciences for helping me to create \Cref{fig:A3}.
Lastly, I would like to thank the anonymous referees for their valuable suggestions to improve the article.}

\section{Matroids and their Minors}\label{sec:matroids}

In this section we review some basics of matroids and their minors.
Details can be found in~\cite{Oxl11}.

\begin{defn}
	A \emph{matroid} $M$ is a pair $(E,\I)$ where $E$ is a finite \emph{ground set} and $\I$ is a non-empty family of subsets of $E$, called \emph{independent sets} such that
	\begin{enumerate}[label=(\roman*)]
		\item for all $A'\subseteq A \subseteq E$ if $A\in \I$ then $A'\in\I$ and
		\item if $A,B\in \I$ with $  |A|>|B|$ then there exists $a\in A\setminus B$ such that $B\cup\{a\}\in \I$.
	\end{enumerate}	
\end{defn}

Given some set finite set $E$ and an $r\times E$-matrix $A$ with entries in some field $\F$ we obtain a matroid $M(A)$ on the ground set $E$ whose independent sets are the columns of~$A$ that are linear independent.
A matroid $M$ is called \emph{representable} over a field $\F$ if there exists an $r\times E$-matrix $A$ such that $M=M(A)$.

An arrangement of hyperplanes $\A$ also gives rise to a matroid by writing the coefficients of a linear equation for each $H\in\A$ as columns in a matrix and applying the above construction.
Similarly, we also get a matroid $M(\A)$ underlying an arrangement $\A$ with ground set $\A$ whose independent set are precisely those whose hyperplanes intersect with codimension equal to the cardinality of the subset.

\begin{defn}
	Let $M=(E,\I)$ be a matroid and $S\subseteq E$. Then one defines:
	\begin{enumerate}
		\item The \emph{restriction} of $M$ to $S$, denoted $M|S$, is the matroid on the ground set $S$ with independent sets $\{ I\in \I\mid I\subseteq S\}$.
		\item Assume that $S$ is independent in $M$.
		Then, the \emph{contraction} of $M$ by $S$, denoted $M/S$, is the matroid on the ground set $E\setminus S$ with independent sets $\{ I \subseteq E\setminus S\mid I\cup S\in \I \}$.
	\end{enumerate}
	A matroid $N$ is called a \emph{minor} of $M$ if $N$ arises from $M$ after a finite sequence of restrictions and contractions.
\end{defn}

Minors play a central role in the theory of matroids.
For instance, Geelen, Gerards and Whittle announced a proof of Rota's conjecture which asserts that matroid representability over a finite field can be characterized by a finite list of excluded minors~\cite{GGW14}.

The restriction of a representable matroid to some subset $S$ is again representable by the same matrix after removing the columns that are not in $S$.
The following lemma establishes a similar connection for contractions of representable matroids.
This also motivates the term minor of a matroid as it corresponds to a minor of a matrix in the representable case.

\begin{lemm}[{\cite[Proposition~3.2.6]{Oxl11}}]\label{lem:oxley}
	Let $E$ be some finite set and $A$ an $r\times E$ matrix over a field $\F$.
	Suppose $e\in E$ is the label of a non-zero column of $A$.
	Let $A'$ be the matrix arising from $A$ through row operations by pivoting on some non-zero element in the column $e$.
	Let $A'/e$ be the matrix $A'$ where one removes the row and column containing the unique non-zero entry in the column $e$.
	Then,
	\[
	M(A)/e =M(A')/e=  M(A'/e).
	\]
\end{lemm}


\section{Universality of the Resonance Arrangement}\label{sec:universality}

Let $M$ be a matroid of rank $r$ and size $n$ that is representable over $\Q$.
Thus after scaling, we can assume that there is a $r\times n$ matrix $A$ with entries in $\Z$ that represents $M$.
Let $a_1,\dots,a_n\in \Z^r$ be the column vectors of the matrix $A$.
The vectors $a_i$ can be expressed as a sum of positive and negative characteristic vectors.
Given that such a representation is usually not unique, we fix one choice of $m_i^+,m_i^-\in \N$ and $P_j^i,N_k^i\subseteq [r]$ for all $1\le j \le m_i^+$ and $1\le k \le m_i^-$ such that 
\begin{equation}\label{eq:ai}
a_i = \sum_{j=1}^{m_i^+} \chi_{P_j^{i}}  - \sum_{k=1}^{m_i^-} \chi_{N_k^{i}}.
\end{equation}


We work in the extended vector space
\[
\Q^N \coloneqq \Q^r \times \Q^{m_1^-}\times \Q^{m_1^+}\times \Q^{m_1^{+}} \times \dots \times \Q^{m_n^-}\times \Q^{m_n^+}\times \Q^{m_n^{+}} ,
\]
for some appropriate $N\in\N$.
Hence, the vectors $a_1,\dots,a_n$ naturally live in the first factor~$\Q^r$ of $\Q^N$.
We fix the standard basis of $\Q^N$ as
\[
e_1,\dots,e_r,e_1^{1,-},\dots,e_{m_1^-}^{1,-},e_1^{1,+},\dots,e_{m_1^+}^{1,+},e_1^{1,++},\dots,e_{m_1^+}^{1,++},\dots.
\]

Now, we describe a construction which will be used in the proof in~\Cref{thm:universality}.
To this end, we define $0/1$-vectors $v_1,\dots,v_n$ which will eventually represent the matroid $M$ after contracting several other $0/1$-vectors.
We define for each $1\le i \le n$:
\begin{align*}
v_i \coloneqq & \sum_{j=1}^{m_i^+} e_j^{i,++}+  \sum_{k=1}^{m_i^-} e_k^{i,-}, \\
r_k^{i,-} \coloneqq & \chi_{N_k^{i}} + e_k^{i,-} \mbox{ for }1\le k \le m_i^-, \\
r_j^{i,+} \coloneqq & \chi_{P_j^{i}} + e_j^{i,+} \mbox{ for }1\le j \le m_i^+,\\
r_j^{i,++} \coloneqq & e_j^{i,+}  + e_j^{i,++}\mbox{ for }1\le j \le m_i^+. 
\end{align*}

We collect these vectors in the sets $V\coloneqq \{ v_1,\dots,v_n\}$ and
\[
R\coloneqq \{ r_k^{i,-}, r_j^{i,+} ,r_j^{i,++} \mid 1\le i \le n, 1\le k \le m_i^- \mbox{ and }1\le j \le m_i^+ \}.
\]

Before presenting the proof of~\Cref{thm:universality}, we give an example of this construction.

\begin{exmp}
	Consider the vectors $a_1\coloneqq (1,-2,-1)^T$ and $a_2\coloneqq (-1,0,-1)^T$ in $\Z^3$.
	They can be expressed as $a_1   = \chi_{\{1\}} - \chi_{\{2,3\}} - \chi_{\{2\}}$ and $a_2  = - \chi_{\{ 1,3 \}}$.
	
	Thus, $m_1^{-}=2, m_1^{+}=1,m_2^{-}=1$, and $m_2^{+}=0$.
	The above construction yields the following column vectors in $\Q^8$ depicted in the left matrix below.
	The matrix on the right arises from the one on the left after suitable row operations as described below in the proof of~\Cref{thm:universality}.
	\begin{equation}\label{eq:example}
	\begin{array}{r}
	v_1\quad r_1^{1,-}\ r_2^{1,-}\ r_1^{1,+}\, r_1^{1,++}\! v_2\ \quad r_1^{2,-} \\
	\left[\setlength{\arraycolsep}{8pt}\def\arraystretch{1.2}
	\begin{array}{>{\columncolor{gray!20}}c c >{\columncolor{gray!20}}cc>{\columncolor{gray!20}}cc>{\columncolor{gray!20}}c}
	\rowcolor{gray!20}
	0 &  0 & 0 & 1 & 0 & 0 & 1 \\ 
	0 &  1 & 1 & 0 & 0 & 0 & 0 \\ \rowcolor{gray!20}
	0 &  1 & 0 & 0 & 0 & 0 & 1 \\ 
	1 &  1 & 0 & 0 & 0 & 0 & 0 \\ \rowcolor{gray!20}
	1 &  0 & 1 & 0 & 0 & 0 & 0 \\ 
	0 &  0 & 0 & 1 & 1 & 0 & 0 \\ \rowcolor{gray!20}
	1 &  0 & 0 & 0 & 1 & 0 & 0 \\ 
	0 &  0 & 0 & 0 & 0 & 1 & 1 
	\end{array}
	\right]
	\end{array}
	\leadsto
	\begin{array}{r}
	\phantom{r_1^{1,+}}\\
	\left[\setlength{\arraycolsep}{8pt}\def\arraystretch{1.2}
	\begin{array}{>{\columncolor{gray!20}}c c >{\columncolor{gray!20}}cc>{\columncolor{gray!20}}cc>{\columncolor{gray!20}}c}
	\rowcolor{gray!20}
	1 &  0 & 0 & 0 & 0 & -1 & 0 \\ 
	-2 &  0 & 0 & 0 & 0 & 0 & 0 \\ \rowcolor{gray!20}
	-1 &  0 & 0 & 0 & 0 & -1 & 0 \\ 
	1 &  1 & 0 & 0 & 0 & 0 & 0 \\ \rowcolor{gray!20}
	1 &  0 & 1 & 0 & 0 & 0 & 0 \\ 
	-1 &  0 & 0 & 1 & 0 & 0 & 0 \\ \rowcolor{gray!20}
	1 &  0 & 0 & 0 & 1 & 0 & 0 \\ 
	0 &  0 & 0 & 0 & 0 & 1 & 1 
	\end{array}
	\right]
	\end{array}.
	\end{equation}
	All columns apart from $v_1,v_2$ became standard basis vectors and removing those columns together with all rows apart from the first three yields the matrix with columns $a_1,a_2$.
\end{exmp}



\begin{proof}[Proof of~\Cref{thm:universality}]
	First, we assemble the vectors in $R$ and $V$ to a matrix as in the matrix on the left hand side of~\Cref{eq:example}.

	Now, we perform row operations on this matrix to ensure that all columns corresponding to vectors in $R$ are standard basis vectors.
	To this end, we apply the following steps for all $1\le i \le n$:
	\begin{enumerate}
		\item We pivot on the entry in row $e_k^{i,-}$ and column $r_k^{i,-}$ for each $1\le k \le m_i^{-}$.
		\item Lastly, we pivot on the entry in row $e_j^{i,s}$ and column $r_j^{i,s}$ for each $1\le j \le m_i^{+}$ and each $s\in \{+,++\}$.
	\end{enumerate}
	By construction and~\Cref{eq:ai}, this procedure yields a matrix as on the right hand side of~\Cref{eq:example}.

	
	Therefore, we obtain the matrix $A$ by removing all columns corresponding to vectors in $R$ and all rows apart from the first $r$ ones.
	Hence, \Cref{lem:oxley} implies that the matroid $M$ equals the matroid of the resonance arrangement $\A_N$ restricted to $V\cup R$ and contracted by $R$, that is $M$ is a minor of the matroid of $\A_N$.
\end{proof}



\section{The Broken Circuit Complex}\label{sec:bc}

A tool to compute the Betti numbers of an arrangement is the broken circuit complex:
\begin{defn}\label{def:broken_circuits}
	Let $\A$ be any arrangement and fix any linear order $<$ on its hyperplanes.
	A \emph{circuit} of $\A$ is a minimally dependent subset.
	A \emph{broken circuit} of $\A$ is a set $C\setminus \{H\}$ where $C$ is a circuit and $H$ is its largest element (in the ordering $<$).
	The \emph{broken circuit complex} $BC(\A)$ is defined by
	\[
	BC(\A)\coloneqq \{ T \subset \A \mid T \mbox{ contains no broken circuit}\}.
	\]
\end{defn}

Its significance lies in the following result:
\begin{theorem}[{\cite{Bry77}}]\label{thm:betti_bc}
	Let $\A$ be any arrangement in a vector space $\F^n$ for some field $\F$ with a fixed linear order~$<$ on its hyperplanes.
	Then for any $1\le i \le n$ it holds that
	\[
	b_{i}(\A) = f_{i-1}(BC(\A)),
	\]
	where $f_i$ is the $f$-vector of the broken circuit complex.
\end{theorem}

For the rest of the article we will study the broken circuit complex of the resonance arrangement $\A_n$.
Each subset of  $I \subseteq \left[ n \right]$ can be encoded as a binary number $\sum_{i \in I} 2^i$.
This gives rise to a natural ordering of the hyperplanes in $\A_n$ which we will use as to obtain its broken circuit complex.
In the subsequent proofs we will identify a hyperplane $H_A$ with its defining subset $A$ or its corresponding characteristic vector $\chi_A$ if no confusion arises.

\section{Proof of~\Cref{thm:betti_stirling}}\label{sec:stirling}

Throughout this section we use the following notation:
Taking all possible intersections of the sets in an $i$-tuple $(A_1,\dots,A_i)$ of pairwise different non-empty subsets of $[n]$ yields a partition $\pi=\{P_1,\dots,P_k\}$ of $[n+1]$ into $k$ blocks with $i+1\le k\le 2^i$ (the block containing $n+1$ exactly contains all elements of $[n]$ which are not contained in any of the sets $A_j$ for $1\le j \le i$).
In other words, the partition $\pi$ is the common refinement of the two-block partitions $(A_1,[n+1]\setminus A_1),\dots,(A_i,[n+1]\setminus A_i)$.
We order the blocks in the partition $\pi$ by their binary representation as detailed above; in particular we have $n+1\in P_k$.

Moreover, the tuple $(A_1,\dots,A_i)$ together with the partition $\pi$ defined above determines a map 
\begin{align*}
f:[k-1]&\rightarrow \cP([i])\setminus\{\emptyset\},\\
\ell &\mapsto \{ j\in [i]\mid P_\ell \subseteq A_j \},
\end{align*}
Note that this map is injective since the sets in the tuple  $(A_1,\dots,A_i)$ are assumed to be pairwise different.
Furthermore, there exists for every $j\in [i]$ some $\ell \in [k-1]$ such that $j\in f(\ell)$ since $A_j$ is assumed to be non-empty.
We call a map satisfying this last property \emph{weakly surjective}.
Moreover, we call a map $f:[k-1]\rightarrow \cP([i])\setminus\{\emptyset\}$ that is injective and weakly surjective an $(i,k)$-\emph{prototype}.

Conversely, given any partition $\pi=\{P_1,\dots,P_k\}$ of $[n+1]$ and a $(i,k)$-prototype $f$ we obtain an $i$-tuple $(A_1,\dots,A_i)$ which we denote by $A_{f,\pi}$ by setting for $1\le j \le i$
\[
A_j \coloneqq  \bigcup_{\ell \in I^f_j }P_{\ell},
\]
where we define $I^f_j \coloneqq \{\ell \in [k-1]  \mid j\in f(\ell) \}$ for $1\le j \le i$.
Since $f$ is weakly surjective by definition of an $(i,k)$-prototype these sets $A_j$ are non-empty for all $1\le j \le i$.
We call these sets the \emph{building blocks} of $f$.

In total, this construction gives a bijection between $i$-tuples of pairwise different non-empty subsets of $[n]$ and pairs of $(i,k)$-prototypes together with partitions of $[n+1]$ into $k$ blocks with $i+1\le k \le 2^i$.

Now the main observation is the following.
Whether an $i$-tuple $A_{f,\pi}$ is a broken circuit depends only on the prototype $f$ but not on the partition $\pi$:

\begin{prop}\label{prop:prototypes}
	In the above notation, let $f:[k-1]\rightarrow \cP([i])\setminus\{\emptyset\}$ be an $(i,k)$-prototype.
	Assume there exists a partition $\pi=\{P_1,\dots,P_k\}$ of $[n+1]$ such that the $i$-tuple $A_{f,\pi}=(A_1,\dots,A_i)$ is a broken circuit of $\A_n$ (in the order induced by the binary representation).
	
	Let $\widetilde{\pi}=\{\widetilde{P_1},\dots,\widetilde{P_k}\}$ be any partition of $[\widetilde{n}+1]$ for some $\widetilde{n}\ge 1$ into $k$ non-empty parts.
	Then the $i$-tuple $A_{f,\widetilde{\pi}}=(\widetilde{A_1},\dots,\widetilde{A_i})$ is also a broken circuit of $\A_{\widetilde{n}}$.
\end{prop}
\begin{proof}
	By assumption, the tuple $A_{f,\pi} = (A_1,\dots,A_i)$ is a broken circuit.
	Thus, there exists some $C \subseteq [n]$ and $\lambda_1,\dots,\lambda_i\in \R^*$ such that
	\begin{equation}\label{eq:bc}
	\sum_{j=1}^i \lambda_j\chi_{A_j} = \chi_{C},
	\end{equation}
	and $A_j < C$ for all $1\le j \le i$.
	
	This implies that $C$ is also a union of the first $k-1$ parts of the partition $\pi$, that is there exists some $I_C\subseteq [k-1]$ such that $C=\bigcup_{\ell \in I_C}P_\ell$.
	Hence, we can rewrite~\Cref{eq:bc} as
	\begin{equation}\label{eq:bc2}
	\sum_{j=1}^i \lambda_j\sum_{\ell \in I_j^f} P_\ell  = \sum_{\ell \in I_C} P_\ell,
	\end{equation}
	Subsequently, the fact $A_j < C$  yields $I_j^f < I_C$ for all $1\le j \le i$ where $I_j^f$ are the building blocks of the prototype $f$ and the order is the one induced by the binary representation of subsets of $[k-1]$.
	
	Now consider the partition $\widetilde{\pi}$ of $[\widetilde{n}+1]$.
	Using the building block $I_C$ of $C$ we can define a corresponding subset of $[\widetilde{n}]$ by setting $\widetilde{C}\coloneqq \bigcup_{\ell \in I_C} \widetilde{P_\ell}$.
	Thus,~\Cref{eq:bc2} implies
	\[
	\sum_{j=1}^i \lambda_j\sum_{\ell \in I_j^f} \widetilde{P_\ell}  = \sum_{\ell \in I_C} \widetilde{P_\ell}.
	\]
	Therefore, the tuple $(\widetilde{A_1},\dots,\widetilde{A_i},\widetilde{C})$ is a circuit of $\A_{\widetilde{n}}$.
	Using the fact $I_j^f < I_C$ we obtain again $\widetilde{A_j}<\widetilde{C}$ for all $1\le j \le i$ which completes the proof that $A_{f,\widetilde{\pi}}$ is a broken circuit in~$\A_{\widetilde{n}}$.
\end{proof}

In light of~\Cref{prop:prototypes} we can subdivide prototypes into two sets.
We call those which contain a broken circuit for some partition, and thus for all partitions, \emph{broken} prototypes.
Otherwise, we call a prototype \emph{functional}.

\begin{proof}[Proof of~\Cref{thm:betti_stirling}]
	As explained above, any $i$-tuple of subsets of $[n]$ can be obtained from an $(i,k)$-prototype and a partition $\pi$ of $[n+1]$ into $k$ blocks with $i+1\le k \le 2^i$.
	\Cref{thm:betti_bc} then implies that we can compute the Betti number $b_i(\A_n)$ for any $i\ge 0$ through functional prototypes and partitions.
	We correct the fact that the latter yields ordered tuples unlike the elements  in the broken circuit complex by multiplying the Betti numbers  $b_i(\A_n)$ by $i!$ in the following computation:
	\begin{align*}
	b_i(\A_n) i!=& |\{ X=(A_1,\dots,A_i)\mid A_j\in \cP([n])\setminus\{\emptyset\} , A_j\neq A_{j'} \mbox{ for all }j\neq j'\mbox{ and}\\
	&\; \mbox{ $X$ does not contain a broken circuit}  \}|\\ 
	=& \sum_{k=i+1}^{2^i} |\{A_{f,\pi}\mid f \mbox{ functional $(i,k)$-prototype and}\\
	& \qquad\quad \pi \mbox{ partition of $[n+1]$ into $k$ blocks}\}|\\
	=& \sum_{k=i+1}^{2^i} |\{\mbox{functional $(i,k)$-prototypes}\}|S(n+1,k).
	\end{align*}
	This already proves that for each $i\ge 0$ the Betti number $b_i(\A_n)$ can be computed by a combination of Stirling numbers which is independent from $n$. This settles the first claim of the theorem.
	
	For the second claim, note that the above argument shows
	\[
	c_{i,k} = \frac{|\{\mbox{functional $(i,k)$-prototypes}\}|}{i!},
	\]
	for all $i\ge 1$ and $i+1\le k \le 2^i$.
	Bounding the number of functional $(i,k)$-prototypes by the number of all injective functions $f:[k-1]\rightarrow \cP([i])\setminus\{\emptyset\}$ immediately yields for all $i\ge 1$ and $i+1\le k \le 2^i$
	\[
	c_{i,k} \le  \binom{2^i-1}{k-1}\frac{(k-1)!}{i!}.\qedhere
	\]
\end{proof}


%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
