\section{Introduction}
Let $V$ be an algebraic variety defined over an algebraically closed field
$k$ of characteristic $p$. Let $G$ be a finite group acting on $V$ and $P\in V$
a fixed closed point of this action. Under these assumptions there is a
well-defined quotient algebraic variety $V/G$. Denote by $\pi\colon V\to V/G$
the natural projection. We say that $Q=\pi(P)\in V/G$ is an \emph{isolated
singularity}, if the variety $V/G$ is singular at $Q$ (i.e., the local ring
$\mathcal{O}_{V/G,Q}$ is not regular), and there are no other singular points
of $V/G$ in some Zariski open neighborhood of $Q$. If characteristic $p$
does not divide the order $|G|$ of $G$, isolated quotient singularities are
completely classified up to formal or, when $k=\C$ is the field of complex
numbers, up to analytic equivalence. The classification over $\C$ was obtained
by H. Zassenhaus, G. Vincent, and J. Wolf as a part of classification of
manifolds of constant positive curvature. It is summarized in Wolf's book
\cite{Wolf}, Chapters~5, 6, 7 (see also our survey in \cite{St}, which is
written from a point of view of singularity theory). It is not hard to see
that Zassenhaus-Vincent-Wolf classification covers also isolated quotient
singularities over arbitrary algebraically closed field $k$ of characteristic
$0$ and of prime characteristic $p$ where $p$ does not divide $|G|$.
The modular case $p\,|\,|G|$ remains open.

The first difficulty in the modular case is that the action of $G$ on $V$
is not in general linearizable in a formal neighborhood of a fixed point $P$.
This means that it is in general impossible to choose a system of parameters
$x_1,\ldots,x_n$ in the complete local ring $\widehat{\mathcal{O}_{V,P}}$ so
that $G$ acts on $\widehat{\mathcal{O}_{V,P}}$ via linear substitutions in
$x_1,\ldots,x_n$. Still a lot of isolated quotient singularities arise as
quotients by a nonlinear action of a modular group, see, e.g., \cite{Lorenzini}.
Thus the classification problem does not reduce to a problem of linear
representation theory as in the nonmodular case.  Nonlinear actions are
not considered in this paper, so from now on we assume that $V$ is a
vector space and $G$ is a subgroup of the general linear group $GL(V)$.
The second difficulty lies in the fact that the inverse
Chevalley-Shephard-Todd Theorem does not hold in the modular case. A linear
map $g\colon V\to V$ is called a \emph{pseudoreflection} if it has finite
order and the set of points fixed by $g$ is a hyperplane. By $S(V^*)$ we
denote the symmetric algebra of the dual space $V^*$ of $V$.
\begin{theorem}[Chevalley-Shephard-Todd Theorem, \cite{Benson}, Theorem~7.2.1]
\label{T:CST}
Let V be a finite dimensional vector space over a field $k$ of characteristic
$p$, $p\geq 0$, and $G$ a subgroup of $GL(V)$. Then if the ring of invariants
$S(V^*)^G$ of $G$ is polynomial (and in particular $V/G$ is nonsingular), then
the group $G$ is generated by pseudoreflections. If the characteristic $p$ does
not divide the order of the group $G$, then the converse also holds.
\end{theorem}
In the modular case, a quotient $V/G$ may be singular even for $G$ generated by
pseudoreflections, as is shown by the example of the symmetric group $S_6$
in its $4$-dimensional irreducible $2$-modular representation obtained as the
nontrivial constituent of the permutation module, see \cite{KM}, Example~2.2.
One can check that in this example the quotient singularity $V/S_6$ is not
isolated. In fact, this is a general phenomenon as follows from a remarkable
result of G. Kemper and G. Malle:
\begin{theorem}[\cite{KM}, Main Theorem]\label{T:KM}
Let $V$ be a finite dimensional vector space and $G$ a finite irreducible
subgroup of $GL(V)$. Then $S(V^*)^G$ is a polynomial ring if and only if $G$
is generated by pseudoreflections and the pointwise stabilizer in $G$ of any
nontrivial subspace of $V$ has a polynomial ring of invariants.
\end{theorem}
If the condition ``irreducible'' could be eliminated from the statement of
Theorem~\ref{T:KM}, the classification of isolated (linear) quotient
singularities would reduce to the nonmodular case, that is, to
Zassenhaus-Vincent-Wolf classification. Moreover, in Section~\ref{S:KMandIQS}
we prove the following equivalence.
\begin{theorem}\label{T:equiv}
The following two statements are equivalent:
\begin{enumerate}
\item Kemper-Malle Theorem~\ref{T:KM} holds for all, not only irreducible,
finite linear groups $G$;
\item let $G$ be a finite subgroup of $GL(V)$ and $H$ the normal subgroup of $G$
generated by pseudoreflections. If $V/G$ is an isolated singularity, then
$V/H$ is nonsingular, $p(=\charact k) \nmid |G/H|$, and
$$V/G \simeq (V/H)/(G/H),$$
i.e., any isolated quotient singularity $V/G$ is naturally isomorphic to a
nonmodular quotient singularity.
\end{enumerate}
\end{theorem}
It should be noted that the induced action of $G/H$ on $V/H$ may be nonlinear,
but since the group $G/H$ is nonmodular, its action can be locally formally
linearized in a neighborhood of the fixed point.

In Kemper-Malle Theorem~\ref{T:KM}, the ground field $k$ need not be
algebraically closed. But it is easy to see that the theorem holds for
general $k$ if and only if it holds for its algebraic closure $\Bar{k}$. Thus
there is no loss of generality in the assumption $k=\Bar{k}$.

In the sequel, we call statement (1) of Theorem~\ref{T:equiv}
\emph{Kemper-Malle conjecture}. Apart from irreducible groups, G. Kemper and
G. Malle proved it for groups $G$ acting on $2$-dimensional vector space $V$
(for $2$-dimensional groups in characteristic $p>3$ it was first proved by
H. Nakajima \cite{Nakajima}), for some indecomposable groups, and showed that it
suffices to prove the conjecture in general indecomposable case (\cite{KM}). We
are motivated by the problem of classifying the isolated quotient singularities
and find Kemper-Malle conjecture to be a key for the modular case. Indeed, as
follows from Theorem~\ref{T:equiv}, the meaning of the conjecture is that if it
holds, then \emph{essentially modular isolated (linear) quotient singularities
do not exist}, that is those that exist are in fact isomorphic to nonmodular
singularities. On the other hand, if statement (2) of Theorem~\ref{T:equiv}
could be proven with methods of algebraic geometry, this would imply the
conjecture. We succeeded only in dimension $3$ and odd characteristic $p>2$.
Our method relies on the classification of $2$-dimensional groups
generated by transvections and does not generalize to higher dimensions. Our
main result is the following
\begin{theorem}\label{T:main}
Let $V$ be a $3$-dimensional vector space over an algebraically closed field
of characteristic $p>2$. Let $G$ be a finite subgroup of $GL(V)$ generated
by pseudoreflections. Then if the quotient $V/G$ is singular, the singularity
is not isolated, i.e., Kemper-Malle conjecture holds for such groups.
\end{theorem}
We say that two singularities $P\in X$ and $Q\in Y$ are \emph{formally
isomorphic}, if there exists an isomorphism of complete local rings
$\widehat{\mathcal{O}_{X,P}}\simeq \widehat{\mathcal{O}_{Y,Q}}$.
\begin{corollary}
If $\dim V=3$, $p>2$, and $G$ is a finite subgroup of $GL(V)$ such that
$0\in V/G$ is an isolated singularity, then $0\in V/G$ is formally isomorphic
to one of nonmodular isolated quotient singularities in Zassenhaus-Vincent-Wolf
classification.
\end{corollary}
In fact, our result is a bit stronger than Theorem~\ref{T:main} and is
also applicable to some groups in even characteristic; see
Section~\ref{S:proof} for the precise formulation.

The paper is organized as follows. In Section~\ref{S:prelim} we collect
some material on quotient singularities used in the consequent sections.
In Section~\ref{S:KMandIQS} we prove Theorem~\ref{T:equiv}. We also
show that Kemper-Malle conjecture holds for groups $G$ possessing a
$1$-dimensional invariant subspace, in particular, for Abelian $G$.
Section~\ref{S:proof} is devoted to the proof of Theorem~\ref{T:main}.

The author is pleased to thank Professors G. Kemper and V.~L. Popov for
providing him with useful information on modular group actions.

\section{Preliminaries}\label{S:prelim}

The results of this section have already appeared in \cite{Kemper}. For the reader's
convenience, we state them in our notation and with complete proofs. If not stated
otherwise, $k$ denotes in this section a field of characteristic $p\geq 0$, not
necessarily algebraically closed.

\begin{lemma}\label{L:regofquot}
Let a finite group $G$ act linearly on the polynomial ring
$R=k[x_1,\dots,x_n]$. Then the ring of invariants $R^G$ is polynomial if
and only if $R^G$ is regular at the maximal ideal $\mathfrak{m}\cap R^G$,
where $\mathfrak{m}=(x_1,\dots,x_n)$.
\end{lemma}
\begin{proof}
Only the sufficiency needs a proof. Suppose that $R^G$ is regular at
$\mathfrak{m}\cap R^G$, but $R^G$ is not polynomial. But $R^G$ is a finitely
generated $k$-algebra (see, e.g., \cite{Benson}, Theorem~1.3.1), so let $f_1$,
$\dots$, $f_m$ be a minimal set of generators of $R^G$. Let $g_1(y_1,\dots,y_m)$,
$\dots$, $g_r(y_1,\dots,y_m)$ be a generating set of all relations between $f_1$,
$\dots$, $f_m$. Note that all the polynomials $f_i$, $i=1,\dots,m$, can be
chosen homogeneous of positive degree, whereas $g_j$, $j=1,\dots,r$,  weighted
homogeneous with
$$\text{weight of }y_i=\deg f_i.$$
It follows that $g_j(0,\dots,0)=0$ for all $j=1,\dots,r$. Moreover, all the
monomials of $g_j$ have degree $>1$, because otherwise the set of generators
$f_1$, $\dots$, $f_m$ would not be minimal. Thus by Jacobian criterion the
ring
$$k[y_1,\dots,k_m]\simeq R^G$$
is not regular at $0$, a contradiction.
\end{proof}

Now consider two algebras $A$ and $B$ without zero divisors over a
field $k$, where $A$ is a subalgebra of $B$. Let $\mathfrak{m}\subset A$ and
$\mathfrak{n}\subset B$ be maximal ideals such that $\mathfrak{n}\cap A=
\mathfrak{m}$. Denote by $j\colon A\to B$ the inclusion, by $\widehat{A}$ and
$\widehat{B}$ the formal completions of $A$ at $\mathfrak{m}$ and $B$ at
$\mathfrak{n}$ respectively, and by $\widehat{j}\colon \widehat{A}\to
\widehat{B}$ the map induced by $j$.

