% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}


\newcommand{\F}{\mathbb{F}}
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\bigabs}[1]{\big\lvert#1\big\rvert}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Pairs of quadratic forms over finite fields}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Alexander Pott\\
\small Faculty of Mathematics\\[-0.8ex]
\small Otto-von-Guericke University\\[-0.8ex]
\small Magdeburg, Germany\\
\small\tt alexander.pott@ovgu.de\\
\and
Kai-Uwe Schmidt\\
\small Department of Mathematics\\[-0.8ex]
\small Paderborn University\\[-0.8ex]
\small Paderborn, Germany\\
\small\tt kus@math.upb.de\\
\and
Yue Zhou\thanks{Yue Zhou is partially supported by the National Natural Science Foundation of China (No.~11401579).}\\
\small Department of Mathematics and System Sciences\\[-0.8ex]
\small National University of Defense Technology\\[-0.8ex]
\small Changsha, China\\
\small Department of Mathematics\\[-0.8ex]
\small Augsburg University\\[-0.8ex]
\small Augsburg, Germany\\
\small\tt yue.zhou.ovgu@gmail.com
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Jan 30, 2014}{Jan 2, 2012}\\
\small Mathematics Subject Classifications: 05E15, 05E30, 06E30}

\begin{document}

\maketitle

\begin{abstract}
Let $\F_q$ be a finite field with $q$ elements and let $X$ be a set of matrices over~$\F_q$. The main results of this paper are explicit expressions for the number of pairs $(A,B)$ of matrices in $X$ such that $A$ has rank~$r$, $B$ has rank $s$, and $A+B$ has rank $k$ in the cases that (i) $X$ is the set of alternating matrices over $\F_q$ and (ii) $X$ is the set of symmetric matrices over $\F_q$ for odd $q$. Our motivation to study these sets comes from their relationships to quadratic forms. As one application, we obtain the number of quadratic Boolean functions that are simultaneously bent and negabent, which solves a problem due to Parker and Pott.
\end{abstract}

\section{Introduction}

