\documentclass[psamsfonts]{amsart}
\usepackage{amssymb,amsfonts}
\usepackage[all,arc]{xy}
\usepackage{enumerate}
\usepackage{mathrsfs}

\newcommand{\NN}{{\mathbb N}}
\newcommand{\RR}{{\mathbb R}}

%theoremstyle{plain} --- default
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{quest}[thm]{Question}

\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{defns}[thm]{Definitions}
\newtheorem{con}[thm]{Construction}
\newtheorem{exmp}[thm]{Example}
\newtheorem{exmps}[thm]{Examples}
\newtheorem{notn}[thm]{Notation}
\newtheorem{notns}[thm]{Notations}
\newtheorem{addm}[thm]{Addendum}
\newtheorem{exer}[thm]{Exercise}

\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{rems}[thm]{Remarks}
\newtheorem{warn}[thm]{Warning}
\newtheorem{sch}[thm]{Scholium}

\makeatletter
\let\c@equation\c@thm
\makeatother
\numberwithin{equation}{section}

\bibliographystyle{plain}

\title{A solution to Berlekamp's switching game}

\author{Fan Fei Chong}

\date{AUGUST 11, 2007}

\begin{document}

\begin{abstract}

This paper studies a game played between two players on an $n \times n$ grid. Using tools from Linear Algebra and Elementary Probability theory, we can show that the ``payout" of the game is asymptotically $n^{\frac{3}{2}}$.

\end{abstract}

\maketitle

\tableofcontents

\section{The problem}

Before stating the problem, we need some asymptotic notation.

\begin{defn}  Let $a_n$, $b_n$ be sequences of real numbers, we say that
 \begin{enumerate}
 \item $a_n=O(b_n)$ if $|a_n/b_n|$ is bounded, i.e.,$ (\exists C>0, n_0 \in \NN)(\forall n>n_0)(|a_n|\leq C|b_n|)$
 \item $a_n=\Omega(b_n)$ if $b_n=O(a_n)$, i.e., if $|b_n/a_n|$ is bounded, $(\exists c>0, n_0 \in \NN)(\forall n>n_0)(|a_n|\geq c|b_n|)$
 \item $a_n=\Theta(b_n)$ if $a_n=O(b_n)$ and $a_n=\Omega(b_n)$, i.e. $(\exists C, c>0, n_0 \in \NN)(\forall n>n_0)(c|b_n| \leq |a_n| \leq C|b_n|)$
 \end{enumerate}
\end{defn}
Consider an $n \times n$ square grid. Each square can hold a value of $\pm1$. Player 1 starts the game and puts $\pm1$ in each cell. Player 2 selects a set of rows and a set of columns and switches the sign of each cell in the selected rows and columns. (If the sign of both the row and the column of a cell has been changed, this double change means no change for the cell.)\\

Let $S(n)$ be the sum of all the numbers in the grid after both players have played. This is the amount Player 1 pays to Player 2. Assuming we have both players playing with optimal strategy, what can we say about $S(n)$ as $n \to \infty$? We shall see that in fact $S(n)=\Theta(n^{3/2})$.

\section{A few observations}

We observe that S is always greater than or equal to 0. If the sum of all the numbers
is non-negative after Player 1 plays, Player 2 can just leave it alone. However, if the
sum is negative, Player 2 can bring it back to positive by switching the signs of every row.
So, now we have a trivial lower bound for S.

We will make a remark about Player 2's moves, before proceeding to improving the
lower bound.

\begin{rem} Notice the following:
\begin{enumerate}
\item All possible moves for Player 2 form a group, generated by the row operations and the column operations.
\item Each of the row operations and the column operations has order 2.
\item Any two operations (row or column) commute.
\end{enumerate}
\end{rem}

A direct consequence of this is that in consideration of the optimal strategy for Player 2, it suffices
to consider only strategies which consists of two phases: in the``first phase", Player 2 switches
a set of rows, and in the ``second phase", Player 2 switches a set of columns.

Once Player 2 is done with the ``first phase", it is clear that the best he can do in the following phase is to
switch a column \textbf{if and only if} the sum of entries in that column is negative. Now, the objective of
Player 2 boils down to maximizing the sum of the absolute value of the sum of entries in the columns.
If we write the numbers in the grid as a $n \times n$ matrix, and define $B_j=\sum^{n}_{i=1}a_{ij}$ to be the 
column sum of the j-th column, the objective of Player 2 would be to maximize $\sum^{n}_{j=1}|B_j|$ in ``first
phase". Similarly, Player 1's objective would be to impose an upper bound on $\sum^{n}_{j=1}|B_j|$.

\section{Hadamard matrix and Player 1's optimal strategy}

Before going into a discussion of Player 1's optimal strategy, we will first study the properties of a special
class of square matrix - the Hadamard matrix.

\begin{defn} A matrix H is an \textbf{Hadamard matrix} if all its entries are either 1 or -1 (we denote this $H=(\pm1)$) and its columns are orthogonal.
\end{defn}

\begin{lem} \label{Had_1} If $A=(\pm1)$ is an $n \times n$ matrix, then the following statements are equivalent.
\begin{enumerate}
\item A is Hadamard
\item $A^TA=nI$
\item $\frac{1}{\sqrt{n}}A \in O_n(\RR)$.
\end{enumerate}
\end{lem}
\begin{proof}
$(1)\Leftrightarrow(2)$: Let $\underline{a}_i$ be the $i^{th}$ column vector of A. Then $A^TA=(\underline{a}_i^T\underline{a}_j)$, i.e. the $(i,j)^{th}$ entry of $A^TA$ is the dot product of the $i^{th}$ with the $j^{th}$ column vectors of A. This implies that (2) is true if and only if $\underline{a}_i^T\underline{a}_i=n$ for all i (which is true because all the entries of A are either 1 or -1) and $\underline{a}_i^T\underline{a}_j=0$ for all $i \neq j$. The latter is true if and only if all the columns of A are orthogonal, which is precisely the definition of Hadamard matrix.\\
$(2)\Leftrightarrow(3)$: (2) implies that $\frac{1}{\sqrt{n}}A^T$ is a left inverse of $\frac{1}{\sqrt{n}}A$. Since determinant is multiplicative and $det(I)=1$, we then know that $det(A)\neq0$ and A is invertible. By the unique existence of inverse, $\frac{1}{\sqrt{n}}A^T$ is the inverse of $\frac{1}{\sqrt{n}}A$. Notice that the two expressions above are transpose of each other, and therefore $\frac{1}{\sqrt{n}}A\in O_n(\RR)$. The other direction of the implication follows immediately from the definition of orthogonal matrix.
\end{proof}

\begin{lem} \label{Had_2} If A is Hadamard, then 
$\begin{pmatrix}
A & A \\
A & -A
\end{pmatrix}$ is also Hadamard.
\end{lem}
The proof is clear from the definition of Hadamard matrix and left to the readers as an exercise. Notice that since the matrix $\begin{pmatrix}
1 & 1 \\
1 & -1
\end{pmatrix}$ is Hadamard, this fact allows us to find an $n \times n$ Hadamard matrix for every $n=2^k$ where $k\in \NN$.

\begin{lem} \label{Had_3} If $A=\left[\underline{a}_1, ...,\underline{a}_n\right]$ is an Hadamard matrix, then switching the signs (1 to -1, -1 to 1) of a whole row or a whole column would still give an Hadamard matrix.
\end{lem}
\begin{proof} The case for switching signs in a column is clear by definition of Hadamard matrix and the fact that inner product is bilinear. By Lemma \ref{Had_1}, it follows from $(1)\Leftrightarrow(3)$ that A is Hadamard if and only if the rows of A are orthogonal. And now, the same argument (as in the case of switching signs in a column) gives us that switching signs in a row would still keep the matrix Hadamard.
\end{proof}

We are only one lemma away from proving that $S(n) \leq cn^{3/2}$ for some constant c. Let's first remind ourselves of an elementary inequality which we will use in the proof of the next lemma.

\begin{prop} \label{CS} (Cauchy-Schwarz) For $a, b \in \RR^n$, we have $|a \cdot b| \leq ||a||\left\|b\right\|$.
\end{prop}

Now, we are ready to prove the key lemma which relates Hadamard matrix to the Switching Game (and hence Player 1's strategy).

\begin{lem} \label{Lindsey} (Lindsey's Lemma) If A is an $n \times n$ Hadamard matrix and T is a $k \times l$ submatrix, then $|\sum_{(i,j)\in T}a_{ij}|\leq \sqrt{nkl}$.
\end{lem}
To improve the readibility of the proof, we introduce the notion of incidence vector.
\begin{notn} Let N be the set \{1, 2, ..., n\} and K be a subset of it. Then the \textbf{incidence vector} of set K is the $n\times1$ column vector $I_K$ of 0's and 1's where the $i^{th}$ column is 1 if and only if $i \in K$. \end{notn}
\begin{proof}
Let $K \subset N, L \subset N$ be the set of rows and the set of columns that defines T. Note that $||I_K||=\sqrt{k}$ and $||I_L||=\sqrt{l}$.  Now the sum of all entries of T is $I_K^TAI_L$. We need to estimate $|I_K^TAI_L|$. Applying the Cauchy-Schwarz Inequality (Proposition \ref{CS}), setting $\vec{a}=I_K$ and $\vec{b}=AI_L$, we have $|I_K^TAI_L|\leq ||I_K|| \: ||AI_L||=\sqrt{k} \: ||AI_L||$.

By Lemma \ref{Had_1}, we have $\frac{1}{\sqrt{n}}A \in O_n(\RR)$. Hence $||(\frac{1}{\sqrt{n}}A)I_L|| = ||I_L||=\sqrt{l}$ and $||AI_L||=\sqrt{nl}$. This gives us the desired inequality $|I_K^TAI_L| \leq \sqrt{nkl}$.
\end{proof}

Now, we have finally achieved enough understanding of the Hadamard matrix to devise a strategy for Player 1 to sufficiently constrain the payout of the game.

\begin{thm} For all $n\geq 1$, $S(n) \leq \sqrt{2n^3}$.
\end{thm}
\begin{proof}
For a given n, pick $k\in\NN$ such that $2^{k-1} \leq n < 2^k$. By Lemma \ref{Had_2}, there exists an Hadamard matrix of dimension $2^k \times 2^k$. Pick one of such and call it A. Now Player 1 needs only pick any $n \times n$ submatrix of A, call it T and copy the distribution of 1's and -1's onto the $n \times n$ grid. Then no matter what Player 2 does, the payout is guaranteed to be $\leq \sqrt{2n^3}$. How does this work?

We can view the $n \times n$ grid (identified with T) as embedded in A. Now say Player 2 has decided to switch the signs in Row 1. We can extend this ``row move" of T to a ``row move" of A, involving the corresponding row of A which contains Row 1 of T. By Lemma \ref{Had_3}, A remains an Hadamard matrix after the move.  The ``modified" T would still be an $n \times n$ submatrix of an Hadamard matrix, by taking the same rows and columns as before from the ``modified" A. The same argument would work if Player 2 decides to change multiple rows and columns. Extending the ``row moves" and ``column moves" of T to the corresponding ones in A, we see that the ``modified" T remains an $n \times n$ submatrix of an Hadamard matrix of dimension $2^k \times 2^k$.

Therefore we may conclude using Lindsey's Lemma (Lemma \ref{Lindsey}) that after Player 2's turn, the sum of the entries in the grid is $\leq \sqrt{2^kn^2} \leq \sqrt{2n^3}$.
\end{proof}

This gives an upper bound for S(n). We proceed to show that this bound is tight (asymptotically) by demonstrating that the optimal strategy of Player 2 would guarantee a ``payout" which is greater than or equal to $cn^{\frac{3}{2}}$ for some $c\in\RR$.

\section{Probabilistic approach and Player 2's optimal strategy}

We are in fact not going to write out explicitly the optimal strategy, as it suffices to show that there exists a strategy for Player 2 which gives a ``payout"$\geq cn^{\frac{3}{2}}$. We will show this with a probablistic approach (which often yields elegant solutions in unexpected situations in combinatorics). Let's recall a result in elementary probability theory.

\begin{prop} \label{prob}
Let X be a discrete random variable. Then $\exists \ k\in\RR$ such that $k\geq E(X)$ and $P(X=k)>0$.
\end{prop}

We will discuss the implication of this result in light of a particular probabilistic strategy of Player 2. In the ``first phase", for each of the n rows, Player 2 tosses a fair coin. If the outcome is Head, he switches the signs in that particular row and does nothing if the coin-toss turns out otherwise. After this process, fix a $j$. We have each of the $a_{ij}$'s in that column \textbf{independently and identically distributed}(i.i.d.) as Bernoulli distribution with success probability 0.5 (i.e. Bin(1, 0.5)). It is easy to see that each entry has exactly 0.5 probability to stay the same, and 0.5 to be changed; this corresponds to 0.5 for +1 and 0.5 for -1, regardless of what the initial value is. Different entries at the same column are independently distributed because they depend on the outcome of different coin-tosses. Note that $E(a_{ij})=0$ and $Var(a_{ij})=1$ for all $1\leq i, j \leq n$. Now, let's recall a special case of the Central Limit Theorem for a sequence of i.i.d. variables.

\begin{thm} \label{CLT}  (Central Limit Theorem for i.i.d. Random Variables) Let $X_1, X_2,...$ be a sequence of independently identically distributed random variables having mean $\mu$ and variance $\sigma^2 \neq 0$. If additionally there exists $M \in \RR$ such that $P\{ |X_i|<M \} =1$, then $X := \sum_{i=1}^n X_i$ converges in distribution to $N(n\mu, n\sigma^2)$ (Normal Distribution with mean $n\mu$ and variance $n\sigma^2$)
\end{thm}

Note that $|a_{ij}| \leq 1$ with probability 1, so Theorem \ref{CLT} applies. We have that the column sum of the j-th column, $B_j=\sum^{n}_{i=1}a_{ij}$,  is converging in distribution to $N(0, n)$, with probability density function (p.d.f.): $f(x) = \frac{1}{\sqrt{2\pi} \sigma}e^{(-\frac{x}{\sqrt{2} \sigma})^2}$. Noticing that the above p.d.f. is symmetric about 0, we have $E[|B_j|] \rightarrow \int_0^\infty 2x f(x) dx$ as $n \rightarrow \infty$. The reader should check that the above integral is equal to $\sqrt{\frac{2}{\pi}} \sqrt{n}$.

Lastly, we need to recall the fact that the expected value operator is linear.

\begin{prop} Let $X_1, X_2, ..., X_n$ be random variables and $a_1, a_2, ..., a_n$ be real numbers. Then we have $E[\sum_{i=1}^{n}a_iX_i]=\sum_{i=1}^na_iE[X_i]$.
\end{prop}

For any two columns i and j, there is no reason why $|B_i|$ and $|B_j|$ are independent. Nevertheless, the above proposition enables us to sum up their expected values and have $E[\sum^{n}_{j=1}|B_j|]=\sum^{n}_{j=1}E[|B_j|]=n \sqrt{\frac{2}{\pi}} \sqrt{n}=\sqrt{\frac{2}{\pi}} n^{\frac{3}{2}}$. We have got the ``right number", but how does this calculation give a lower bound for the payout of Player 2's optimal strategy? We need Proposition \ref{prob}.

Let X be the random variable which gives the payout of the game if Player 2 follows the ``coin-tossing strategy" outlined above. It is clear that $X=\sum^{n}_{j=1}|B_j|$. Since X can only take on an integer value between $-n^2$ and $n^2$, it is then a discrete random variable. Then Lemma \ref{prob} would imply that there exists positive probability that $X \geq E[X]=\sqrt{\frac{2}{\pi}} n^{\frac{3}{2}}$. Since X is completely determined by the outcome of the $n$ coin-tosses, this implies there exists an outcome of the coin-tosses which gives instructions for Player 2 to achieve a payout at least as much as E[X]. By definition, the optimal strategy for Player 2 should achieve a payout at least as much as that achievable using any other strategy, so $\sqrt{\frac{2}{\pi}} n^{\frac{3}{2}}$ is a lower bound for the optimal payout for Player 2.

\section{Conclusion}
We have demonstrated that if both Player 1 and Player 2 play optimally, we then have $\sqrt{\frac{2}{\pi}} n^{\frac{3}{2}} \leq S(n) \leq \sqrt{2} n^{\frac{3}{2}}$ as $n \rightarrow \infty$. So as $n \rightarrow \infty$, $|S(n)/n^{\frac{3}{2}}| \leq \sqrt{2}$ and $|n^{\frac{3}{2}}/S(n)| \leq \sqrt{\frac{\pi}{2}}$, which means $S(n)=\Theta(n^{3/2})$.

\end{document}