\begin{lemma}\label{L:alglem}
Assume that the following conditions are satisfied:
\begin{enumerate}
\item $A$ and $B$ are Noetherian;
\item $A/\mathfrak{m}=B/\mathfrak{n}=k$;
\item $B$ is unramified at $\mathfrak{n}$ over $A$, that is
$\mathfrak{m}B_\mathfrak{n}=\mathfrak{n}B_\mathfrak{n}$,
where $B_\mathfrak{n}$ is the localization of $B$ at $\mathfrak{n}$.
\end{enumerate}
Then $\widehat{j}$ is an isomorphism.
\end{lemma}
\begin{proof}
Let
$$j_n\colon \mathfrak{m}^n/\mathfrak{m}^{n+1}\to
\mathfrak{n}^n/\mathfrak{n}^{n+1},\: n\geq 0,$$
be the natural map induced by $j$. By \cite{AM}, Lemma~10.23, it is enough to
show that $j_n$ is an isomorphism for each $n\geq 0$. Note that
$$\mathfrak{n}^n/\mathfrak{n}^{n+1}\simeq
(\mathfrak{n}B_\mathfrak{n})^n / (\mathfrak{n}B_\mathfrak{n})^{n+1},$$
thus surjectivity of $j_n$ follows easily from condition (3). Let us
prove injectivity of $j_n$.

Assume on the contrary that $j_n$ is not injective for some $n\geq 0$. This
means that there is an element $a\in\mathfrak{m}^n$ such that $a\notin
\mathfrak{m}^{n+1}$, but $a\in\mathfrak{n}^{n+1}$. Considering $a$ as an
element of $B_\mathfrak{n}$ and using again condition (3), we can write $a$
as
$$a=\sum b_i a_i,$$
where $b_i\in B_\mathfrak{n}$, $a_i\in\mathfrak{m}^{n+1}$. Now use condition
(2) and the fact that the field $k$ is contained in $A$ and $B$ to write
$b_i=b_{i}^{0}+b'_{i}$, $b_{i}^{0}\in k$, $b'_{i}\in
\mathfrak{n}B_\mathfrak{n}$. This allows to rewrite $a$ as
$$a=\sum b_{i}^{0}a_i + b',$$
where, on the one hand, $b'$ is an element of $A$ not contained in
$\mathfrak{m}^{n+1}$ (otherwise we would have $a\in\mathfrak{m}^{n+1}$), on the
other hand, $b'$ is contained in $(\mathfrak{n}B_\mathfrak{n})^{n+2}\cap B =
\mathfrak{n}^{n+2}$. Moreover, $b'\ne 0$ because otherwise $a$ would not be
contained in $\mathfrak{n}^{n+1}$. Applying the same argument to $b'$ we get
$0\ne b''\in\mathfrak{n}^{n+3}$, $b''\in\mathfrak{m}^n$, $b''\notin
\mathfrak{m}^{n+1}$. It follows that $\mathfrak{m}^n\setminus
\mathfrak{m}^{n+1}$ contains nonzero elements of $\mathfrak{n}^N$ for
arbitrary large $N$.

The ideals $\mathfrak{n}^N$ are $k$-vector subspaces of $B$. Condition (1)
implies that $V=\mathfrak{m}^n/\mathfrak{m}^{n+1}$ is a finite dimensional
$k$-vector space. Thus
$$V_N=(\mathfrak{n}^N\cap \mathfrak{m}^n)/\mathfrak{m}^{n+1},\: N>n+1,$$
is a descending sequence of subspaces of $V$. This sequence stabilizes on some
subspace $W$ of $V$. We saw above that each member of the sequence has a
nonzero element, thus $W\ne 0$. On the other hand, by Krull's theorem
$\cap_{n\geq 0}\mathfrak{n}^n=(0)$, so we must have $W=0$. This contradiction
proves injectivity of $j_n$ and hence the lemma.
\end{proof}

Algebraic Lemma~\ref{L:alglem} can be applied to quotient singularities in
the following way. Let $G$ be a finite group that acts linearly on a vector
space $V$. Let $P\in V$ be a (closed) point and $H$ the stabilizer of
$P$ in $G$. Consider the quotients $V/H=\spec S(V^*)^H$ and $V/G=
\spec S(V^*)^G$. Let $Q\in V/H$ and $R\in V/G$ be the images of $P$ under the
natural projections $p_H\colon V\to V/H$ and $p_G\colon V\to V/G$. In general
$H$ is not normal in $G$, so there is no natural group action on $V/H$, but
anyway there is a morphism $\varphi\colon V/H\to V/G$ that makes the following
diagram commutative:
$$\begin{xymatrix}{
&V \ar[dd]_{p_G} \ar[rd]^{p_H} & \\
& &V/H \ar[ld]^{\varphi} \\
&V/G &
}
\end{xymatrix}
$$
Let $\widehat{\mathcal{O}}_{V/H,Q}$ and $\widehat{\mathcal{O}}_{V/G,R}$ be the
complete local rings of the points $Q\in V/H$ and $R\in V/G$ respectively.

\begin{lemma}\label{L:isomofquots}
Assume that the ground field $k$ is infinite. Then the map
$$\widehat{\varphi}\colon
\widehat{\mathcal{O}}_{V/H,Q}\to \widehat{\mathcal{O}}_{V/G,R}$$
induced by $\varphi$ is an isomorphism.
\end{lemma}
\begin{proof}
Let $\mathfrak{m}_P$ be the maximal ideal of the point $P\in V$,
$\mathfrak{m}_Q=\mathfrak{m}_P \cap S(V^*)^H$, $\mathfrak{m}_R=\mathfrak{m}_P
\cap S(V^*)^G$. Then apply Lemma~\ref{L:alglem} to the algebras $A=S(V^*)^G$,
$B=S(V^*)^H$, and the ideals $\mathfrak{m}_R$ and $\mathfrak{m}_Q$. We have to
check only condition (3) of Lemma~\ref{L:alglem}, i.e., that $B$ is
unramified at $\mathfrak{m}_Q$ over $A$.

First let us show that the ideal $\mathfrak{m}_Q$ is generated by polynomials
$f_1$, $\dots$, $f_n\in S(V^*)$ such that for all $i$, $1\leq i\leq n$,
$f_i(P)=0$, but for all $g\in G$, $g\notin H$, $f_i(gP)\ne 0$. Indeed, choose
a linear function $l$ on $V$ such that $l(P)=0$ but $l(gP)\ne 0$ for all
$g\in G$, $g\notin H$. Such choice is possible since $k$ is infinite. Consider
an invariant
$$L(v)=\prod_{h\in H} l(hv)$$
of the group $H$. Suppose now that $f'_1$, $\dots$, $f'_{n-1}$ is any
generating set of the ideal $\mathfrak{m}_Q$. Then one may choose $c_1$,
$\dots$, $c_{n-1}\in k$ so that the system
$$f_1=f'_1+c_1L,\:\dots,\:f_{n-1}=f'_{n-1}+c_{n-1}L,\: f_n=L$$
of generators of $\mathfrak{m}_Q$ has the desired property.

Now for each $i$, $1\leq i\leq n$, consider
$$g_i(v)=N_{H}^{G}(f_i)(v)=\prod_g f_i(gv),$$
where $g$ runs over a system of representatives of all right classes of $G$
modulo $H$. By construction $g_i$ is an invariant of $G$ and belongs to
$\mathfrak{m}_R$. Since $f_i$ is an invariant of $H$,
$$\frac{g_i}{f_i}=\prod_{g\notin H} f_i(gv),$$
where the product is taken over all representatives of nontrivial right
classes of $G$ modulo $H$, is also an invariant of $H$. Moreover,
$g_i/f_i(Q)\ne 0$, thus it is a unit in the local ring $\mathcal{O}_{V/H,Q}$.
It follows that $g_1$, $\dots$, $g_n$ generate the ideal
$\mathfrak{m}_Q\cdot\mathcal{O}_{V/H,Q}$.
\end{proof}

\begin{lemma}\label{L:fixator}
Let a finite group $G$ act linearly on a finite dimensional vector space $V$.
Suppose that $W$ is a subspace of $V$ which is pointwise fixed by $G$. Let
$P_1\in W$ and $P_2\in W$ be two (closed) points, and $Q_1\in V/G$, $Q_2\in V/G$
their images under the natural projection $p\colon V\to V/G$. Then the local
rings of $Q_1$ and $Q_2$ are isomorphic:
$$\mathcal{O}_{V/G,Q_1}\simeq\mathcal{O}_{V/G,Q_2}.$$
\end{lemma}
\begin{proof}
Let $v$ be a vector of $V$ that joins $P_1$ to $P_2$: $P_1+v=P_2$. The
translation by vector $v$ is an automorphism of $V$ as a scheme. Since $v\in W$,
this  translation can be pushed forward along $p$ to an automorphism of $V/G$
that maps the point $Q_1$ to $Q_2$. The lemma follows.
\end{proof}

\section{Kemper-Malle conjecture and isolated quotient singularities}
\label{S:KMandIQS}
In this section the field $k$ will be assumed algebraically closed. Let us
prove Theorem~\ref{T:equiv}. First consider the implication $(2)\Rightarrow(1)$.
Let $G$ be a subgroup of $GL(V)$ generated by pseudoreflections. By
Lemma~\ref{L:regofquot}, the ring $S(V^*)^G$ is polynomial if and only if $V/G$
is nonsingular at the image of the origin. But then $V/G$ is nonsingular
everywhere. Indeed, the singular set is closed, and $V/G$ can be singular only
at the image of a linear subspace of $V$. Then our theorem follows from
Chevalley-Shephard-Todd Theorem~\ref{T:CST} and Lemma~\ref{L:isomofquots}.

If $W$ is a subspace of $V$, denote by $\fix(W)$ the pointwise stabilizer
of $W$ in $G$. In the sequel we refer to $\fix(W)$ as the \emph{fixator} of
the subspace $W$. Suppose that $S(V^*)^{\fix(W)}$ is polynomial for every
nontrivial subspace $W$ of $V$. Then by Lemma~\ref{L:isomofquots} $V/G$ is
nonsingular everywhere except possibly the image of the origin. But since $G$
is generated by pseudoreflections, $V/G$ is nonsingular by (2).

Now let us prove the implication $(1)\Rightarrow(2)$. Let $G$ be a finite
subgroup of $GL(V)$ such that the singularity $V/G$ is isolated, and $H$ the
subgroup of $G$ generated by pseudoreflections. Then by
Lemma~\ref{L:isomofquots} and Chevalley-Shephard-Todd Theorem the fixator
$\fix(W)$ of every nontrivial subspace of $V$ is generated by pseudoreflections
and, moreover, $V/\fix(W)$ is nonsingular. Note also that $\fix(W)$ is contained
in $H$. Then, by (1), the quotient $V/H$ is nonsingular. Further, let $g$ be an
element of $G$ of order $p^r$, $r>0$, $p=\charact k$. Such an element
necessarily fixes a subspace $W$ of positive dimension. Thus $g\in\fix(W)$;
in particular, $g$ is contained in $H$. It follows that $p\nmid |G/H|$.
The nonmodular group $G/H$ acts naturally on $V/H$ and
$$V/G\simeq (V/H)/(G/H).$$
Theorem~\ref{T:equiv} is proven.