Let $\F_q$ be a finite field with $q$ elements. Let $X$ be a set of matrices of the same size over~$\F_q$ and let $X_k$ contain all matrices in $X$ of rank $k$. Define
\begin{equation}
N_X(r,s,k)=\bigabs{\{(A,B)\in X_r\times X_s:\,A+B\in X_k\}},   \label{eqn:def_N}
\end{equation}
which is the number of pairs $(A,B)$ of matrices in $X$ such that $A$ has rank~$r$, $B$ has rank $s$, and $A+B$ has rank $k$. We are interested in the numbers $N_X(r,s,k)$ when $X$ is the set of $m\times m$ alternating matrices over $\F_q$ and when $X$ is the set of $m\times m$ symmetric matrices over $\F_q$ (recall that a matrix is \emph{alternating} if it is skew-symmetric and its diagonal contains only zeros). Our motivation to study these sets comes from their relationships to quadratic forms over finite fields. Some consequences of our results for quadratic forms are discussed later in this section.
\par
Our main results are explicit expressions for the numbers $N_X(r,s,k)$, which involve the \emph{$q^2$-binomial coefficient} given by
\[
{x\brack k}=\prod_{i=1}^k(q^{2x-2i+2}-1)/(q^{2i}-1)
\]
for real $x$ and nonnegative integral $k$ (see~\cite{And1976} and~\cite{DelGoe1975}, for example,  for elementary properties of these numbers). For now we state our results for the most important case when $r=s=k=m$. The general results are postponed to later sections.
\par
We begin with the case that $X$ is the set of alternating matrices over~$\F_q$. Recall that every alternating matrix has even rank (see~\cite[Lemma~10]{DelGoe1975}, for example). We have the following result, which holds for finite fields of arbitrary characteristic.
\begin{theorem}
\label{thm:alt_fullrank}
Let $m$ be even and let $X$ be the set of $m\times m$ alternating matrices over $\F_q$. Writing $n=m/2$, we have
\[
N_X(m,m,m)=\frac{v}{q^n}\sum_{i=0}^{n}(-1)^i\,q^{i(i-1)}{n\brack i}\;\prod_{k=1}^{n-i}(q^{2k-1}-1)^2,
\]
where
\[
v=q^{n(n-1)}\prod_{k=1}^n\,(q^{2k-1}-1)
\]
is the number of nonsingular matrices in $X$.
\end{theorem}
\par
For the symmetric matrices we have the following result for finite fields of odd characteristic.
\begin{theorem}
\label{thm:sym_fullrank}
Let $q$ be an odd prime power and let $X$ be the set of $m\times m$ symmetric matrices over $\F_q$. Write $n=\lfloor (m+1)/2\rfloor$. Then, for odd $m$, we have
\[
N_X(m,m,m)=\frac{v}{q^n}\sum_{i=0}^{n}(-1)^i\,q^{i(i-1)}{n\brack i}\;\prod_{k=1}^{n-i}(q^{2k-1}-1)^2,
\]
and for even $m$, we have
\[
N_X(m,m,m)=\frac{v}{q^n}\sum_{i=0}^{n}(-1)^i\,q^{i(i-1)}{n\brack i}\;\prod_{k=1}^{n-i}(q^{2k}-q)^2,
\]
where
\[
v=\begin{cases}
q^{n(n-1)}\prod\limits_{k=1}^n(q^{2k-1}-1) & \quad\text{for odd $m$}\\[1ex]
q^{n(n+1)}\prod\limits_{k=1}^n(q^{2k-1}-1) & \quad\text{for even $m$}
\end{cases}
\]
is the number of nonsingular matrices in $X$.
\end{theorem}
\par
It can be shown that Theorem~\ref{thm:sym_fullrank} also holds for even $q$ and odd $m$. In particular, it can be shown that, if $q$ is even and $X$ is the set of $m\times m$ symmetric matrices over $\F_q$ and $Y$ is the set of $m+1\times m+1$ alternating matrices over $\F_q$, then
\[
N_X(m,m,m)=N_Y(m+1,m+1,m+1),
\]
and so $N_X(m,m,m)$ can be obtained from Theorem~\ref{thm:alt_fullrank}. This follows from a relationship between two association schemes (see~\cite[Section~5]{Sch2010}, for example) and our discussion on association schemes in Section~\ref{sec:general}. We could not prove, but conjecture based on its verification for $m\in\{2,4,6\}$, that Theorem~\ref{thm:sym_fullrank} also holds for even $q$ and even $m$. 
\par
A quadratic form on $\F_q^m$ that is nonsingular is also called \emph{bent} or a \emph{quadratic bent function}. (There is a more general definition~\cite{Car2010a} of the bent property for arbitrary functions from $\F_q^m$ to $\F_q$, which however is not required here.) Recall that there is a one-to-one correspondence between quadratic forms on $\F_q^m$ and $m\times m$ alternating matrices over $\F_q$ if $q=2$ and $m\times m$ symmetric matrices over $\F_q$ if $q$ is odd. Thus, for $q=2$ or odd $q$, a quadratic form on $\F_q^m$ is bent if the corresponding matrix is nonsingular.
\par
Vector spaces of bent functions are important in cryptography and coding theory (see~\cite{Car2010a} and~\cite{Car2010b}, for example) and $m$-dimensional spaces of bent functions on $\F_p^m$ for odd prime $p$ (also called \emph{planar} functions) are equivalent to commutative semifields of odd characteristic~\cite{CouHen2008}. Our results give the number of $2$-dimensional spaces of quadratic bent functions on $\F_2^m$. A related and more difficult problem is the determination of the number of inequivalent $2$-dimensional spaces of quadratic bent functions on $\F_q^m$. This number is known for odd $q$ and $m\in\{2,3\}$ and equals $1$ in these cases~\cite{Men1977},~\cite{OzbPot2014}.
\par
A quadratic form on $\F_2^m$ is \emph{negabent} if its associated alternating matrix $M$ is such that $M+I$ is nonsingular, where $I$ is the identity matrix~\cite{ParPot2007} (again there is a more general definition of negabent functions from $\F_2^m$ to $\F_2$~\cite{ParPot2007}, which we do not require here). A quadratic form on $\F_2^m$ is \emph{bent-negabent} if it is simultaneously bent and negabent. Hence bent-negabent quadratic forms on $\F_2^m$ can only exist if $m$ is even. It has been shown in~\cite[Theorem~8]{ParPot2007} that a quadratic form on $\F_2^m$ is bent-negabent if and only if its associated alternating matrix $M$ is such that $M$ and $M+I+J$ are both nonsingular, where $I$ and $J$ are the identity and the all-ones matrix, respectively. 
\par
Let $X$ be the set of $m\times m$ alternating matrices over $\F_2$ and let $X_k$ contain all matrices in $X$ of rank $k$. Since $X_0,X_1,\dots,X_m$ are the fibres of an association scheme (see Sections~\ref{sec:general} and~\ref{sec:alt}), we find by a general property of association schemes that, for fixed $A\in X_r$, the number of $B\in X_s$ such that $A+B\in X_k$ is independent of the particular choice of $A$. Therefore, Theorem~\ref{thm:alt_fullrank} gives the number of bent-negabent quadratic forms, solving a problem due to Parker and Pott~\cite[Problem~2]{ParPot2007}.
\begin{corollary}
The number of bent-negabent quadratic forms on $\F_2^{2n}$ is
\[
\frac{1}{2^n}\sum_{i=0}^{n}(-1)^i\,2^{i(i-1)}{n\brack i}\;\prod_{k=1}^{n-i}(2^{2k-1}-1)^2.
\]
\end{corollary}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{A general method}
\label{sec:general}