\begin{lemma}\label{L:dim1}
Kemper-Malle conjecture holds for groups $G$ possessing a $1$-dimensional
invariant subspace.
\end{lemma}
\begin{proof}
In view of Theorem~\ref{T:CST}, we have to show that if $G$ is generated
by pseudoreflections, has a $1$-dimensional invariant subspace, and $V/G$ is
singular, then the singularity $V/G$ is nonisolated. Let $W$ be the
$1$-dimensional invariant subspace of $G$. Note that in this case the
fixator $\fix(W)$ is normal in $G$. If $V/\fix(W)$ is singular, then
by Lemma~\ref{L:fixator} it is nonisolated. Thus by Lemma~\ref{L:isomofquots}
$V/G$ is also nonisolated.

Suppose that $V/\fix(W)$ is nonsingular. If $g$ is an element of $G$ of
order $p^r$, $r>0$, then the restriction of $g$ to the subspace $W$ is trivial.
Thus $g\in \fix(W)$. It follows that the quotient group $G/\fix(W)$ is
nonmodular. Its action on $V/\fix(W)$ can be locally formally linearized
(see, e.g., \cite{St}, Lemma~2.3), and, since $G$ is generated by
pseudoreflections, the linearization of $G/\fix(W)$ is also generated by
pseudoreflections. Then it follows from Chevalley-Shephard-Todd Theorem that
$$V/G\simeq (V/\fix(W))/(G/\fix(W))$$
is nonsingular.
\end{proof}

\begin{corollary}
Kemper-Malle conjecture holds for all Abelian groups generated by
pseudoreflections.
\end{corollary}
\begin{proof}
Indeed, a linear Abelian group always has a $1$-dimensional invariant subspace.
\end{proof}

\begin{corollary}
Let $G<GL(V)$ be a finite Abelian group such that the singularity $V/G$ is
isolated. Then $V/G$ is formally isomorphic to a nonmodular cyclic singularity.
\end{corollary}
\begin{proof}
We can get rid of pseudoreflections and assume that the group $G$ is nonmodular.
Then the statement follows from Zassenhaus-Vincent-Wolf classification of
isolated quotient singularities, see \cite{Wolf} or \cite{St}.
\end{proof}

Examples illustrating statement (2) of Theorem~\ref{T:equiv} are easy to
construct.
\begin{example}
Let $k$ be a field of characteristic $3$ and $V=k^2$. Let $G$ be a subgroup of
$GL(2,k)$ generated by
$$s=\begin{pmatrix}
2 & 0 \\
0 & 2
\end{pmatrix} \text{ and }
t=\begin{pmatrix}
1 & 1 \\
0 & 1
\end{pmatrix}.
$$
Then $G$ is isomorphic to the direct sum $\Z/2\oplus\Z/3$, and $t$ is a
pseudoreflection (transvection, see Section~\ref{S:proof}) generating a subgroup
$H$ isomorphic to $\Z/3$. Basis invariants of $H$ are
$$f_1=x(x+y)(x+2y) \text{ and } f_2=y,$$
where $x,y$ is a basis of $V^*$. Thus $V/H$ is nonsingular. $G/H\simeq\Z/2$ acts
on $f_1$ and $f_2$ via $f_1\mapsto -f_1$, $f_2\mapsto -f_2$, thus the singularity
$V/G$ is isolated and isomorphic to a quadratic cone.
\end{example}

\section{Proof of Theorem~\ref{T:main}}\label{S:proof}

Now we are going to prove our main result, Theorem~\ref{T:main}. It will be
a consequence of more general Theorem~\ref{T:main_gen}. First let us recall
some terminology. A pseudoreflection $g\colon V\to V$ is called a
\emph{transvection}, if $g$ has the only eigenvalue $1$. A transvection
necessarily has order $p$ equal to characteristic of the base field $k$. Note
that if $\dim V=2$, then any element of $GL(V)$ of order $p^r$, $r\geq 1$,
has in fact order $p$ and is a transvection.

\begin{theorem}\label{T:main_gen}
Let $V$ be a $3$-dimensional vector space over an algebraically closed field
of any characteristic $p$. Let $G$ be a finite subgroup of $GL(V)$ generated
by pseudoreflections. Denote by $G_p$ the normal subgroup of $G$ generated by
all elements of order $p^r$, $r\geq 1$. Assume that $G_p$ is either
\begin{enumerate}
\item irreducible on $V$, or
\item has a $1$-dimensional invariant subspace $U$, or
\item has a $2$-dimensional invariant subspace $W$ and the restriction of $G_p$
to $W$ is generated by two noncommuting transvections (and thus is irreducible).
\end{enumerate}
Then Kemper-Malle conjecture holds for $G$, i.e., if $V/G$ is singular, then
the singularity is not isolated. Moreover, if $G$ satisfies condition (3) or
condition (2) plus the induced action of $G_p$ on $V/U$ is generated by two
noncommuting transvections, then $V/G$ is nonsingular.
\end{theorem}

\begin{remark}\label{R:tgroupsindim2}
To see how Theorem~\ref{T:main} follows from Theorem~\ref{T:main_gen}, suppose
that $p$ is odd. In case (3) of Theorem~\ref{T:main_gen}, denote by $H$ the
restriction of the group $G_p$ to $W$. Since $\dim W=2$, $H$ is an irreducible
group generated by transvections. It follows from general representation
theory that $H$ is defined over a finite extension of the prime subfield of $k$
(\cite{CR}, Chapter XII). Classification of such groups is known since
the beginning of the twentieth century (see, e.g., \cite{Mitchell}, \S~1); it
implies that $H$ is conjugate in $GL(W)$ to the group $SL(2,q)$, $q=p^n$ -- the
group of $2\times 2$ matrices of determinant $1$ with entries in the Galois
field $\Fq$, -- or, in characteristic $p=3$, $H$ may also be conjugate to the
binary icosahedral group $I^*\simeq SL(2,5)$ in a $3$-modular representation. In
the last case $H$ is conjugate to the subgroup of $SL(2,9)$ generated by two
transvections
$$
t= \begin{pmatrix}
1 & 1 \\
0 & 1
\end{pmatrix} \text{ and }
s= \begin{pmatrix}
1 & 0 \\
\lambda & 1
\end{pmatrix},
$$
where $\lambda^2=-1$. Each group $SL(2,q)$ for odd $q$ is also generated by two
appropriate noncommuting transvections. In characteristic $2$, each group
generated by two noncommuting transvections is conjugate to an imprimitive group
generated by
$$
t= \begin{pmatrix}
0 & 1 \\
1 & 0
\end{pmatrix} \text{ and }
s= \begin{pmatrix}
x & 0 \\
0 & x^{-1}
\end{pmatrix},
$$
where $x\ne 0,1$ is an element of the field $\mathbb{F}_{2^n}$. Obviously, this
group is isomorphic to the dihedral group $D_n$. The group $SL(2,2^n)$, $n>1$,
is not generated by two transvections, whereas over an algebraically closed
field the group $SL(2,2)$ is conjugate to an imprimitive group described above.
\end{remark}

\begin{proof}
The case of irreducible groups $G$ is proved by G. Kemper and G. Malle in
\cite{KM}. The proof in case (2) follows from Lemma~\ref{L:dim1}. So we
concentrate on the proof of case (3).

Note that if we show that the quotient $V/G_p$ is nonsingular, then a
nonmodular group $G/G_p$ generated by pseudoreflections acts naturally on the
nonsingular variety $V/G_p$. Such an action is locally formally linearizable,
thus the quotient $V/G\simeq (V/G_p)/(G/G_p)$ is also nonsingular. Therefore
it is enough to prove our theorem in the case $G=G_p$.

Denote by $N$ the kernel of the restriction map $G\to H$, so that we have an
extension
\begin{equation}\label{E:extension}
1\to N\to G\to H\to 1.
\end{equation}
The group $N$ is Abelian and consists of the matrices of the form
$$\begin{pmatrix}
1 & 0 & a \\
0 & 1 & b \\
0 & 0 & 1
\end{pmatrix},
$$
where $a$, $b\in k$ and the basis is chosen so that the invariant subspace $W$
is generated by the first two vectors.

\begin{lemma}\label{L:ting}
In the conditions of case (3) of Theorem~\ref{T:main_gen}, the group $G$
necessarily contains transvections that restrict to (nontrivial) transvections of
the group $H$.
\end{lemma}
\begin{proof}
According to the classification of the irreducible groups generated by
transvections, the group $H$ is one of the following: $SL(2,q)$, $q$ is odd;
$I^*\simeq SL(2,5)$ in the $3$-modular representation described in
Remark~\ref{R:tgroupsindim2}; the imprimitive $2$-modular group also described
in Remark~\ref{R:tgroupsindim2}. In fact, our proof works also for
the groups $H=SL(2,2^n)$, $n>1$, so we shall study also this case. Let
us consider these possibilities one by one. In each case we assume that $G$ does
not contain transvections with nontrivial image in $H$, and come to a
contradiction.

\emph{Case 1}: $H=SL(2,q)$, $q$ is odd. Then $H$ contains matrices
$$
t= \begin{pmatrix}
1 & 1 \\
0 & 1
\end{pmatrix} \text{ and }
s= \begin{pmatrix}
1 & 0 \\
1 & 1
\end{pmatrix}.
$$
Let $\tilde{t}$ and $\tilde{s}$ be some lifts of $t$ and $s$ to $G$ respectively.
We assume that $\tilde{t}$ and $\tilde{s}$ are not transvections. Then one can
choose a basis in $V$ so that
$$
\tilde{t}= \begin{pmatrix}
1 & 1 & 0 \\
0 & 1 & 1 \\
0 & 0 & 1
\end{pmatrix},\quad
\tilde{s}= \begin{pmatrix}
1 & 0 & \mu \\
1 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix},
$$
where $\mu\ne 0$ is an element of $k$. One has
$$
\tilde{t}^{-1}\tilde{s}\tilde{t}= \begin{pmatrix}
0 & -1 & \mu \\
1 & 2 & 0 \\
0 & 0 & 1
\end{pmatrix},\quad
\tilde{s}^{-1}\tilde{t}\tilde{s}= \begin{pmatrix}
2 & 1 & 0 \\
-1 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix},
$$
$$
u=\tilde{t}^{-1}\tilde{s}\tilde{t}\tilde{s}^{-1}\tilde{t}\tilde{s}=
\begin{pmatrix}
1 & 0 & \mu-1 \\
0 & 1 & 2 \\
0 & 0 & 1
\end{pmatrix} \in N.
$$
Then
$$u^{-1}\tilde{s}=\begin{pmatrix}
1 & 0 & 1 \\
1 & 1 & -2 \\
0 & 0 & 1
\end{pmatrix}
$$
It follows that we could assume from the beginning that $\mu\in \Fq$.
Conjugating $u$ with appropriate elements of $G$ one gets elements of $N$ with
arbitrary vectors $(a,b,1)^T$, $a$, $b\in \Fq$ in place of the third column. In
particular, there is an element $u_1$ in $N$ with the third column $(0,-1,1)^T$.
The product  $u_{1}\tilde{t}$ is a transvection that restricts to $t\in H$.

\emph{Case 2}: $H=I^*<SL(2,9)$. We represent the field $\mathbb{F}_9$ as the
decomposition field of the polynomial
$$x^2+x+2$$
over $\mathbb{F}_3$. Then we can choose the transvections generating $H$ to be
$$
t= \begin{pmatrix}
1 & 1 \\
0 & 1
\end{pmatrix} \text{ and }
s= \begin{pmatrix}
1 & 0 \\
x+2 & 1
\end{pmatrix}.
$$
Denote again by $\tilde{t}$ and $\tilde{s}$ some lifts of $t$ and $s$ to $G$
respectively. If $\tilde{t}$ and $\tilde{s}$ are not transvections, in a
suitable basis they have matrices
$$
\tilde{t}= \begin{pmatrix}
1 & 1 & 0 \\
0 & 1 & 1 \\
0 & 0 & 1
\end{pmatrix},\quad
\tilde{s}= \begin{pmatrix}
1 & 0 & \mu \\
x+2 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix},
$$
where $\mu\ne 0$ is an element of $k$. By a routine calculation one checks that
$$(\tilde{t}\tilde{s})^5= \begin{pmatrix}
2 & 0 & 2x+1 \\
0 & 2 & \mu+2 \\
0 & 0 & 1
\end{pmatrix}, \quad
(\tilde{s}\tilde{t})^5= \begin{pmatrix}
2 & 0 & 2x+2\mu+1 \\
0 & 2 & \mu \\
0 & 0 & 1
\end{pmatrix},
$$
$$
u=(\tilde{t}\tilde{s})^5 (\tilde{s}\tilde{t})^5= \begin{pmatrix}
1 & 0 & \mu \\
0 & 1 & 2 \\
0 & 0 & 1
\end{pmatrix} \in N.
$$
It follows that
$$\tilde{u}=u\tilde{s}= \begin{pmatrix}
1 & 0 & 0 \\
x+2 & 1 & 1 \\
0 & 0 & 1
\end{pmatrix} \in G.
$$
Then one has
$$(\tilde{t}\tilde{u})^5= \begin{pmatrix}
2 & 0 & 2x+1 \\
0 & 2 & 2 \\
0 & 0 & 1
\end{pmatrix}, \quad
(\tilde{u}\tilde{t})^5= \begin{pmatrix}
2 & 0 & x+2 \\
0 & 2 & 0 \\
0 & 0 & 1
\end{pmatrix},
$$
and
$$
u_1=(\tilde{t}\tilde{u})^5 (\tilde{u}\tilde{t})^5= \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 2 \\
0 & 0 & 1
\end{pmatrix} \in N.
$$
Then $(u_{1}^{-1} u)^{-1} \tilde{s}$ is a transvection that restricts to
$s\in H$.

\emph{Case 3}: $H$ is imprimitive, the characteristic of $k$ is $2$. The
generators $t$ and $s$ of $H$ are defined in Remark~\ref{R:tgroupsindim2}. Their
lifts to $G$ can be chosen to be
$$\tilde{t}= \begin{pmatrix}
0 & 1 & \mu \\
1 & 0 & \mu^{-1} \\
0 & 0 & 1
\end{pmatrix} \text{ and }
\tilde{s}= \begin{pmatrix}
x & 0 & 0 \\
0 & x^{-1} & 0 \\
0 & 0 & 1
\end{pmatrix}
$$
respectively; here $\mu\ne 0,1$ is an element of $k$. One has
$$\tilde{t}^2= \begin{pmatrix}
1 & 0 & \mu+\mu^{-1} \\
0 & 1 & \mu+\mu^{-1} \\
0 & 0 & 1
\end{pmatrix},\:
(\tilde{s}\tilde{t})^2= \begin{pmatrix}
1 & 0 & \mu^{-1}+x\mu \\
0 & 1 & \mu+x^{-1}\mu^{-1} \\
0 & 0 & 1
\end{pmatrix} \in N.
$$
Together with $\tilde{t}^2$, $(\tilde{s}\tilde{t})^2$ the group $N$ contains also
all their conjugates and products. One easily deduces that $N$ contains all
matrices with the third column
$$(f(x)(x+1)\mu,f(x^{-1})(x^{-1}+1)\mu^{-1},1)^T$$
for all polynomials $f$ with coefficients in $\mathbb{F}_2$. If the minimal
polynomial $g$ of $x$ over $\mathbb{F}_2$ is reciprocal, that is $g(x^{-1})=0$,
then if $h(x)(x+1)=1$ for some polynomial $h$, then also $h(x^{-1})(x^{-1}+1)=1$.
It follows that $N$ contains a matrix $u$ with the third column
$(\mu,\mu^{-1},1)^T$. Then $u\tilde{t}$ is a transvection that restricts to
$t\in H$. If $g$ is not reciprocal, then, taking $f=g$, we see that $N$ contains
a matrix with the third column
$$(0,g(x^{-1})(x^{-1}+1)\mu^{-1},1)^T.$$
Its conjugates and their combinations produce also a matrix with the third
column $(0,\mu^{-1},1)^T$. Taking $f$ to be the minimal polynomial for $x^{-1}$,
we find also a matrix in $N$ with the third column $(\mu,0,1)$. Then it again
easily follows that $G$ has a transvection that restricts to $\tilde{t}$.

\emph{Case 4}: $H=SL(2,2^n)$, $n>1$. Since $SL(2,2)$ is a subgroup of each
$SL(2,2^n)$, it is enough to prove the lemma for $H=SL(2,2)$. But this is
already proved above since $SL(2,2)$ is conjugate to an imprimitive group.
\end{proof}

\begin{lemma}
The group $G$ contains transvections that restrict to generators of the group
$H$. This holds also for $H=SL(2,2^n)$, $n>1$.
\end{lemma}
\begin{proof}
The group $H=SL(2,2^n)$, as well as imprimitive groups $H$ and $H=I^*<SL(2,9)$,
have only one conjugacy class of transvections. Thus for these groups the lemma
follows directly from Lemma~\ref{L:ting}. The groups $H=SL(2,q)$, $q$ is odd,
have two conjugacy classes of transvections. The transvections
$$
t'= \begin{pmatrix}
1 & a \\
0 & 1
\end{pmatrix} \text{ and }
t''= \begin{pmatrix}
1 & b \\
0 & 1
\end{pmatrix},
$$
$a$, $b\in\Fq$, are conjugate if and only if $a$ and $b$ simultaneously are
or are not squares in $\Fq$. The two noncommuting transvections $t$ and $s$
generating $SL(2,q)$ can be chosen in the form
$$
t= \begin{pmatrix}
1 & 1 \\
0 & 1
\end{pmatrix}, \quad
s= \begin{pmatrix}
1 & 0 \\
\lambda & 1
\end{pmatrix},
$$
where $\lambda$ must be an element of $\Fq$ not belonging to a smaller field,
and $\lambda^2\ne -1$ if $q=9$. We have already seen in the proof of
Lemma~\ref{L:ting} that $t$ is a restriction of a transvection from $G$.
Clearly $\lambda$ in $s$ can be chosen to be or not to be a square in $\Fq$, so
that $t$ and $s$ are conjugate.
\end{proof}

\begin{lemma}\label{L:splitting}
Extension~\eqref{E:extension} is a semidirect product, and the group
$H$ can be embedded in $G$ so that it acts on $V$ via a decomposable
representation with two invariant subspaces of dimensions $1$ and $2$.
\end{lemma}
\begin{proof}
Lift two generating transvections $t$ and $s$ of $H$ to transvections $\tilde{t}$
and $\tilde{s}$ of $G$ and consider the subgroup that they generate in $G$.
The planes fixed by $\tilde{t}$ and $\tilde{s}$ intersect at a line not
contained in the invariant subspace $W$. This gives the desired splitting.
\end{proof}

\begin{remark}
At least for $H=SL(2,q)$, $q$ is odd, Lemma~\ref{L:splitting} could also be
proved with a help of known results on vanishing of the first and the second
group cohomology of $SL(2,q)$ with coefficients in the natural module
(\cite{CPS}, \cite{Chih-Han}), or with a help of the complete reducibility of
low dimensional modules over $SL(2,q)$ (\cite{Guralnik}). However, we would have
to study in detail the structure of $N$ as a module over $H$, and consider
separately the cases $H=I^*$ and $H$ is imprimitive. This is the reason why we
have preferred the elementary uniform proof presented above.
\end{remark}

From now on, we fix some splitting of \eqref{E:extension} and consider $H$ as a
subgroup of $G$. Next we are going to study the quotient $V/G$ in two steps:
first take the quotient $V/N$ and then consider the induced action of $H$ on
$V/N$. By \cite{CW}, Theorem~3.9.2, the invariant ring of $N$ is polynomial.

\begin{lemma}
The induced action of $H$ on $V/N\simeq k^3$ is linear and decomposable with
invariant subspaces of dimensions $1$ and $2$.
\end{lemma}
\begin{proof}
Fix a basis for $V$ in which the elements of $H$ are represented by block
matrices of the form
$$\begin{pmatrix}
a & b & 0 \\
c & d & 0 \\
0 & 0 & 1
\end{pmatrix}.
$$
Let $x$, $y$, $z$ be the dual basis of $V^*$. Then $N$ acts on $x$, $y$, $z$ via
transformations
$$x\mapsto x+\lambda z,\quad y\mapsto y+\mu z,\quad z\mapsto z,$$
$\lambda$, $\mu\in k$. Clearly, $f_3=z$ is invariant. Let $f_1$ and $f_2$ be
two other invariants that together with $f_3$ generate $S(V^*)^N$. One can
choose $f_1$ and $f_2$ homogeneous and not containing the monomial $z^m$ with a
nonzero coefficient. First let us assume that $f_1$ and $f_2$ have different
degrees, say, $\deg f_2< \deg f_1$. Then $f_2$ must be semiinvariant under the
induced action of $H$. Indeed, the degree of $f_2$ is preserved, thus for
$h\in H$ the polynomial $h\cdot f_2$ expresses only through $f_2$ and $f_3$,
but also $h$ acts only on $x$ and $y$, thus $h\cdot f_2$ expresses only through
itself. Moreover, since $H$ is generated by elements of order $p$ but any
element of $\Fq^*$ has multiplicative order coprime to $p$, $f_2$ is in fact
an invariant of $H$. For the same reason if
$$h\cdot f_1 = \lambda f_1 + g(f_2,f_3),$$
then $\lambda=1$ for each $h\in H$. But then the subset of $V/N$ defined by
equations $f_2=f_3=0$ is pointwise fixed under the action of $H$. The natural
projection $V\to V/N$ is $H$-equivariant. In turn, this implies that $G$ has an
invariant line contained in the subspace $W=\{z=0\}$, which contradicts the
condition $H$ to be irreducible on $W$.