Suppose that $(X,+)$ is an abelian group of matrices over $\F_q$ (which is certainly true when $X$ is the set of $m\times m$ alternating or symmetric matrices over $\F_q$). In this case the numbers $N_X(r,s,k)$ can be computed as follows. Recall that the \emph{characters} of $(X,+)$ are the homomorphisms from $(X,+)$ to the multiplicative group of the complex numbers and form themselves a group, which is isomorphic to $(X,+)$.
\begin{lemma}
\label{lem:char_sum}
Let $(X,+)$ be an abelian group of matrices over $\F_q$ and let $X_k$ contain all matrices in $X$ of rank $k$. Then the numbers defined in~\eqref{eqn:def_N} satisfy
\[
N_X(r,s,k)=\frac{1}{\abs{X}}\sum_{\phi}\sum_{A\in X_r}\phi(A)\sum_{B\in X_s}\phi(B)\sum_{C\in X_k}\phi(C),
\]
where the first sum ranges over all characters $\phi$ of $(X,+)$.
\end{lemma}
\begin{proof}
Indeed, by an elementary property of characters, the sum
\[
\frac{1}{\abs{X}}\sum_{\phi}\phi(A+B-C)
\]
equals $1$ if $A+B=C$ and is zero otherwise. The lemma follows easily from this.
\end{proof}
\par
The computation of the numbers $N_X(r,s,k)$ is particularly simple in the case that $X$ has the structure of a (symmetric) translation scheme, which is an association scheme with additional properties. Let $X_0,X_1,\dots,X_m$ be a partition of $X$. Then $X$ is a \emph{translation scheme} with \emph{fibres} $X_0,X_1,\dots,X_m$ if the following properties are satisfied:
\begin{enumerate}
\item[(P1)] $X_0$ contains only the identity of $(X,+)$.
\item[(P2)] For all $r\in\{1,\dots,m\}$, we have $x\in X_r$ if and only if $-x\in X_r$.
\item[(P3)] If $x-y\in X_r$, then the number of $z\in X$ such that $z-y\in X_s$ and $x-z\in X_k$ is a constant $p(r,s,k)$ (called the \emph{intersection numbers}) depending only on $r$, $s$, and $k$, but not on the particular choice of $x$ and $y$.
\end{enumerate} 
We refer to~\cite{Del1973} and~\cite{DelLev1998} for background on association schemes and in particular to~\cite[Section~V]{DelLev1998} for background on translation schemes.
\par
Let $X_k$ contain all matrices in $X$ of rank $k$ and suppose that $X_0,X_1,\dots,X_m$ are the fibres of a translation scheme. Then by taking $y$ equal to the zero matrix in (P3), it is readily verified that the numbers $N_X(r,s,k)$ can be computed from the intersection numbers $p(r,s,k)$ via
\begin{equation}
N_X(r,s,k)=\abs{X_r}\cdot p(r,s,k).   \label{eqn:N_intersection_numbers}
\end{equation}
Let $\widehat{X}$ be the group of characters of $(X,+)$. There is a unique partition $\widehat{X}_0,\widehat{X}_1,\dots,\widehat{X}_m$ of $\widehat{X}$ with the property that
\begin{equation}
\sum_{A\in X_k}\phi(A)   \label{eqn:eigenvalue}
\end{equation}
is constant for each $\phi\in \widehat{X}_i$. The numbers~\eqref{eqn:eigenvalue}, denoted by $P_k(i)$, are the \emph{eigenvalues} of the translation scheme. It then follows from Lemma~\ref{lem:char_sum} that
\[
N_X(r,s,k)=\frac{1}{\abs{X}}\,\sum_{i=0}^m\abs{\widehat{X}_i}\;P_r(i)P_s(i)P_k(i),
\]
which, via~\eqref{eqn:N_intersection_numbers}, gives a well known formula for the intersection numbers (see~\cite[p.~227]{God1993}, for example). Hence, to compute $N_X(r,s,k)$, it is sufficient to know the \emph{multiplicities} $\abs{\widehat{X}_i}$ and the eigenvalues $P_k(i)$ of the translation scheme.
\par
This principle can be applied for example when $X$ is the set of $m\times n$ matrices over $\F_q$. Without loss of generality, assume that $m\le n$, in which case, $X_0,X_1,\dots,X_m$ are the fibres of an association scheme whose multiplicities and eigenvalues are given in~\cite{Del1978}. The principle can also be applied in the case that $X$ is the set of $m\times m$ alternating matrices over $\F_q$, which is discussed in Section~\ref{sec:alt}. However, in general, the principle cannot be applied in the case that $X$ is the set of $m\times m$ symmetric matrices over $\F_q$ since then (P3) in the definition of a translation scheme does not hold. We can however still apply Lemma~\ref{lem:char_sum} in this case, which we shall do in Section~\ref{sec:sym}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Alternating matrices}
\label{sec:alt}