It follows that $\deg f_1= \deg f_2$. By the same argument as above $h\cdot f_1$
and $h\cdot f_2$ are linear combinations of $f_1$ and $f_2$. On $V/N$ the group
$H$ acts also by block matrices, thus the representation is decomposable.
It should be also possible to prove this lemma by a direct computation of the
invariants of $N$ and the induced action of $H$ on them.
\end{proof}

Let $V/N=V_1\oplus V_2$ be the decomposition of $V/N$ into a sum of invariant
$H$-modules, $\dim V_1=2$, $\dim V_2=1$. Since the group $H$ acting on $V$ is
generated by transvections, the action of $H$ on $V_1$ and $V_2$ is also
generated by transvections. In particular, the action on $V_2$ is trivial, and
the invariant ring of $H$ acting on $V_1$ is polynomial (see, e.g., \cite{KM},
Proposition~7.1). It follows that the invariant ring of $H$ acting on $V/N$ is
also polynomial, and hence the invariant ring of $G$ acting on $V$ is polynomial.

It remains to show that if $G$ acts on $V$ with a $1$-dimensional invariant
subspace $U$ and the induced action of $G$ on $W=V/U$ is irreducible and
generated by two noncommuting transvections, then $V/G$ is again nonsingular.
This situation is in some sense dual to the one considered above. Denote
$H$ the natural image of $G$ in $GL(W)$ and $N$ the corresponding kernel. We
again have an extension of the form \eqref{E:extension}. In an appropriate basis
$N$ is an Abelian group of the matrices of the form
$$\begin{pmatrix}
1 & a & b \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix},
$$
where $a$, $b\in k$. An argument, which is similar to the one given above and
which we do not write here, shows that the group $G$ contains transvections that
map to the generators of $H$. The proof of the following lemma is easy and left
to the reader.
\begin{lemma}
Any two transvections on a $3$-dimensional vector space have a common
$2$-dimensional invariant subspace.
\end{lemma}

Now if $\tilde{t}$ and $\tilde{s}$ are transvections of $G$ that map to
generators of $H$, consider their common $2$-dimensional invariant subspace.
Clearly it does not contain $U$, thus can be identified with $W$. It follows
that the sequence~\eqref{E:extension} again splits.

In a suitable basis $x$, $y$, $z$ of $V^*$, the group $N$ acts via
transformations of the form
$$x\mapsto x+ay+bz,\quad y\mapsto y,\quad z\mapsto z.$$
It is not hard to determine basis invariants of $N$. They are
$$f_1=\prod_{g\in N} g\cdot x,\quad f_2=y,\quad f_3=z,$$
in particular, the invariant ring $S(V^*)^N$ is polynomial. It is also clear in
this case that the induced action of $H$ on $V/N$ is linear and decomposable.
As above, it follows that $(V/N)/H$ and hence $V/G$ is nonsingular. This
finishes the proof of Theorem~\ref{T:main_gen}.
\end{proof}


\section{Introduction}

Let $V=\{1,\ldots,n\}$.  We say that a Hermitian matrix $A\in\mathbb{C}^{n\times n}$ can be colored with $c$ colors if there exists a partition of $V$ into disjoint subsets $V_1,\ldots,V_c$ such that for each $s=1,\ldots,c$ we have $a_{k\ell}=0$ for all $k,\ell\in V_s$.

In the special case when $A$ is the adjacency matrix of a graph, this corresponds to the usual graph coloring.  We say that the graph can be colored with $c$ colors if it is possible to assign at most $c$ different colors to its vertices such that any two adjacent vertices receive different colors. The chromatic number $\chi$ is the minimum number of colors required to color the graph.

In 2007, Nikiforov proved the following theorem \cite{Nikiforov07}:

\begin{theorem}\label{thm:Niki}
Let $A\in\mathbb{C}^{n\times n}$ be an arbitrary Hermitian matrix that is colorable with $c$ colors.  Then, for any real diagonal matrix
$B\in\mathbb{C}^{n\times n}$, we have
\begin{equation}
\lambda_{\max}(B-A) \ge \lambda_{\max} \left( B + \frac{1}{c-1} A\right)
\end{equation}
\end{theorem}
This theorem implies immediately several known lower bounds on the chromatic number.  It is convenient to formulate the following corollary to obtain
elegant derivations of these bounds.
\begin{cor}\label{cor}
Let $A\in\mathbb{C}^{n\times n}$ be an arbitrary Hermitian matrix that is colorable with $c$ colors.  Then, for any real diagonal matrix
$B\in\mathbb{C}^{n\times n}$, we have
\begin{equation}
\lambda_{\max}(B-A) \ge \lambda_{\max} ( B + A ) - \frac{c-2}{c-1} \lambda_{\max}(A)
\end{equation}
and consequently
\begin{equation}
c \ge 1 + \frac{\lambda_{\max}(A)}{\lambda_{\max}(A) - \lambda_{\max}(B+A) + \lambda_{\max}(B-A)}.
\end{equation}
\end{cor}
\begin{proof}
Consider the statement of Nikiforov's theorem and write the matrix on the right hand side as $B+\frac{1}{c-1}A = B+A - \frac{c-2}{c-1} A$.  It is easy to see that $\lambda_{\max}(X-Y)\ge\lambda_{\max}(X)-\lambda_{\max}(Y)$ holds for arbitrary
Hermitian matrices. In particular, this inequality holds for $X=B+A$ and $Y=\frac{c-2}{c-1} A$, which yields the statement of the corollary.
\end{proof}

To state the lower bounds on the chromatic number, we need to introduce some notation.
Let $G$ be a graph with $n$ vertices, $m$ edges, chromatic number $\chi$ and adjacency matrix $A$.  Let $D$ be the diagonal matrix of vertex degrees.  Let $L=D-A$ denote the Laplacian of $G$ and $Q=D+A$ denote the signless Laplacian of $G$.
The eigenvalues of $A$ are denoted by $\mu_1\ge\ldots\ge \mu_n$; of $L$ by $\theta_1 \ge \ldots \ge \theta_n =0$; of $Q$ by $\delta_1\ge\ldots\ge\delta_n\ge 0$.  It is known that for all graphs $\delta_i \ge 2 \mu_i$ holds for $i=1,\ldots,n$.

\begin{theorem}[Lower bounds on the chromatic number]\label{thm:bounds}
The chromatic number is bounded from below by:
\begin{eqnarray}
\chi & \ge & 1 + \frac{\mu_1}{-\mu_n} \label{eq:Hoffman} \\
\chi & \ge & 1 + \frac{\mu_1}{\theta_1 - \mu_1} \label{eq:Niki} \\
\chi & \ge & 1 + \frac{\mu_1}{\mu_1 - \delta_1 + \theta_1} \label{eq:Kolo1} \\
\chi & \ge & 1 + \frac{\mu_1}{\mu_1 - \delta_n + \theta_n} \label{eq:Kolo2}
\end{eqnarray}
The bound (\ref{eq:Hoffman}) was proved by Hoffman \cite{Hoffman70} in 1970, the bound (\ref{eq:Niki}) by Nikiforov \cite{Nikiforov07} in 2007, and the bounds (\ref{eq:Kolo1}) and (\ref{eq:Kolo2}) by Kolotilina \cite{Kolotilina} in 2010.  Observe that we include $\theta_n=0$ in (\ref{eq:Kolo2}) on purpose because our generalization of this bound makes use of the eigenvalues of $L$.
\end{theorem}
\begin{proof}
Hoffman's bound (\ref{eq:Hoffman}) is equivalent to the statement of Theorem~\ref{thm:Niki} when $A$ is the adjacency matrix and $B$ is the zero matrix.  Kolotilina's bounds (\ref{eq:Kolo1}) and (\ref{eq:Kolo2})
are equivalent to the statement of Corollary~\ref{cor} when $A$ is the adjacency matrix and $B=\pm D$, respectively.
Note that Nikiforov's hybrid bound (\ref{eq:Niki}) follows from
(\ref{eq:Kolo1}) since $\delta_1 \ge 2\mu_1$.
\end{proof}

One of the purposes of this article to prove a multi-eigenvalue generalization of Nikiforov's theorem and to apply it to spectral graph theory.

Throughout the paper we use the following notation.  For an arbitrary Hermitian matrix $X\in\mathbb{C}^{n\times n}$, let $\lambda^\downarrow_1(X),\ldots,\lambda^\downarrow_n(X)$ denote its eigenvalues sorted in non-increasing order.

\begin{theorem}\label{thm:majThm}
Let $A\in\mathbb{C}^{n\times n}$ be an arbitrary Hermitian matrix that can be colored with $c$ colors.  Then, for any real diagonal matrix
$B\in\mathbb{C}^{n\times n}$, we have
\begin{equation}
\sum_{i=1}^m \lambda_i^\downarrow (B-A) \ge \sum_{i=1}^m \lambda_i^\downarrow \left( B + \frac{1}{c-1} A\right) \ge
\sum_{i=1}^m \lambda_i^\downarrow (B+A) - \frac{c-2}{c-1} \sum_{i=1}^m \lambda_i^\downarrow (A)
\end{equation}
for all $m=1\,\ldots,n$.
\end{theorem}
The proof of Theorem~\ref{thm:majThm} follows from our method of conversion of the adjacency matrix into the zero matrix and results of majorization theory.
Using this theorem, we obtain the following generalizations of the above lower bounds on the chromatic number.

\begin{theorem}[Generalized lower bounds on the chromatic number]\label{thm:genBounds}
The chromatic number is bounded from below by:
\begin{eqnarray}
\chi & \ge & 1 + \frac{\sum_{i=1}^m \mu_i}{-\sum_{i=1}^m \mu_{n+1-i}} \label{eq:genHof} \\
\chi & \ge & 1 + \frac{\sum_{i=1}^m \mu_i}{\sum_{i=1}^m (\theta_i - \mu_i)} \label{eq:genNiki} \\
\chi & \ge & 1 + \frac{\sum_{i=1}^m \mu_i}{\sum_{i=1}^m (\mu_i - \delta_i + \theta_i)} \label{eq:genKolo1} \\
\chi & \ge & 1 + \frac{\sum_{i=1}^m \mu_i}{\sum_{i=1}^m (\mu_i - \delta_{n+1-i} + \theta_{n+1-i})} \label{eq:genKolo2}
\end{eqnarray}
for all $m=1,\ldots,n$.
\end{theorem}

\begin{remark}
In 2011 Lima, Oliveira, Abreu and Nikiforov \cite{LOAN} proved that
\begin{equation}\label{eq:LOAN}
\chi \ge 1 + \frac{2m}{2m-n \delta_n}.
\end{equation}
We provide a new proof of this result based on the method of converting the adjacency matrix into the zero matrix.  This conversion method is at the heart of the proof of Theorem~\ref{thm:majThm}.  Observe that since $\mu_1 \ge 2m/n$, bound (\ref{eq:Kolo2})  follows immediately from this result.
\end{remark}

\section{Normalization}

\subsection{Normalization based on sequence of degrees}

Let $G$ be a graph with no isolated vertices. Let $D$ denote the diagonal matrix whose entries $d_1,\ldots,d_n$ are the degrees of the vertices.  Shigehalli and Shettar \cite{SS11} have defined a normalized adjacency matrix of $G$, $\mathcal{A} = D^{-1/2} A D^{-1/2}$. This accords with Chung's \cite{Chung97} earlier definition of a normalized Laplacian matrix $\mathcal{L} = I -\mathcal{A}$.  We can similarly define a normalized signless Laplacian matrix $\mathcal{Q} = I + \mathcal{A}$. Let $1 = \mu_1^* \ge \mu_2^* \ge \ldots \ge \mu_n^*$ denote the eigenvalues of $\mathcal{A}$; $\theta_1^* \ge \theta_2^* \ge \ldots \ge \theta_n^* = 0$ denote the eigenvalues of $\mathcal{L}$; and  $\delta_1^* \ge \delta_2^* \ge \ldots \ge \delta_n^*$ denote the eigenvalues of $\mathcal{Q}$. Note that $\theta_i^* = 1 - \mu_{n-i+1}^*$ and $\delta_i^* = 1 + \mu_i^*$, for all $i$.

In Corollary~\ref{cor} we can let $B = 0$ and $A=\mathcal{A}$; $B = I$ and $A = \mathcal{L}$; and $B = -I$ and $A = \mathcal{Q}$. These lead to normalized versions of the Hoffman and Kolotilina bounds. However, because of the relationships between the eigenvalues of $\mathcal{A}$, $\mathcal{L}$, and $\mathcal{Q}$, all three normalized bounds are equal to the following inequality:
\begin{equation}\label{eq:norHoffman}
\chi \ge 1 + \frac{1}{-\mu_n^*}
\end{equation}
Bound (\ref{eq:norHoffman}) is exact for all bipartite graphs and for regular graphs for which bound (\ref{eq:Hoffman}) is exact.   It is also exact for some irregular graphs for which bound (4) is not exact, such as Sierpi\'nski and some Windmill graphs.  It may be possible to characterize all irregular graphs for which bound (14) is exact.

In Theorem~\ref{thm:majThm} we can also let $B=0$ and $A=\mathcal{A}$; $B = I$ and $A = \mathcal{L}$; and $B = -I$ and $A = \mathcal{Q}$. These lead to normalized versions of bounds (\ref{eq:genHof}), (\ref{eq:genKolo1}) and (\ref{eq:genKolo2}), all of which are equal to:
\begin{equation}\label{eq:norGenHof}
\chi \ge 1 + \frac{\sum_{i=1}^m \mu_i^*}{\sum_{i=1}^m -\mu^*_{n+i-1}}
\end{equation}
for all $m = 1, ..., n$.

These normalized bounds are equal to the equivalent un-normalized bounds for regular graphs. However, as discussed in section~\ref{sec:performance} below, bounds (\ref{eq:norHoffman}) and (\ref{eq:norGenHof}) perform better than the un-normalized bounds for many named irregular graphs that we have examined. The normalized bounds typically perform less well than the un-normalized bounds for random graphs. We presume this difference in performance reflects the greater structure in named graphs, which is captured by normalisation.

\subsection{General weighting and connection to vector chromatic number}

Let $G=(V,E)$ be an arbitrary graph on $n$ vertices and $A$ its adjacency matrix.  We now refer to $\mathcal{A}$ more generally as a weighted adjacency matrix if
$\mathcal{A}$ is Hermitian and the entry of $\mathcal{A}$ in the $k$th row and $\ell$th column is zero whenever the corresponding entry of $A$ in the $k$th row and $\ell$th column is zero.  Clearly, if $A$ is colorable with $c$ colors then so is $\mathcal{A}$.  We also consider the weighted Laplacian $\mathcal{L}=D-\mathcal{A}$ and the weighted signless Laplacian $\mathcal{Q}=D+\mathcal{A}$ where $D$ is an arbitrary diagonal matrix with real entries.

Theorem~\ref{thm:genBounds} allows us to obtain lower bounds on the chromatic number of $G$ if we consider arbitrary weighted matrices $\mathcal{A}$, $\mathcal{L}$ and $\mathcal{Q}$.  Unfortunately, we do not know efficient methods which make it possible to compute optimally weighted matrices that yield the best possible spectral lower bounds on the chromatic number.  This remains an interesting open problem.

We now establish a connection to the vector chromatic numbers and show that the strong vector chromatic number provides a lower bound on the chromatic number that is at least as good as the generalized Hoffman bound (\ref{eq:genHof}) in the special case where $\mathcal{A}$ has only non-negative entries and $m=1$.

Let $v_1,\ldots,v_n$ be unit vectors in $\mathbb{R}^n$.  Let $\< v_k, v_\ell\>$ denote the inner product between the two vectors $v_k$ and $v_\ell$.
Following \cite{KMS98, FLS04}, we define the vector chromatic number, the strict vector chromatic number and the strong vector chromatic number.

The vector chromatic number $\chi_v$ of $G$ is the smallest positive $k$ such that
\[
\<v_k,v_\ell\> \le -\frac{1}{k-1} \quad\mbox{for all $(k,\ell)\in E$}.
\]
The strict vector chromatic number $\chi_v'$ of $G$ is the smallest positive $k$ such that
\[
\<v_k,v_\ell\> = -\frac{1}{k-1} \quad\mbox{for all $(k,\ell)\in E$}.
\]
The strict vector chromatic number is equal to the Lovasz $\theta$ function on $\bar{G}$, where $\bar{G}$ is the complementary graph.
The strong vector chromatic number $\chi_v''$ of $G$ is the smallest positive $k$ such that
\begin{eqnarray*}
\<v_k,v_\ell\> & =   & -\frac{1}{k-1} \quad\mbox{for all $(k,\ell)\in E$}, \\
\<v_k,v_\ell\> & \ge & -\frac{1}{k-1} \quad\mbox{for all $(k,\ell)\not\in E$}.
\end{eqnarray*}
We have the following inequalities \cite{KMS98, FLS04}:
\[
\omega \le \chi_v \le \chi_v' \le \chi_v'' \le \chi
\]
It is important that all three vector chromatic indices can be computed efficiently since the corresponding optimization problems can be formulated as semidefinite programs \cite{KMS98,FLS04,BV}.

Bilu \cite{Bilu} proved that the chromatic number $\chi$ in the generalized Hoffman bound
\begin{equation}
\chi \ge 1 + \frac{\lambda_{\max}(\mathcal{A})}{-\lambda_{\min}(\mathcal{A})}
\end{equation}
can in fact be replaced by the vector chromatic number $\chi_v$ when $\mathcal{A}$ is an arbitrary weighted adjacency matrix of $G$ having only non-negative entries.  DeVos \cite{DeVos} presented a simpler proof of this result.

The above discussion shows that instead of trying to determine an optimally weighted adjacency matrix $\mathcal{A}$ with non-negative entries to obtain the best possible spectral lower bound on the chromatic number, we can directly compute the strong vector chromatic number $\chi_v''$.

It is an interesting problem to find an example where the generalized lower bounds using arbitrary matrices $\mathcal{A}$, $\mathcal{L}$ and $\mathcal{Q}$ and $m\ge 1$ give a better lower bound on the chromatic number than the strong vector chromatic number.

\section{Proof of Theorem~\ref{thm:majThm}, proof of the generalized lower bounds, and alternative proof of the bound due to Lima et al.}

\subsection{Majorization of spectra of Hermitian matrices}

The following statement is presented in \cite[Exercise II.1.14]{bhatia}.
\begin{lemma}
Let $X,Y\in\mathbb{C}^{n\times n}$ be arbitrary Hermitian matrices.
Then for all $m=1,\ldots,n$
\begin{equation}
\sum_{i=1}^m \lambda^\downarrow_i(X+Y)  \le
\sum_{i=1}^m \lambda^\downarrow_i(X) + \sum_{i=1}^m \lambda^\downarrow_i(Y).
\end{equation}
\end{lemma}
This lemma immediately implies the following two results.  We formulate these results explicitly to simplify the proof of Theorem~\ref{thm:majThm}.

Let $X_1,\ldots,X_d\in\mathbb{C}^{n\times n}$ be arbitrary Hermitian matrices.  Then
\begin{equation}\label{eq:resOne}
\sum_{i=1}^m \lambda_i^\downarrow(X_1) + \ldots + \sum_{i=1}^m \lambda_i^\downarrow(X_d) \ge
\sum_{i=1}^m \lambda_i^\downarrow\left( X_1 + \ldots + X_d\right).
\end{equation}
This result is obtained by combining the above lemma with induction on $d$.

Let $S,T\in\mathbb{C}^{n\times n}$ be two arbitrary Hermitian matrices.  Then
\begin{equation}\label{eq:resTwo}
\sum_{i=1}^m \lambda_i^\downarrow( S - T) \ge \sum_{i=1}^m \lambda_i^\downarrow(S) - \sum_{i=1}^m \lambda_i^\downarrow(T).
\end{equation}
This result follows from the above lemma by setting $X=S-T$ and $Y=T$.

\subsection{Conversion of the adjacency matrix $A$ into the zero matrix}

The following theorem was proved by Wocjan and Elphick \cite{WE}.  We also present an alternative proof of this result in this paper in Theorem~\ref{thm:unitaryPinching}.

\begin{theorem}[Conversion of adjacency matrix]\label{thm:conversion}
Let $A\in\mathbb{C}^{n\times n}$ be an arbitrary Hermitian matrix that can be colored with $c$ colors.  Then, there exist $c$ diagonal unitary matrices $U_1, \ldots, U_c$ whose entries are $c$th roots of unity such that
\begin{equation}
\sum_{s=1}^{c}  U_s^\dagger A U_s  = 0.
\end{equation}
\end{theorem}
Without loss of generality we may assume that $U_c$ is the identity matrix.

\subsection{Proof of Theorem~\ref{thm:majThm}}