Throughout this section, let $X$ be the set of $m\times m$ alternating matrices over $\F_q$ and write 
\[
n=\bigg\lfloor \frac{m}{2}\bigg\rfloor\quad\text{and}\quad c=q^{\frac{m(m-1)}{2n}},
\]
so that $\abs{X}=c^n$. Let $X_k$ contain all matrices in $X$ of rank~$k$. It is well known that $X_0,X_1,\dots,X_m$ are the fibres of a translation scheme~\cite{DelGoe1975}.
\par
Let $v(k)$ be the cardinality of $X_k$. (It turns out that these numbers are the multiplicities of the translation scheme.) It is known (see~\cite[Theorem~3]{Mac1969}, for example) that $v(k)=0$ for odd $k$ and
\begin{equation}
v(2i)={n\brack i}\,\prod_{k=0}^{i-1}\,(c-q^{2k})   \label{eqn:v_alt}
\end{equation}
for each $i\in\{0,\dots,n\}$. Let $A,S\in X$ and write $a_{ij}$ and $s_{ij}$ for their entries, respectively (indexed from $1$ to $m$). Let $\chi$ be a nontrivial character of $(\F_q,+)$ and define $\phi_S:X\to\mathbb{C}$ by
\[
\phi_S(A)=\chi\bigg(\sum_{1\le i<j\le m} s_{ij}a_{ij}\bigg).
\]
Since $X$ is an $\F_q$-vector space of dimension $m(m-1)/2$, the mapping $\phi_S$ ranges through all characters of $(X,+)$ as $S$ ranges over $X$. For $S\in X_{2i}$, the numbers
\[
P_k(i)=\sum_{A\in X_{2k}}\phi_S(A)
\]
are well defined. They are the eigenvalues of the translation scheme and given by~\cite{DelGoe1975}
\begin{equation}
P_k(i)=\sum_{j=0}^k(-1)^{k-j}q^{(k-j)(k-j-1)}{n-j\brack n-k}{n-i\brack j}\,c^j.   \label{eqn:eigenvalues}
\end{equation}
The following result is now a straightforward consequence of Lemma~\ref{lem:char_sum}.
\begin{theorem}
\label{thm:alt}
Let $X$ be the set of $m\times m$ alternating matrices over $\F_q$. Then the numbers defined in~\eqref{eqn:def_N} satisfy
\[
N_X(r,s,k)=\frac{1}{\abs{X}}\sum_{i=0}^n\,v(2i)\,P_r(i)P_s(i)P_k(i),
\]
where $v(2i)$ and $P_k(i)$ are given in~\eqref{eqn:v_alt} and~\eqref{eqn:eigenvalues}, respectively.
\end{theorem}
\par
To obtain Theorem~\ref{thm:alt_fullrank} from Theorem~\ref{thm:alt}, let $m$ be even, so that $m=2n$, and observe that in this case
\begin{equation}
P_n(i)=(-1)^iq^{n(n-1)}\prod_{k=1}^{n-i}(q^{2k-1}-1).   \label{Pn_alt}
\end{equation}
This formula can be either obtained from~\eqref{eqn:eigenvalues} by a tedious calculation using the q-binomial theorem
\begin{equation}
\sum_{j=0}^hq^{j(j-1)}{h\brack j}x^{h-j}\,y^j=\prod_{k=0}^{h-1}(x+q^{2k}y)\quad\text{for real $x,y$}   \label{eqn:q-binomial}
\end{equation}
or by observing that $P_n(0)=v(2n)$ and $P_n(i)$ satisfies the recurrence
\[
P_n(i)(1-q^{2n-2i+1})=P_n(i-1),
\]
which can be obtained from~\cite[Lemma~12]{DelGoe1975} and~\eqref{eqn:eigenvalues}. From~\eqref{eqn:v_alt} we find that
\begin{equation}
v(2i)=q^{i(i-1)}\,{n\brack i}\,\prod_{k=n-i+1}^{n}\,(q^{2k-1}-1).   \label{eqn:v_alt_2}
\end{equation}
Theorem~\ref{thm:alt_fullrank} is now easily obtained from Theorem~\ref{thm:alt} using~\eqref{Pn_alt} and~\eqref{eqn:v_alt_2}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Symmetric matrices}
\label{sec:sym}