\begin{proof}
Theorem~\ref{thm:conversion} implies that
\[
\sum_{s=1}^{c}  U_s^\dagger (B - A) U_s  = c B
\]
since $U_s B U_s^\dagger = B U_s U_s^\dagger = B$ holds because the diagonal matrices $U_s$ and $B$ commute and $U_s U_s^\dagger = I$ for all $s$.  We may assume without loss of generality that the last matrix $U_c$ is equal to the identity matrix, which leads to the matrix equation
\begin{equation}\label{eq:matEq}
\sum_{s=1}^{c-1}  U_s^\dagger (B - A) U_s  = (c-1) B + A.
\end{equation}
We obtain the first desired statement
\begin{equation}\label{eq:desiredOne}
\sum_{i=1}^m \lambda_i^\downarrow (B-A) \ge \sum_{i=1}^m \lambda_i^\downarrow \left( B + \frac{1}{c-1} A\right)
\end{equation}
by applying the result in (\ref{eq:resOne}) with $X_s = U_s^\dagger(B-A) U_s$ for $s=1,\ldots,c-1$ to the left hand side of (\ref{eq:matEq}) and by dividing everything by $(c-1)$.  We also use that conjugation by a unitary matrix does not change the spectrum of a Hermitian matrix, that is, $\lambda_i^\downarrow (X_s)=\lambda_i^\downarrow (B-A)$ for all $i$ and $s$.

We obtain the second desired statement
\[
\sum_{i=1}^m \lambda_i^\downarrow \left( B + \frac{1}{c-1} A\right) \ge \sum_{i=1}^m \left( \lambda_i^\downarrow ( B + A) - \frac{c-2}{c-1} \lambda_i^\downarrow (A) \right)
\]
by writing $B + \frac{1}{c-1} A=B+A - \frac{c-2}{c-1}A$ and applying the result in (\ref{eq:resTwo}) with $S=B+A$ and $T=\frac{c-2}{c-1}A$ to the right hand side of (\ref{eq:desiredOne}).
\end{proof}

As noted in the introduction, the above result encompasses the special case
\[
\lambda^\downarrow_1\left(
 B + \frac{1}{c-1} A
 \right)
 \le \lambda^\downarrow_1( B - A),
\]
which was proved by Nikiforov in \cite[Theorem 1]{Nikiforov07} using entirely different techniques.

\subsection{Proofs of the generalized bounds}

The generalized Hoffman bound (\ref{eq:genHof}) is equivalent to the statement of Theorem~\ref{thm:majThm} when $A$ is the adjacency matrix and $B$ is the zero matrix.  The generalized Kolotilina bounds (\ref{eq:genKolo1}) and (\ref{eq:genKolo2})
are equivalent to the statement of Theorem~\ref{thm:majThm} when $A$ is the adjacency matrix and $B=\pm D$, respectively.
Note that the generalized Nikiforov bound (\ref{eq:genNiki}) follows from
(\ref{eq:genKolo1}) since $\delta_i \ge 2\mu_i$ for all $i$.

\subsection{Alternative proof of the lower bound due to Lima et al.}

We now give an alternative proof of the Lima, Oliveira, Abreu and Nikiforov bound in (\ref{eq:LOAN}).
Using the conversion technique, the identity $D-Q=-A$, and the invariance of the diagonal entries under conjugation by the diagonal unitary matrices $U_s$ we obtain
\[
A = \sum_{s=1}^{c-1} U_s(-A)U_s^\dagger = \sum_{s=1}^{c-1} U_s(D-Q)U_s^\dagger = (c-1) D - \sum_{s=1}^{c-1} U_s Q U_s^\dagger.
\]
Define the column vector $v=\frac{1}{\sqrt{n}}(1,1,\ldots,1)^T$. We multiply the left and right most sides of the above matrix equation by $v^\dagger$ from the left and by $v$ from the right and obtain
\[
\frac{2m}{n} = v^\dagger A v = (c-1) \frac{2m}{n} - \sum_{s=1}^{c-1} v^\dagger U_s Q U_s^\dagger v \le
(c-1) \frac{2m}{n} - (c-1) \delta_n.
\]
We have used here that $v^\dagger A v = v^\dagger D v = 2m/n$, which is equal to the sum of all entries of respectively $A$ and $D$ divided by $n$ due to the special form of $v$, and that $w^\dagger U_s Q U_s^\dagger w \ge \lambda_{\min}(Q)=\delta_n$.  This inequality follows from \cite[Problem I.6.15]{bhatia} since $U_s^\dagger w$ is a unit vector, which is not necessarily an eigenvector of $Q$ corresponding to the eigenvalue $\delta_n$.

\section{Performance of the bounds}\label{sec:performance}

We can derive several known bounds by using various properties of Laplacian and signless Laplacian eigenvalues, which are for example proved in section 3.9 of Brouwer and Haemers \cite{BH12}.  In particular we use that $\delta_i\ge 2\mu_i$ and $\theta_1\le n$ for all graphs.

For example:
\[
\chi \ge
1 + \frac{\mu_1}{\mu_1 - \delta_1 + \theta_1} \ge
1 + \frac{\delta_1}{2\theta_1 - \delta_1} \ge
1 + \frac{\delta_1}{2n-\delta_1} \ge
1 + \frac{\mu_1}{n-\mu_1}.
\]
The second bound in this chain is inequality~3.17 in Kolotilina \cite{Kolotilina}; the third bound is due Hansen and Lucas \cite{HL}; and the fourth bound is due to Cvetkovic \cite{Cvetkovic72}.

Wilf \cite{Wilf86} proved that Cvetkovic's bound is in fact a lower bound for the clique number and recently He, Jin and Zhang \cite{HJZ} and Abreu and Nikiforov (in a paper entitled ``Clique number and the signless Laplacian'' which has been submitted for publication) proved that Hansen and Lucas's bound is also a lower bound for the clique number.

The bounds (\ref{eq:Hoffman}) to (\ref{eq:Kolo2}) are, of course, not lower bounds for the clique number as evidenced for example by the triangle-free
Gr\"otzsch graph.

\subsection{Extremal graphs}

Nikiforov \cite{Nikiforov07} has demonstrated that bound (\ref{eq:Niki}) is exact if and only if every two color classes of a graph induce a regular bipartite graph of degree $-\mu_n$. The other bounds in Theorem~\ref{thm:bounds} are exact for complete graphs, for complete regular multipartite graphs and for all bipartite graphs, because the spectra of $L$ and $Q$ are identical for all bipartite graphs.
Bounds (\ref{eq:Niki}) to (\ref{eq:Kolo2}) are equal to Hoffman's bound for regular graphs, and therefore are exact for all regular graphs for which Hoffman's bound is exact. A coloring for which Hoffman's bound is exact is called a Hoffman coloring (see section 3.6 of [4]).

\subsection{Named graphs}

The Wolfram function \texttt{GraphData[n]} generates parameters for named graphs on $n$ vertices. It is useful to compare the following lower bounds for the chromatic number:

\begin{itemize}
\item the Hoffman bound (\ref{eq:Hoffman})
\item the generalization of the Hoffman bound ((\ref{eq:genHof}) with $m > 1$)
\item the normalized bound (\ref{eq:norHoffman})
\item the generalization of the normalized bound ((\ref{eq:norGenHof}) with $m>1$)
\item the Kolotilina bounds (bounds (\ref{eq:Kolo1}) and (\ref{eq:Kolo2}))
\item the generalization of the Kolotilina bounds (bounds (\ref{eq:genKolo1}) and (\ref{eq:genKolo2}) with $m >1$).
\end{itemize}

We have examined Wolfram's named graphs on $16$, $18$, $25$ and $28$ vertices. Based on this limited sample, the results are as follows.

For all regular graphs, bounds (\ref{eq:Kolo1}), (\ref{eq:Kolo2}) and (\ref{eq:norHoffman}) equal the Hoffman bound and for most regular graphs this bound is not improved by setting $m > 1$ in Theorem~\ref{thm:genBounds} and bound (\ref{eq:norGenHof}). There are, however, exceptions. For example, for \texttt{Circulant}(16, (1,7,8)), bounds (\ref{eq:Hoffman}), (\ref{eq:Kolo1}), and (\ref{eq:norHoffman}) equal $2.7$;  bound (\ref{eq:genKolo1}) with $m = 3$ equals $2.8$; but bounds (\ref{eq:genHof}) and (\ref{eq:norGenHof}) with $m = 3$ equals $2.9$. The chromatic number of this graph is $4$.

For irregular graphs, the position is more diverse. There are graphs for which all eight bounds are best, with the normalized bounds being best most frequently.  For example, the \texttt{NoPerfectMatchingGraph} on $16$ vertices has bound (\ref{eq:Hoffman}) equal to $2.5$; bound (\ref{eq:Kolo1}) equal to $2.7$; bound (\ref{eq:genHof}) with $m = 3$ equal to $2.8$; and bound (\ref{eq:genKolo1}) with $m = 3$ equal to $2.9$. The chromatic number of this graph is $4$.   \texttt{Barbell}(8) has bound (\ref{eq:Hoffman}) equal to $4.8$ but bound (\ref{eq:Kolo2}) equal to $7.3$. \texttt{Sun}(8) has bound (\ref{eq:Hoffman}) equal to $4.1$ but bound (\ref{eq:Kolo1}) equal to $5.5$.   \texttt{Windmill(3,6)} has bound (\ref{eq:Kolo1}) equal to $2.1$, bounds (\ref{eq:Hoffman}) and (\ref{eq:Kolo2}) equal to $3.7$ but bound (\ref{eq:norHoffman}) equal to the chromatic number $6$.

Further improvements in bounds for the chromatic number can be achieved by using the left hand inequality of Theorem~\ref{thm:majThm} instead of Theorem~\ref{thm:genBounds}, but at the expense of greater computational effort.  So we can determine the smallest value of $c$ (with the condition $c \ge 2$) that satisfies the inequality:
\[
\sum_{i=1}^m \lambda^\downarrow_i(B - A) \ge \lambda^\downarrow_i(B + A/(c-1))
\]
for each $m$ and select the maximum. So, for example, for \texttt{Sun}(8) this procedure gives $\chi \ge 7$ with $m = 1$.  The result of this procedure is of course always an integer.

\subsection{Random Graphs}

The Wolfram function \texttt{RandomGraph[n,p]} generates a random graph $G_{n,p}$ on $n$ vertices with each edge being present with independent probability $p$. Eigenvalues are found using the function \texttt{Spectrum}, provided the Wolfram package ``Combinatorica'' has been loaded.

Theorem~\ref{thm:genBounds} with $m\ge 2$ almost never exceeds Theorem~\ref{thm:bounds} for random graphs, because for almost all random graphs $\mu_1 >> \mu_2$.
Tabulated below is the performance of bounds (\ref{eq:Kolo1}) and (\ref{eq:Kolo2}) against the Hoffman bound for each combination of $n = 20$ and $50$ and $p = 0.5$, $0.7$ and $0.9$, in each case averaged over $15$ graphs. We have included a comparison with the Bollobas result that the chromatic number of almost every random graph $G_{n,p}$ is:
\[
q = (1/2 + o(1)) n/\log_b(n),
\]
where $b = 1/(1 - p)$.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$n$	& $p$	& Hoffman & Bound~(\ref{eq:Kolo1}) & Bound~(\ref{eq:Kolo2}) & Bollobas \\ \hline \hline
20	& 0.5	& 3.5	    & 3.1	                   & 2.7	                  & 2.3  \\
20	& 0.7	& 4.4	    & 4.1	                   & 3.3	                  & 4.0  \\
20	& 0.9	& 6.5	    & 7.8	                   & 4.7	                  & 7.7  \\
50	& 0.5	& 4.6	    & 4.0	                   & 3.4	                  & 4.4  \\
50	& 0.7	& 6.2     & 5.3	                   & 4.5	                  & 7.7  \\
50	& 0.9	& 10.1    & 9.9	                   & 6.6	                  & 14.7 \\ \hline
\end{tabular}
\end{center}

It can be seen that for $n = 20$ all bounds exceed the Bollobas formula for varying levels of $p$, because for low levels of $n$ the $\mathrm{o}(1)$ term is material. The main conclusion is that bound (\ref{eq:Kolo1}) outperforms the Hoffman bound for smaller, denser random graphs.  On average, bound (\ref{eq:Kolo2}) is consistently less good than bound (\ref{eq:Kolo1}), but for individual graphs bound (\ref{eq:Kolo2}) sometimes exceeds bound (\ref{eq:Kolo1}). Bounds (\ref{eq:Kolo1}) and (\ref{eq:Kolo2}) are sometimes better and sometimes worse than the conjectured lower bound in Wocjan and Elphick \cite{WE}, which involves the sum of the squares of the eigenvalues of the adjacency matrix.

The normalized bound (\ref{eq:norHoffman}) is only occasionally better than the Hoffman bound for random graphs.

\section{Connection to orthogonal representations of graphs}

We now strengthen the statement of Theorem~\ref{thm:conversion}. We show that the parameter $c$ with $c\ge \chi$ can be replaced by $d$ with $d\ge\xi'$, where $\xi'$ is the normalized orthogonal rank of $G$.

Orthogonal representations of graphs have been investigated in \cite{CMNSW07,HPSWM10} in the study of the quantum chromatic number.
A $d$-dimensional orthogonal representation of $G$ is a map $\Psi : V \rightarrow \mathbb{C}^d$, mapping vertices to $d$-dimensional column vectors such that $a_{k\ell}=1$ implies $\langle \Psi_k, \Psi_\ell\rangle = 0$ for $k,\ell\in V$, where $\langle \Psi_k, \Psi_\ell\rangle = \Psi_k^\dagger \Psi_\ell$ denotes the inner product between these two column vectors.

The orthogonal rank of $G$, denoted by $\xi$, is the minimum $d$ such that there exists an orthogonal representation of $G$ in $\mathbb{C}^d$.  Furthermore, let $\xi'$ be the smallest $d$ such that $G$ has an orthogonal representation in the vector space $\mathbb{C}^d$ with the added restriction that the entries of each vector must have modulus one \cite{CMNSW07}.  We refer to these representations as normalized orthogonal representations and to $\xi'$ as the normalized orthogonal rank.

It can be shown that $\xi'\le\chi$ and that there are graphs whose normalized orthogonal rank is strictly smaller than their chromatic number \cite[Subsection 2.4]{WE}.

In the following it is convenient to assume that all the vectors of an orthogonal representation have length $d$.

\begin{lemma}
Let $U_1,\ldots,U_d$ be a collection of diagonal unitary matrices of size $n$ and use the notation
\begin{equation}
U_s=\mathrm{diag}(u_{1,s},\ldots,u_{n,s}) \quad\mbox{for $s=1,\ldots,d$}
\end{equation}
to denote the diagonal entries of the matrices $U_s$.

Then, we have
\begin{equation}\label{eq:annhilate}
\sum_{s=1}^d U_s^\dagger U_s=I \quad\mbox{and}\quad
\sum_{s=1}^d U_s A U_s^\dagger = 0
\end{equation}
if and only if the vectors
\[
\Psi_k = (u_{k,1},\ldots,u_{k,d})^T \quad\mbox{for $k=1,\ldots,n$}
\]
form a normalized orthogonal representation of the graph with adjacency matrix $A$.
\end{lemma}
\begin{proof}
The entry on the left hand side of (\ref{eq:annhilate}) in the $k$th row and $\ell$th column is
equal to
\[
\sum_{s=1}^d \bar{u}_{k,s} \, u_{\ell,s} \, a_{k,\ell} = \langle \Psi_k , \Psi_\ell \rangle \, a_{k,\ell},
\]
where equality follows from the definition of the vectors $\Psi_k$.
\end{proof}

This discussion demonstrates that the lower bounds on the chromatic number in this paper are in fact lower bounds on the normalized orthogonal rank.

\begin{remark}
Note that if we use vectors of an orthogonal representation that is not normalized, then we also obtain $d\ge\xi$ diagonal matrices $D_1,\ldots,D_d$ satisfying the following two properties:
\[
\sum_{s=1}^d D_s^\dagger D_s = I \quad\mbox{and}\quad \sum_{s=1}^d D_s A D_s^\dagger = 0.
\]
In contrast, we may not assume without loss of generality that one of these matrices is equal to the identity matrix and, thus, we cannot convert $A$ to $-A$.  The latter is necessary in order to prove lower bounds on the orthogonal rank with majorization techniques.
\end{remark}

\section{Connection to pinching}

We now prove a general linear-algebraic result that could be of independent interest.

Let $P_1,\ldots,P_c\in\mathbb{C}^{n\times n}$ be a collection of orthogonal projectors such that $\sum_{a=1}^c P_a=I$, where $I$ denotes the identity matrix.  Then, the operation $\mathcal{C} : \mathbb{C}^{n\times n} \rightarrow \mathbb{C}^{n\times n}$ that maps arbitrary matrices $X$ to
\begin{equation}\label{eq:pinching}
\mathcal{C}(X) = \sum_{a=1}^c P_a X P_a
\end{equation}
is called pinching.

\begin{theorem}\label{thm:unitaryPinching}
Let $P_1,\ldots,P_c\in\mathbb{C}^{n\times n}$ be a collection of orthogonal projectors such that $\sum_{a=1}^c P_a=I$, where $I$ denotes the identity matrix.  Then, the corresponding pinching operator $\mathcal{C}$, defined in (\ref{eq:pinching}), can be realized as a convex combination of conjugations with unitary matrices:
\begin{equation}
\mathcal{C}(X) = \frac{1}{c} \sum_{s=1}^c U_s X U_s^\dagger,
\end{equation}
where the unitary matrices $U_s$ are given by
\[
U_s = \sum_{a=1}^c \omega^{a \cdot s} P_a
\]
for $s=1,\ldots,c$.  Here $\omega=e^{2\pi i / c}$ is the $c$th primitive root of unity.
\end{theorem}

\begin{proof}
Write $X=\sum_{a,b=1}^s P_a X P_b$.  Due to linearity it suffices to prove the result for $P_a X P_b$ for fixed $a$ and $b$.  We have
\[
\frac{1}{c} \sum_{s=1}^c U_s P_a X P_b U_s^\dagger = \frac{1}{c} \sum_s \omega^{(a-b)\cdot s} P_a X P_b,
\]
which is equal to $P_a X P_a$ if $a=b$ and the zero matrix otherwise.
\end{proof}

Combining the above result with majorization, we obtain:

\begin{cor}Let $X\in\mathbb{C}^{n\times n}$ be an arbitrary Hermitian matrix.
Then, for all $m=1,\ldots,n$
\[
\sum_{i=1}^m \lambda^\downarrow_i(X) \ge \sum_{i=1}^m \lambda^\downarrow_i\left(  \frac{c}{c-1} \mathcal{C}(X) - \frac{1}{c-1} X \right).
\]
\end{cor}
Observe that this corollary encompasses Theorem~\ref{thm:majThm}, which is recovered as follows. For $s=1,\ldots,c$, define $P_s$ to be the projector onto the subspace $\{ e_k \mid k \in V_s \}$ where $e_k$ denotes the $k$th standard basis vector of $\mathbb{C}^n$, $V=V_1\dot{\cup}\ldots\dot{\cup} V_c$ is the partition defining the coloring of the matrix $A$ in Theorem~\ref{thm:majThm}, and $B$ is an arbitrary diagonal matrix.  The above corollary now yields the statement of Theorem~\ref{thm:majThm} if we set $X=B-A$ since then $\mathcal{C}(X)=B$.

Besides introducing the new spectral bounds (\ref{eq:Kolo1}) and (\ref{eq:Kolo2}), Kolotolina proved results in \cite{Kolotilina}, which imply that the diagonal matrix $B$ in Theorem~\ref{thm:majThm} can be replaced by any block-diagonal matrix $B$ that is consistent with the coloring.  Note that the above corollary also encompasses this generalization.

\section{Conclusions}

In this paper, we have generalized an eigenvalue inequality due to Nikiforov. This enables several lower bounds for the chromatic number to be generalized to encompass all eigenvalues of the adjacency, Laplacian and signless Laplacian matrices, which for some graphs improves their performance.  We have also derived a new bound using the normalized adjacency matrix, which often performs better than any of the un-normalized bounds.

We have also discussed lower bounds for the clique number which are not lower bounds for the chromatic number. These bounds cannot be generalized in an equivalent way, because for example, the bound due to He et al. \cite{HJZ} would monotonically increase to $n/(n - m)$.

The proof of Theorem~\ref{thm:majThm} is straightforward because of the power of combining Theorem~\ref{thm:conversion} with majorization, and because the proof uses graph matrices rather than the eigenvectors of these matrices. Perhaps it is possible to also derive upper bounds for the chromatic number using Theorem~\ref{thm:conversion}.

Our proof that the minimum number of diagonal unitary matrices that can be used to convert the adjacency matrix into the zero matrix is the normalized orthogonal rank, may enable results to be proved about the normalized orthogonal rank that could not be proved about the chromatic number.

\section*{Acknowledgements}
The results in this paper build on the foundations laid by Nikiforov in his 2007 paper and on Kolotolina's extensions of the Nikiforov hybrid bound in her 2010 paper.
We would like to thank Vladimir Nikiforov, in private correspondance, for helpful discussions, leading to the simple derivation of the lower bounds on the chromatic number in Theorem~\ref{thm:bounds} based on Theorem~\ref{thm:Niki} and Corollary~\ref{cor}.

P.W. gratefully acknowledges the support from the National Science Foundation CAREER Award CCF-0746600.  This work was supported in part by the National Science Foundation Science and Technology Center for Science of Information, under grant CCF-0939370.

\bibliographystyle{amsplain}