Throughout this section, let $q$ be an odd prime power and let $\eta$ be the quadratic character of $\F_q$. Let $X$ be the set of $m\times m$ symmetric matrices over $\F_q$ and write 
\[
n=\bigg\lfloor\frac{m+1}{2}\bigg\rfloor\quad\text{and}\quad c=q^{\frac{m(m+1)}{2n}},
\]
so that $\abs{X}=c^n$. As usual, let $X_k$ be the subset of $X$ containing all matrices of rank $k$. 
\par
Let $A,S\in X$ and write $a_{ij}$ and $s_{ij}$ for their entries, respectively (indexed from $1$ to $m$). Let $\chi$ be a nontrivial character of $(\F_q,+)$ and define $\phi_S:X\to\mathbb{C}$ by
\[
\phi_S(A)=\chi\bigg(\sum_{i,j=1}^m s_{ij}a_{ij}\bigg).
\]
Since $X$ is an $\F_q$-vector space of dimension $m(m+1)/2$ and $q$ is odd, the mapping $\phi_S(A)$ ranges through all characters of $(X,+)$ as $S$ ranges over $X$. 
\par
Two matrices $A,B\in X$ are \emph{equivalent} if there exists a nonsingular matrix $L$ such that $LAL^T=B$. We recall some well known facts (see~\cite[Section~6.2]{LidNie1997}, for example). Every matrix $A\in X$ of rank~$r$ is equivalent to a diagonal matrix with main diagonal $[d_1,\dots,d_r,0,\dots,0]$, where $d_1,\dots,d_r$ are nonzero. The value $\eta(d_1\cdots d_r)$ is preserved under equivalence and is called the \emph{type} of $A$ (an empty product equals $1$ by convention and so the all-zero matrix has type $1$). Two matrices in $X$ are equivalent if and only if they have the same rank and the same type.
\par
Our further analysis crucially relies on the following lemma.
\begin{lemma}
\label{lem:character_rank_type}
The number
\[
\sum_{A\in X_k}\phi_S(A)
\]
depends only on the type and rank of $S$.
\end{lemma}
\begin{proof}
Let $L$ be an arbitrary $m\times m$ matrix over $\F_q$. For $A\in X$, we readily verify the identity
\[
\phi_{LSL^T}(A)=\phi_S(L^TAL).
\]
If $L$ is nonsingular, then the mapping $A\mapsto L^TAL$ induces a permutation on $X_k$ and hence
\[
\sum_{A\in X_k}\phi_{LSL^T}(A)=\sum_{A\in X_k}\phi_S(L^TAL)=\sum_{A\in X_k}\phi_S(A),
\]
as required.
\end{proof}
\par
In view of Lemma~\ref{lem:character_rank_type}, we may write
\[
P_k(i,\delta)=\sum_{A\in X_k}\phi_S(A),
\]
where $S$ is of rank $i$ and of type $\delta$.
\par 
The equivalence relation defined above partitions $X$ into $2m+1$ equivalence classes. Let $v(i,\delta)$ be the cardinality of the equivalence class containing matrices of rank $i$ and type $\delta$. It will be convenient to write $v(0,-1)=0$ and $P_k(0,-1)=1$.
\par
The following result is a consequence of Lemmas~\ref{lem:char_sum} and~\ref{lem:character_rank_type}.
\begin{theorem}
\label{thm:main_sym}
Let $q$ be an odd prime power and let $X$ be the set of $m\times m$ symmetric matrices over $\F_q$. Then the numbers defined in~\eqref{eqn:def_N} satisfy
\[
N_X(r,s,k)=\frac{1}{\abs{X}}\sum_{i=0}^m\sum_{\delta\in\{-1,1\}}v(i,\delta)\;P_r(i,\delta)P_s(i,\delta)P_k(i,\delta).
\]
\end{theorem}
\par
To apply Theorem~\ref{thm:main_sym} efficiently, we need to find explicit expressions for the numbers $v(i,\delta)$ and $P_k(i,\delta)$. The numbers $v(i,\delta)$ were computed by Carlitz~\cite{Car1954} and will be given in Proposition~\ref{pro:num_sym_mat}. The numbers $P_k(i,\delta)$ will be given in Proposition~\ref{pro:Pki_sym}. (These results depend on $\eta(-1)$, which equals $1$ if $q
\equiv 1\pmod 4$ and equals $-1$ otherwise.)
\begin{proposition}[{Carlitz~\cite[Theorem~3]{Car1954}}]
\label{pro:num_sym_mat}
We have
\begin{align*}
v(2s,\delta)&=\frac{(q^s+\eta(-1)^s\delta)}{2}\,\frac{(q^m-1)(q^m-q)\cdots(q^m-q^{2s-1})}{(q^{2s}-1)(q^{2s}-q^2)\cdots(q^{2s}-q^{2s-2})},\\[1ex]
v(2s+1,\delta)&=\frac{1}{2q^s}\,\frac{(q^m-1)(q^m-q)\cdots(q^m-q^{2s})}{(q^{2s}-1)(q^{2s}-q^2)\cdots(q^{2s}-q^{2s-2})}.
\end{align*}
\end{proposition}
\par
In what follows let $v(i)$ be the number of $m\times m$ symmetric matrices of rank $i$, so that $v(i)=v(i,1)+v(i,-1)$.
\begin{proposition}
\label{pro:Pki_sym}
Write $\ell=\lfloor k/2\rfloor$. Let
\[
F(m,k,s)=(-1)^k\sum_{j=0}^\ell(-1)^{\ell-j}q^{(\ell-j)(\ell-j+1)}{n-j-1\brack n-\ell-1}{n-s-1\brack j}\, c^j
\]
whenever this expression is defined and let $F(m,k,s)=0$ otherwise. Then $P_0(i,\delta)=1$ and $P_k(0,\delta)=v(k)$, and for $k,i\ge 1$, the numbers $P_k(i,\delta)$ are given by
\begin{gather}
P_k(2s+1,\delta)=F(m,k,s),   \label{Pki_odd}
\intertext{and}
P_k(2s,\delta)=F(m,k,s-1)+\delta\,\eta(-1)^s\, q^{m-s} F(m-1,k-1,s-1).   \label{Pki_even}
\end{gather}
\end{proposition}
\par
To prove Proposition~\ref{pro:Pki_sym}, we require the following recurrence relation for the numbers $P_k(i,\delta)$. Henceforth, we write $P^{(m)}_k(i,\delta)$ and $v^{(m)}(i)$ for $P_k(i,\delta)$ and $v(i)$, respectively, to indicate dependence on $m$.
\begin{lemma}
\label{lem:recurrence}
For $1\le i,k\le m$, we have
\[
P^{(m)}_k(i,\delta)=P^{(m)}_k(i-1,1)-(-\delta)^{i+1}\,\eta(-1)^s\,q^{m-s}\,P^{(m-1)}_{k-1}(i-1,1),
\]
where $s=\lfloor i/2\rfloor$.
\end{lemma}
\par
We first deduce Proposition~\ref{pro:Pki_sym} from Lemma~\ref{lem:recurrence} and then prove Lemma~\ref{lem:recurrence}.
\begin{proof}[Proof of Proposition~\ref{pro:Pki_sym}]
From the definition of $P_k(i)$ we see that $P_0(i,\delta)$ equals $1$ and $P_k(0,\delta)$ is the number of symmetric $m\times m$ matrices of rank $k$, namely $v(k)$.
\par
From this last identity and Lemma~\ref{lem:recurrence} we find that
\[
P^{(m)}_k(1,\delta)=v^{(m)}(k)-q^m\,v^{(m-1)}(k-1).
\]
With elementary manipulations we then deduce from Proposition~\ref{pro:num_sym_mat} that
\[
P^{(m)}_k(1,\delta)=\frac{(-1)^k}{q^\ell}\,\frac{(q^m-q)(q^{m}-q^2)\cdots(q^m-q^{2\ell})}{(q^{2\ell}-1)(q^{2\ell}-q^2)\cdots(q^{2\ell}-q^{2\ell-2})},
\]
which we can write as
\begin{equation}
P^{(m)}_k(1,\delta)=(-1)^k{n-1\brack \ell}\prod_{j=1}^\ell(c-q^{2j}).   \label{eqn:Pk1}
\end{equation}
Using
\[
{n-j-1\brack n-\ell-1}{n-1\brack j}={\ell\brack j}{n-1\brack \ell},
\]
we find that
\[
F(m,k,0)=(-1)^k{n-1\brack \ell}\sum_{j=0}^\ell q^{j(j-1)}{\ell\brack j}(-1)^j\,q^{2j}\,c^{\ell-j}.
\]
Applying the q-binomial theorem~\eqref{eqn:q-binomial}, we then see from~\eqref{eqn:Pk1} that
\begin{equation}
P^{(m)}_k(1,\delta)=F(m,k,0),   \label{eqn:initial}
\end{equation}
as required. Now substitute the recurrence in Lemma~\ref{lem:recurrence} into itself to obtain
\begin{equation}
P^{(m)}_k(2s+1,\delta)=P^{(m)}_k(2s-1,1)-c\,q^{2(n-s-1)}\,P^{(m-2)}_{k-2}(2s-1,1).   \label{eqn:P_rec_2}
\end{equation}
Using
\[
{n-s\brack j}-q^{2(n-s-j)}{n-s-1\brack j-1}={n-s-1\brack j},
\]
%Using $q$-analogues of Pascal's identities, 
it is readily verified that
\[
P^{(m)}_k(2s+1,\delta)=F(m,k,s)
\]
satisfies the recurrence~\eqref{eqn:P_rec_2} for all $s\ge 1$. Combination with~\eqref{eqn:initial} proves~\eqref{Pki_odd}. The identity~\eqref{Pki_even} is a then straightforward consequence of Lemma~\ref{lem:recurrence} and~\eqref{Pki_odd}.
\end{proof}
\par
We now prove Lemma~\ref{lem:recurrence}.
\begin{proof}[Proof of Lemma~\ref{lem:recurrence}]
Fix $i\in\{1,\dots,m\}$ and $\delta\in\{-1,1\}$. Let $S$ be an $m\times m$ diagonal matrix of rank $i$ with diagonal $[z,1,\dots,1,0,\dots,0]$ such that $\eta(z)=\delta$, and let $S'$ be an $(m-1)\times(m-1)$ diagonal matrix of rank $i-1$ with diagonal $[1,\dots,1,0,\dots,0]$. We have
\begin{align}
P^{(m)}_k(i-1,1)-P^{(m)}_k(i,\delta)&=\sum_{A\in X^{(m)}_k}\big(\phi_{S'}(B)-\phi_S(A)\big)   \label{eqn:diff_P}\\
&=\sum_{A\in X^{(m)}_k}\phi_{S'}(B)\big(1-\chi(za)\big),   \label{eqn:sum_AB}
\end{align}
where we write $A$ as
\begin{equation}
A=\begin{bmatrix}
a & v^T\\
v & B
\end{bmatrix}   \label{eqn:def_A}
\end{equation}
for some $a\in\F_q$, some $v\in\F_q^{m-1}$, and some $(m-1)\times(m-1)$ symmetric matrix $B$ over $\F_q$. The summand in~\eqref{eqn:sum_AB} is zero for $a=0$, so assume that $a$ is nonzero. Writing
\[
L=\begin{bmatrix}
1 & -a^{-1}v^T\\
0 & I
\end{bmatrix},
\]
we have
\[
L^TAL=\begin{bmatrix}
a & 0\\
0 & C
\end{bmatrix},\quad\text{where}\quad C=B-a^{-1}vv^T.
\]
Note that $L$ is nonsingular. Therefore, as $a\in\F_q^*$, $C\in X^{(m-1)}_{k-1}$, and $v\in\F_q^{m-1}$ range over their possible values, the matrix $A$, given in~\eqref{eqn:def_A}, ranges over all elements of $X^{(m)}_k$, except for those matrices~\eqref{eqn:def_A} satisfying $a=0$. Hence, using the homomorphism property of $\phi_{S'}$, the sum~\eqref{eqn:sum_AB} becomes
\begin{equation}
\sum_{a\in\F_q^*}\big(1-\chi(za)\big)\sum_{C\in X^{(m-1)}_{k-1}}\phi_{S'}(C)\sum_{v\in\F_q^{m-1}}\phi_{S'}(a^{-1}vv^T).   \label{eqn:sum_AB_2}
\end{equation}
By definition we have
\begin{equation}
\sum_{C\in X^{(m-1)}_{k-1}}\phi_{S'}(C)=P^{(m-1)}_{k-1}(i-1,1).   \label{eqn:sum_C}
\end{equation}
Furthermore,
\begin{align}
\sum_{v\in\F_q^{m-1}}\phi_{S'}(a^{-1}vv^T)&=q^{m-i}\sum_{v_1,\dots,v_{i-1}\in\F_q}\chi(a^{-1}(v_1^2+\cdots+v_{i-1}^2))   \nonumber\\
&=q^{m-i}\Bigg(\sum_{v\in\F_q}\chi(a^{-1}v^2)\Bigg)^{i-1}.   \label{eqn:sum_v}
\end{align}
Putting $\eta(0)=0$, the summation becomes
\begin{align}
\sum_{v\in\F_q}\chi(a^{-1}v^2)&=\sum_{y\in\F_q}(1+\eta(y))\chi(a^{-1}y)   \nonumber\\
&=\sum_{y\in\F_q}(1+\eta(ay))\chi(y)   \nonumber\\
&=\eta(a)\,G(\eta,\chi),   \label{eqn:sum_vx}
\end{align}
where
\[
G(\eta,\chi)=\sum_{y\in\F_q}\eta(y)\chi(y)
\]
is a Gauss sum. Substitute~\eqref{eqn:sum_vx} into~\eqref{eqn:sum_v} and then~\eqref{eqn:sum_v} and~\eqref{eqn:sum_C} into~\eqref{eqn:sum_AB_2}, we find that~\eqref{eqn:diff_P} equals
\[
P^{(m-1)}_{k-1}(i-1,1)\,q^{m-i}\,G(\eta,\chi)^{i-1}\sum_{a\in\F_q^*}\big(1-\chi(za)\big)\eta(a)^{i-1}.
\]
The inner summation equals $q$ for odd $i$ and, by an argument similar to that leading to~\eqref{eqn:sum_vx}, equals $-\eta(z)G(\eta,\chi)$ for even $i$. Hence, since $\eta(z)=\delta$, we have
\[
P^{(m)}_k(i-1,1)-P^{(m)}_k(i,\delta)=(-\delta)^{i+1}\,q^{m-2s}\,G(\eta,\chi)^{2s}\,P^{(m-1)}_{k-1}(i-1,1)
\]
(where $s=\lfloor i/2\rfloor$). The proof is completed by recalling that
\[
G(\eta,\chi)^2=\eta(-1)q
\]
(see~\cite[Theorem 5.12 (iv)]{LidNie1997}, for example).
\end{proof}
\par
In the remainder of this section we sketch how Theorem~\ref{thm:sym_fullrank} follows from Theorem~\ref{thm:main_sym} and Propositions~\ref{pro:num_sym_mat} and~\ref{pro:Pki_sym}.
\par
We first consider the case that $m$ is odd, thus $m=2n-1$. In this case, the expression $F(m-1,m-1,s)$ in Proposition~\ref{pro:Pki_sym} equals $0$ for all $s$ and we find that
\[
P_m(2i,1)=P_m(2i,-1)=P_m(2i-1,1)=P_m(2i-1,-1).
\]
Using the q-binomial theorem~\eqref{eqn:q-binomial}, we see that these numbers equal
\[
(-1)^iq^{n(n-1)}\prod_{k=1}^{n-i}(q^{2k-1}-1).
\]
Furthermore, from Proposition~\ref{pro:num_sym_mat} we find that
\[
v(2i,1)+v(2i,-1)+v(2i-1,1)+v(2i-1,-1)
\]
equals
\begin{equation}
q^{i(i-1)}{n\brack i}\prod_{k=n-i+1}^n(q^{2k-1}-1).   \label{eqn:v_sum}
\end{equation}
It then follows from Theorem~\ref{thm:main_sym} that
\[
N_X(m,m,m)=\frac{v(m)}{q^n}\sum_{i=0}^n(-1)^iq^{i(i-1)}{n\brack i}\prod_{k=1}^{n-i}(q^{2k-1}-1)^2,
\]
% (Note that $v(m)=v(2n)+v(2n-1)$ since $v(2n)=0$.
where $v(m)$, the number of nonsingular matrices in $X$, is given by
\[
v(m)=q^{n(n-1)}\prod_{k=1}^n(q^{2k-1}-1)
\]
(which can be obtained from~\eqref{eqn:v_sum} by putting $i=n$).
\par
Next we consider the case that $m$ is even, thus $m=2n$. In this case, the expression $F(m,m,s)$ in Proposition~\ref{pro:Pki_sym} equals $0$ for all $s$ and therefore we have
\[
P_m(2i+1,\delta)=0
\]
and
\[
P_m(2i,\delta)=\delta\,\eta(-1)^i\,(-1)^iq^{n^2}\prod_{k=1}^{n-i}(q^{2k}-q).
\]
Hence, by Theorem~\ref{thm:main_sym}, %$P_k(2i,-1)=-P_k(2i,1)$. 
\[
N_X(m,m,m)=\frac{1}{\abs{X}}\sum_{i=0}^n(v(2i,1)-v(2i,-1))P_m(2i,1)^3.
\]
From Proposition~\ref{pro:num_sym_mat} we find that
\[
v(2i,1)-v(2i,-1)=\eta(-1)^iq^{i(i-1)}{n\brack i}\prod_{k=n-i+1}^n(q^{2k}-q),
\]
and therefore,
\[
N_X(m,m,m)=\frac{v(m)}{q^n}\sum_{i=0}^n(-1)^iq^{i(i-1)}{n\brack i}\prod_{k=1}^{n-i}(q^{2k}-q)^2,
\]
where $v(m)$ is given by
\[
v(m)=q^{n^2}\prod_{k=1}^n(q^{2k}-q).
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% \bibliographystyle{plain} 
% \bibliography{references} 

\begin{thebibliography}{10}

\bibitem{And1976}
G.~E. Andrews.
\newblock {\em {The Theory of Partitions}}, volume~2 of {\em Encyclopedia of
  Mathematics and its Applications}.
\newblock Cambridge University Press, 1976.

\bibitem{Car2010a}
C.~Carlet.
\newblock Boolean functions for cryptography and error-correcting codes.
\newblock In Y.~Crama and P.~L. Hammer, editors, {\em Boolean models and
  methods in mathematics, computer science, and engineering}, pages 257--397.
  Cambridge University Press, 2010.

\bibitem{Car2010b}
C.~Carlet.
\newblock Vectorial boolean functions for cryptography.
\newblock In Y.~Crama and P.~L. Hammer, editors, {\em Boolean models and
  methods in mathematics, computer science, and engineering}, pages 257--397.
  Cambridge University Press, 2010.

\bibitem{Car1954}
L.~Carlitz.
\newblock Representations by quadratic forms in a finite field.
\newblock {\em Duke Math. J.}, 21:123--137, 1954.

\bibitem{CouHen2008}
R.~S. Coulter and M.~Henderson.
\newblock Commutative presemifields and semifields.
\newblock {\em Adv. Math.}, 217(1):282--304, 2008.

\bibitem{Del1973}
P.~Delsarte.
\newblock An algebraic approach to the association schemes of coding theory.
\newblock {\em Philips Res. Rep. Suppl.}, 10, 1973.

\bibitem{Del1978}
P.~Delsarte.
\newblock Bilinear forms over a finite field with applications to coding
  theory.
\newblock {\em J. Combin. Theory Ser. A}, 25(3):226--241, 1978.

\bibitem{DelGoe1975}
P.~Delsarte and J.~M. Goethals.
\newblock Alternating bilinear forms over {${\rm GF}(q)$}.
\newblock {\em J. Combin. Theory Ser. A}, 19(1):26--50, 1975.

\bibitem{DelLev1998}
P.~Delsarte and V.~I. Levenshtein.
\newblock Association schemes and coding theory.
\newblock {\em IEEE Trans. Inf. Theory}, 44(6):2477--2504, 1998.

\bibitem{God1993}
C.~D. Godsil.
\newblock {\em Algebraic combinatorics}.
\newblock Chapman and Hall Mathematics Series. Chapman \& Hall, New York, 1993.

\bibitem{LidNie1997}
R.~Lidl and H.~Niederreiter.
\newblock {\em Finite fields}, volume~20 of {\em Encyclopedia of Mathematics
  and its Applications}.
\newblock Cambridge University Press, 2nd edition, 1997.

\bibitem{Mac1969}
J.~MacWilliams.
\newblock Orthogonal matrices over finite fields.
\newblock {\em Amer. Math. Monthly}, 76:152--164, 1969.

\bibitem{Men1977}
G.~Menichetti.
\newblock On a {K}aplansky conjecture concerning three-dimensional division
  algebras over a finite field.
\newblock {\em J. Algebra}, 47(2):400--410, 1977.

\bibitem{OzbPot2014}
F.~{\"O}zbudak and A.~Pott.
\newblock Uniqueness of {$\mathbb{F}_q$}-quadratic perfect nonlinear maps from
  {$\mathbb{F}_{q^3}$} to {$\mathbb{F}_q^2$}.
\newblock {\em Finite Fields Appl.}, 29:49--88, 2014.

\bibitem{ParPot2007}
M.~G. Parker and A.~Pott.
\newblock On {B}oolean functions which are bent and negabent.
\newblock In {\em Sequences, subsequences, and consequences}, volume 4893 of
  {\em Lecture Notes in Comput. Sci.}, pages 9--23. Springer, Berlin, 2007.

\bibitem{Sch2010}
K.-U. Schmidt.
\newblock Symmetric bilinear forms over finite fields of even characteristic.
\newblock {\em J. Combin. Theory Ser. A}, 117(8):1011--1026, 2010.

\end{thebibliography}



\end{document}
