% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P16}{20(2)}{2013} % 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{thm}{Theorem} \newtheorem{lem}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{pro}[thm]{Proposition} %\newtheorem{rem}[thm]{Remark} %\newtheorem{observation}[theorem]{Observation} %\newtheorem{claim}[theorem]{Claim} \newtheorem{prerem}[thm]{{\bf Remark}} %\renewcommand{\thepreremark}{{\arabic{preremark}}} \newenvironment{rem}{\begin{prerem}\em{\hspace{-0.5 em}}}{\end{prerem}} \newcommand{\noi}{\noindent} \newcommand{\te}{\theta} \newcommand{\x}{{\bf x}} \newcommand{\w}{{\bf w}} \newcommand{\g}{\geqslant} \newcommand{\lee}{\leqslant} \newcommand{\p}{{\bf p}} \newcommand{\e}{{\bf e}} \newcommand{\B}{{\cal B}} \newcommand{\C}{{\cal C}} \newcommand{\D}{{\cal D}} \newcommand{\la}{\lambda} \newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\vf}{\varphi} \newcommand{\tr}{{\rm tr}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{\bf On optimality of designs with\\ three distinct eigenvalues} \author{M.R. Faghihi$^1$\quad E. Ghorbani$^{2,3,}$\thanks{Corresponding author, email: {\tt e\_ghorbani@ipm.ir}} \quad G.B. Khosrovshahi$^3$\quad S. Tat$^1$\\[.3cm] {\small $^1$Department of Statistics, Shahid Beheshti University, Tehran, Iran} \\ {\small $^2$Department of Mathematics, K.N. Toosi University of Technology, }\\ {\small P.O. Box 16315-1618, Tehran, Iran} \\ {\small $^3$School of Mathematics, Institute for Research in Fundamental Sciences (IPM),}\\ {\small P.O. Box 19395-5746, Tehran, Iran }} \date{\dateline{Sep 14, 2012}{Apr 15, 2013}{Apr 24, 2013}\\ \small Mathematics Subject Classifications: 05C50, 62K05, 90C30} \begin{document} \maketitle \begin{abstract} %Consider a design $d=(X,\B)$ where $X$ is a $v$-set of treatments and $\B$ is a collection of $k$-subsets (blocks) of $X$. %The set of all designs with $v$ treatments, $b$ blocks and block size $k$ is denoted by Let $\D_{v,b,k}$ denote the family of all connected block designs with $v$ treatments and $b$ blocks of size $k$. Let $d\in\D_{v,b,k}$. The replication of a treatment is the number of times it appears in the blocks of $d$. The matrix $C(d)=R(d)-\frac{1}{k}N(d)N(d)^\top$ is called the information matrix of $d$ where $N(d)$ is the incidence matrix of $d$ and $R(d)$ is a diagonal matrix of the replications. Since $d$ is connected, $C(d)$ has $v-1$ nonzero eigenvalues $\mu_1(d),\ldots,\mu_{v-1}(d)$. Let $\D$ be the class of all binary designs of $\D_{v,b,k}$. We prove that if there is a design $d^*\in\D$ such that (i) $C(d^*)$ has three distinct eigenvalues, (ii) $d^*$ minimizes trace of $C(d)^2$ over $d\in\D$, (iii) $d^*$ maximizes the smallest nonzero eigenvalue and the product of the nonzero eigenvalues of $C(d)$ over $d\in\D$, then for all $p>0$, $d^*$ minimizes $\left(\sum_{i=1}^{v-1}\mu_i(d)^{-p}\right)^{1/p}$ over $d\in\D$. In the context of optimal design theory, this means that if there is a design $d^*\in\D$ such that its information matrix has three distinct eigenvalues satisfying the condition (ii) above and that $d^*$ is E- and D-optimal in $\D$, then $d^*$ is $\Phi_p$-optimal in $\D$ for all $p>0$. As an application, we demonstrate the $\Phi_p$-optimality of certain group divisible designs. Our proof is based on the method of KKT conditions in nonlinear programming. \bigskip\noindent \textbf{Keywords:} Optimal designs; Designs with three eigenvalues; D-optimal; E-optimal; $\Phi_p$-optimal; KKT conditions; Group divisible designs \end{abstract} \section{Introduction} For a statistician, a design is a much more general structure than what it means to a combinatorialist. What statisticians consider a design is in fact a more general structure than a hypergraph; the blocks may contain repeated treatments. Statisticians use designs as experimenting schemes and they need to decide which one is better than the other in some sense. Their criterion for this is the general principle that a better design has a smaller variance of estimators \cite{bc}. A design which is the best in this sense is called `optimal'. Usually, statisticians consider three major criteria for optimality: A-optimality, D-optimality, and E-optimality. (The letters A, D, and E stand for `average', `determinant', and `extreme'.) These criteria can be stated in terms of the eigenvalues of certain matrices associated to designs which is discussed in the remaining parts of this introductory remarks. We consider designs in statistical sense which are pairs $(X,\B)$ where $X$ is a $v$-set whose elements are called {\em treatments} and $\B$ is a collection of lists (called {\em blocks}) each consists of $k$ treatments. A design is said to be {\em connected} if for every pair of treatments it is possible to pass from one to the other through a chain of treatments such that any two consecutive treatments in the chain appear in a common block. The set of all connected designs with $v$ treatments, $b$ blocks and block size $k$ is denoted by $\D_{v,b,k}$. Since the blocks of a design are defined as lists, they may contain repeated elements. If the blocks are subsets of $X$, i.e. have no repeated elements, then the design is called {\em binary}. Let $d\in\D_{v,b,k}$. Let $N(d)$ be the $v \times b$ {\em incidence matrix} whose $(i,j)$ entry is the number of times that treatment $i$ occurs in block $j$. Thus the column sums of $N(d)$ are all equal to $k$, the block sizes while the sum $r_i$ of the $i$-th row is the number of times which treatment $i$ occurs overall which is the {\em replication} of $i$. If $d$ binary, then $N(d)$ is a $(0,1)$-matrix. A design is called {\em equireplicate} if all the treatments have equal replications. The {\em concurrence matrix} of $d$ is the $v\times v$ matrix $S(d)=N(d)N(d)^\top$. The diagonal matrix whose diagonal entries are the replication numbers of treatments is denoted by $R(d)$. The matrix $C(d)=R(d)-\frac{1}{k}S(d)$ is called the {\em information matrix} of $d$. It is well known that $C(d)$ is a positive semidefinite matrix and since $d$ is connected, $C(d)$ has exactly one eigenvalue zero. Let $\mu_1(d)\g\cdots\g\mu_{v-1}(d)$ be the nonzero eigenvalues of $C(d)$ which we assume throughout that are ordered decreasingly. The multiset of nonzero eigenvalues of $C(d)$ is called the {\em spectrum} of $C(d)$. If $\mu_1>\cdots>\mu_s$ are distinct nonzero eigenvalues of $C(d)$ with multiplicities $t_1,\ldots,t_s$, respectively, we use the notation $\{\mu_1^{t_1},\ldots,\mu_s^{t_s}\}$ for the spectrum of $C(d)$. Given a class of designs, a design is said to be {\em A-optimal} if it maximizes the harmonic mean of $\mu_1,\ldots,\mu_{v-1}$ in that class. A design is {\em D-optimal} if it maximizes the geometric mean of $\mu_1,\ldots,\mu_{v-1}$. A design is said to be {\em E-optimal} if it maximizes the minimum of the nonzero eigenvalues of $C(d)$. The eigenvalue optimality criteria are generalized by Kiefer \cite{k} to a much more general criterion called {\em $\Phi_p$-optimality}. For any $p>0$, a design is $\Phi_p$-optimal if it minimizes $$\left(\frac{\sum_{i=1}^{v-1}\mu_i^{-p}}{v-1}\right)^\frac{1}{p}.$$ A-optimality corresponds to $p = 1$; the limit as $p\to 0$ gives D-optimality; the limit as $p\to\infty$ gives E-optimality. Cheng \cite{ch78} further generalized the notion of optimality as follows. Let $a$ be a large enough positive number and $f$ be a real valued function defined on the interval $(0,a)$. Suppose that $f$ satisfies the conditions (i) $\lim_{x\to0^+}f(x)=\infty$, (ii) $f'<0$, (iii) $f''>0$, and (iv) $f'''<0$. Then a design $d^*$ is called {\em type 1 optimal} if for any $d$ with the same number of treatments and blocks as $d^*$ and for all functions $f$ satisfying the above properties, we have $$\sum_{i=1}^{v-1}f(\mu_i(d^*))\lee\sum_{i=1}^{v-1}f(\mu_i(d)).$$ The specific functions $f(x)=x^{-p}$ and $f(x)=-\ln x$ give $\Phi_p$-optimality and $D$-optimality, respectively. The notion of universal optimality introduced by Kiefer \cite{k} helps in unifying the various optimality criteria. Let $M_v$ be the set of all $v \times v$ symmetric matrices with zero row and column sums. Consider a function $\Phi:M_v\to\mathbb{R}$ such that \begin{itemize} \item[\rm(i)] $\Phi$ is convex, \item[\rm(ii)] $\Phi(bC)$ is a nonincreasing function of $b\g0$ for any $C\in M_v$, and \item[\rm(iii)] $\Phi$ is invariant under each simultaneous permutation of rows and columns. \end{itemize} A design $d^*$ is said to be {\em universally optimal} over a class of competing designs $\D$ if $d^*\in\D$ and for every function $\Phi$ satisfying the above conditions $\Phi(C(d^*))\lee\Phi(C(d))$ for any $d\in\D$. It can be shown that a design that is universally optimal is also A-, D- and E-optimal. The theory of optimal designs is discussed in details in the recent survey \cite{bc}. In this paper we are interested in the optimality of designs with three distinct eigenvalues, that is designs $d$ for which the information matrix $C(d)$ has three distinct eigenvalues. For equireplicate designs, this is equivalent to say that the concurrence matrix of $d$ has three distinct eigenvalues. The (connected) designs with three distinct eigenvalues are called {\em connected designs with second-order balance} in the statistical literature. R.A. Bailey (see \cite{cam}) raised the question that which designs have three eigenvalues. More specific, it was asked for which equireplicate designs $d$ does the concurrence matrix $S(d)$ have three distinct eigenvalues. This was partially answered in \cite{ds,ds2}. This class of designs include {\em partial geometric designs}. A partial geometric design is defined as a binary equireplicate connected design whose concurrence matrix is a singular matrix with at most three distinct eigenvalues, see \cite{bbs,bss}. The optimality of designs with few eigenvalues has captured the attention of many workers in the field. The following result due to Kiefer \cite{k} provides a sufficient condition for determining a universally optimal design over a class of competing designs $\D$. \begin{thm} {\rm(Kiefer \cite{k})} Suppose a class $\C = \{ C(d) \mid d\in\D\}$ of matrices in $M_v$ contains a $C(d^*)$ for which \begin{itemize} \item[\rm(i)] $C(d^*)$ is completely symmetric, that is its diagonal elements are constant and its off-diagonal elements are constant, and \item[\rm(ii)] $d^*$ maximizes the trace of $C(d)$ over $d\in\D$. \end{itemize} Then $d^*$ is universally optimal over $\D$. In particular, if $\D_{v, b, k}$ contains a BIBD $d^*$, then $d^*$ is universally optimal over $\D_{v, b, k}$. \end{thm} In other words, the Kiefer's result says that if a design $d^*$ maximizes the trace of $C(d)$ over $d\in\D_{v, b, k}$ and the spectrum of $C(d^*)$ is of the form $\{\mu_1^{v-1}\}$, then $d^*$ is universally optimal over $\D_{v, b, k}$. \begin{thm} {\rm(Cheng \cite{ch78})} Suppose $d^*\in\D_{v,b,k}$ satisfies the following properties: \begin{itemize} \item[\rm(i)] $C(d^*)$ has spectrum of the form $\{\mu_1,\mu_2^{v-2}\}$, \item[\rm(ii)] $d^*$ maximizes trace of $C(d)$ over $d\in\D_{v,b,k}$, \item[\rm(iii)] $d^*$ minimizes the trace of $C(d)^2$ over $d\in\D_{v,b,k}$. \end{itemize} Then $d^*$ is type 1 optimal in $\D_{v,b,k}$. \end{thm} \begin{thm}\label{ch} {\rm(Cheng \cite{ch87})} If there is a design $d^*\in\D_{v, b, k}$ such that \begin{itemize} \item[\rm(i)] $C(d^*)$ has spectrum of the form $\{\mu_1^{v-2},\mu_2\}$, \item[\rm(ii)] $d^*$ maximizes trace of $C(d)$ over $d\in\D_{v,b,k}$, \item[\rm(iii)] $d^*$ is $\Phi_p$-optimal for some $p > 0$, \end{itemize} then $d^*$ is $\Phi_q$-optimal for all $0\lee q\lee p$. \end{thm} In the same paper, Cheng also showed that the same result holds if one replace the condition (ii) in Theorem~\ref{ch} by ``(ii)$'$ $d^*$ is D-optimal.'' \begin{thm} {\rm(Jacroux \cite{j})} Suppose $d^*\in\D_{v,b,k}$ satisfies the following properties: \begin{itemize} \item[\rm(i)] $C(d^*)$ has spectrum of the form $\{\mu_1,\mu_2^{v-3},\mu_3\}$, \item[\rm(ii)] $d^*$ minimizes the trace of $C(d)^2$ over $d\in\D_{v,b,k}$, \item[\rm(iii)] $d^*$ is E-optimal. \end{itemize} Then $d^*$ is type 1 optimal in $\D_{v,b,k}$. \end{thm} A design $d^*$ is said to be {\em $M$-optimal} (or {\em Schur-optimal}) in $\D_{v,b,k}$ if for any $d\in\D_{v,b,k}$, the vector of eigenvalues of $C(d)$, ordered decreasingly, majorizes the vector of eigenvalues of $C(d^*)$, that is $$\sum_{i=1}^t\mu_i(d^*)\lee\sum_{i=1}^t\mu_i(d),~~~\hbox{for all $t=1,\ldots,v-1$.}$$ It is known that if $d^*$ is $M$-optimal, then it is optimal with respect to many criteria including type~1 optimality. We note that for a partial geometric design $d$, the replication $r$ is an eigenvalue of $C(d)$ as $S(d)$ is singular. The {\em dual} of a design $d$ with $b$ blocks and $v$ treatments is the design $\overline{d}$ with $v$ blocks, $b$ treatments and $N(\overline{d})=N(d)^\top$. \begin{thm} {\rm(Bagchi and Bagchi \cite{bb})} Suppose $d^*\in\D_{v,b,k}$ is a partial geometric design with replication $r$ and spectrum $\{r^g,\mu^{v-1-g}\}$. If $d^*$ satisfies the following properties \begin{itemize} \item[\rm(i)] $g\lee\frac{(v-1)(k-1)}{r(v-k)}$, \item[\rm(ii)] the dual of $d^*$ is M-optimal in the class of all equireplicate designs of $\D_{b,v,r}$, \end{itemize} then $d^*$ is M-optimal in $\D_{v,b,k}$. \end{thm} For similar results on M-optimality see \cite{bmm}. More results on optimality of designs with few eigenvalues can be found in \cite{b,ch78}. In this paper, we continue this line of research and prove the following theorem. \begin{thm}\label{main} Let $\D$ be the class of all binary designs of $\D_{v,b,k}$. Let $d^*\in\D$ such that $C(d^*)$ has two nonzero distinct eigenvalues. If \begin{itemize} \item[\rm(i)] $d^*$ minimizes the trace of $C(d)^2$ over $d\in\D$, \item[\rm(ii)] $d^*$ is E-optimal in $\D$, \item[\rm(iii)] $d^*$ is D-optimal in $\D$, \end{itemize} then $d^*$ is $\Phi_p$-optimal for all $p>0$ in $\D$. \end{thm} \begin{rem} The referee pointed out that the designs which satisfy the hypotheses of Theorem~\ref{main} seem rather likely to be partially balanced designs with two associate classes and concurrences differing by one (for definition and properties see \cite[Chapter~11]{st}). A related result was proved in \cite{cb} where it was shown that among partially balanced designs with two associate classes and concurrences differing by one those which have a singular concurrence matrix are type 1 optimal within the subclass of all binary equireplicate incomplete designs of $\D_{v,b,k}$. \end{rem} As an application of Theorem~\ref{main}, we demonstrate the $\Phi_p$-optimality of certain group divisible designs. Group divisible designs are an important class of partially balanced incomplete block designs. These designs have $v$ treatments divided into $m$ groups of $n$ treatments each such that treatments in the same group occur together in $\la_1$ blocks and treatments in different groups occur together in $\la_2$ blocks. Jacroux \cite{j0} showed that group-divisible designs of group size $2$, $k\g3$, and $\la_2=\la_1+1$ or $\la_2=\la_1-1$ (where $\la_1>1$) are D-optimal. These designs have two distinct nonzero eigenvalues, and clearly minimize $\tr(C^2)$. They are also E-optimal. The E-optimality of the former was shown by Takeuchi \cite{t} and the latter by Cheng \cite{ch80}. Hence by Theorem~\ref{main}, they are $\Phi_p$-optimal. We summarize this in the following theorem. \begin{thm} Group-divisible designs of group size $2$, $k\g3$, and $\la_2=\la_1+1$ or $\la_2=\la_1-1$ (where $\la_1>1$) are $\Phi_p$-optimal for all $p>0$. \end{thm} Another application of Theorem~\ref{main} concerning the optimality of the Petersen graph will be given at the end of Section~3. Theorem~\ref{main} is a consequence of the following general inequality which could be of interest on its own. We recall that for two different designs $d_1,d_2\in\D_{v,b,k}$, it is likely that ${\rm trace}\,C(d_1)\ne{\rm trace}\,C(d_2)$. Nonetheless, for binary designs these are equal, namely for all binary designs $d\in\D_{v,b,k}$, ${\rm trace}\,C(d)=b(k-1)$. \begin{thm}\label{main2} Let $(\te_1,\ldots,\te_n)$ be a vector consisting of two distinct, positive components. If a vector $(x_1,\ldots,x_n)$ of positive components satisfies the conditions \begin{itemize} \item[\rm(i)] $x_1+\cdots+x_n=\te_1+\cdots+\te_n$, \item[\rm(ii)] $x_1^2+\cdots+x_n^2\g \te_1^2+\cdots+\te_n^2$, \item[\rm(iii)] $\min\{x_i \mid i=1,\ldots,n\}\lee\min\{\te_i \mid i=1,\ldots,n\}$, \item[\rm(iv)] $\prod_{i=1}^n x_i \lee \prod_{i=1}^n \te_i $, \end{itemize} then for all $p>0$, $$x_1^{-p}+\cdots+x_n^{-p}\lee \te_1^{-p}+\cdots+\te_n^{-p}.$$ \end{thm} The proof of Theroem~\ref{main2} is based on Karush--Kuhn--Tucker (KKT) conditions from nonlinear programming and shall be presented in Section~3. \section{Karush--Kuhn--Tucker (KKT) conditions} In nonlinear programming, the Karush--Kuhn--Tucker (KKT) conditions are necessary for a local solution to a minimization problem provided that some regularity conditions are satisfied. Allowing inequality constraints, the KKT approach to nonlinear programming generalizes the method of Lagrange multipliers, which allows only equality constraints. For details see \cite{book}. Consider the following optimization problem: \begin{quote} Minimize $f(\x)$\\ subject to:\\ $~~~~~g_i(\x)\lee0$,~ for $i\in I$,\\ $~~~~~h_j(\x)=0$,~ for $j\in J$, \end{quote} where $I$ and $J$ are finite sets of indices. Suppose that the objective function $f:\mathbb{R}^n\to\mathbb{R}$ and the constraint functions $g_i:\mathbb{R}^n\to\mathbb{R}$ and $h_j:\mathbb{R}^n\to\mathbb{R}$ are continuously differentiable at a point $\x^*$. If $\x^*$ is a local minimum that satisfies some regularity conditions, then there exist constants $\nu_i$ and $\la_j$, called KKT multipliers, such that \begin{align*} \nabla f(\x^*)+\sum_{i\in I}&\,\nu_i\nabla g_i(\x^*)+\sum_{j\in J}\la_j\nabla h_j(\x^*)={\bf0}\\ g_i(\x^*)&\lee0,~~~\hbox{for all $i\in I$},\\ h_j(\x^*)&=0,~~~\hbox{for all $j\in J$},\\ \nu_i&\g0,~~~\hbox{for all $i\in I$},\\ \nu_ig_i(\x^*)&=0,~~~\hbox{for all $i\in I$}. \end{align*} In order for a minimum point to satisfy the above KKT conditions, it should satisfy some regularity conditions (or constraint qualifications). The one which suits our problem is the Mangasarian--Fromovitz constraint qualification (MFCQ). Let $I(\x^*)$ be the set of indices of active inequality constraints at $\x^*$, i.e. $I(\x^*)=\left\{i\in I\mid g_i(\x^*)=0\right\}$. We say that MFCQ holds at a feasible point $\x^*$ if the set of gradient vectors $\{\nabla h_j(\x^*)\mid j\in J\}$ is linearly independent and that there exists $\w\in\mathbb{R}^n$ such that \begin{align*} \nabla g_i(\x^*)\w^\top&<0,~~~ \hbox{for all $i\in I(\x^*)$},\\ \nabla h_j(\x^*)\w^\top&=0,~~~ \hbox{for all $j\in J$}. \end{align*} \begin{thm} {\rm(\cite{mf}, see also \cite{book})} If a local minimum $\x^*$ of the function $f(\x)$ subject to the constraints $g_i(\x)\lee0$, for $i\in I$, and $h_j(\x)=0$, for $j\in J$, satisfies MFCQ, then it satisfies the KKT conditions. \end{thm} \section{Proofs} In this section, we prove Theorem~\ref{main2}. We start by stating some results on inequalities. \begin{lem}\label{ben1} {\rm (Bennet \cite{ben})} Suppose that $\al_1,\al_2,\delta_1,\delta_2\g0$, $d_10$ for the rest of the paper and find the global minima of the function $$f(\x):=x_1^{-p}+\cdots+x_n^{-p},~~~ \x=(x_1,\ldots,x_n)\in\mathbb{R}^n$$ subject to the constraints: \begin{align*} g(\x)&:=x_1+\cdots+x_n-m_1\te_1-m_2\te_2=0,\\ h(\x)&:=m_1\te_1^2+m_2\te_2^2-x_1^2-\cdots-x_n^2\lee0,\\ k(\x)&:=x_1\cdots x_n-\te_1^{m_1}\te_2^{m_2}\lee0,\\ l_1(\x)&:=x_1-\te_1\lee0,\\ l_2(\x)&:=\xi-x_1\lee0,\\ m_i(\x)&:=x_1-x_i\lee0,~~\hbox{for $i=2,\ldots,n-1$},\\ n_i(\x)&:=x_i-x_n\lee0,~~\hbox{for $i=2,\ldots,n-1$}. \end{align*} The positive number $\xi$ is chosen small enough so that it satisfies $\xi^{-p}>f(\p)$. Hereafter we suppose that the vector $$\e=(e_1,\ldots,e_n)$$ is a local minimum of the above problem. \begin{lem}\label{mfcq} If $l_2(\e)<0$, then $\e$ satisfies MFCQ. \end{lem} \begin{proof}{With no loss of generality, assume that $e_1\lee e_2\lee\cdots\lee e_n$. We have also $e_1b$. By choosing $\w=(-a,0,\ldots,0,b,\ldots,b,c)$, with $b$ repeated $t-1$ times, we see that for all ${\bf y}$ in $$ \{\nabla h(\e),\nabla k(\e),\nabla l_1(\e)\}\cup\{\nabla m_i(\e)\mid i=2,\ldots,n-1-t \}\cup\{\nabla n_i(\e)\mid i=n-2-t,\ldots,n-1 \} $$ we have ${\bf y}\w^\top<0$. Hence MFCQ conditions are satisfied for $\e$. }\end{proof} \begin{thm}\label{ep} If $\e$ is a global minimum, then it must be a permutation of $\p$. \end{thm} \begin{proof}{Assume that $f(\e)\lee f(\p)$ and $e_1\lee e_2\lee\cdots\lee e_n$. We show that $\e$ must be equal to $\p$. By the choice of $\xi$, $l_2(\e)<0$ and so by Lemma~\ref{mfcq}, $\e$ satisfies KKT conditions, namely \begin{equation}\label{nabla} \nabla f(\e)+\nu\nabla g(\e)+\la\nabla h(\e)+\rho\nabla k(\e)+\sum_{i=1}^2\eta_i\nabla l_i(\e)+ \sum_{i=2}^{n-1}\left(\al_i\nabla m_i(\e)+\be_i\nabla n_i(\e)\right)=0, \end{equation} \begin{align} &~~~~~~~~~~e_1+\cdots+e_n-m_1\te_1-m_2\te_2=0,\\ \la&\g0,~~~\la(m_1\te_1^2+m_2\te_2^2-e_1^2-\cdots-e_9^2)=0,\label{lambda}\\ \rho&\g0,~~~\rho(e_1\cdots e_n-\te_1^{m_1}\te_2^{m_2})=0,\label{prod}\\ \eta_1&\g0,~~~\eta_1(e_1-\te_1)=0,\label{eta1}\\ \eta_2&\g0,~~~\eta_2(\xi-e_1)=0,\label{eta3}\\ \al_i&\g0,~~~\al_i(e_1-e_i)=0,~~ \hbox{for $i=2,\ldots,n-1$},\label{alpha}\\ \be_i&\g0,~~~\be_i(e_i-e_n)=0,~~ \hbox{for $i=2,\ldots,n-1$}.\label{beta} \end{align} Since $l_2(\e)<0$, we have $\eta_2=0$. If we let $D=\prod_{i=1}^ne_i$, then (\ref{nabla}) can be written as \begin{align} &-pe_1^{-p-1}+\nu-2\la e_1+\rho\frac{D}{e_1}+\eta_1+\al_2+\cdots+\al_{n-1}=0,\label{e1}\\ &-pe_i^{-p-1}+\nu-2\la e_i+\rho\frac{D}{e_i}-\al_i+\be_i=0,~~ \hbox{for $i=2,\ldots,n-1$},\nonumber\\ &-pe_n^{-p-1}+\nu-2\la e_n+\rho\frac{D}{e_n}-\be_2-\cdots-\be_{n-1}=0.\label{e9} \end{align} Assume that $r$ of $e_i$ are equal to $e_1$, $t$ of $e_i$ are equal to $e_n$, and $s$ of them are between $e_1$ and $e_n$. We consider four cases according to whether $r$ and $t$ are equal to $1$ or not. \noi{\bf Case 1.} $r\g2$ and $t\g2$. We have $e_2=e_1$. This implies that $e_20$ and so by (\ref{lambda}), %\begin{equation}\label{=120} $$re_1^2+te_n^2=m_1\te_1^2+m_2\te_2^2.$$ %\end{equation} Now Lemma~\ref{2eq} implies that $e_1=\te_1$, $e_n=\te_2$, $r=m_1$ and $t=m_2$. Therefore, $\e=\p$. \noi{\bf Case 2.} $r\g2$ and $t=1$. Since $t=1$, by (\ref{beta}), all $\be_i$ are zero. Since $r\g2$, as above, $\eta_1=\al_2=\cdots=\al_{n-1}=0$. It follows that all $e_i$ are zeros of $y(x)$ and so $e_1=\cdots=e_{n-1}$. We have necessarily $e_n\g\te_2$. Now, if $m_2>1$, then by Lemma~\ref{2eq}, we arrive at a contradiction and if $m_2=1$, then $\e=\p$. \noi{\bf Case 3.} $r=1$ and $t\g2$. Since $r=1$, by (\ref{alpha}), all $\al_i$ are zero and from $t\g2$ it follows that $\be_2=\cdots=\be_{n-1}=0$. If $\eta_1=0$, then all $e_i$ admit at most two different values which is only possible when $r=m_1$ and $t=m_2$ as in Case~2. Thus $\eta_1>0$ and so $e_1=\te_1$. The rest of $e_i$ are zeros of $y(x)$ and so they are equal to either $e_2$ or $e_n$. Clearly $e_2>\te_1$. From lemma~\ref{2eq} it follows that $e_n > \te_2$. Now we apply Lemma~\ref{ben2} with the function $\vf(x)=\ln x$. It turns out that $e_1\cdots e_n>\te_1^{m_1}\te_2^{m_2}$, a contradiction. \noi{\bf Case 4.} $r=t=1$. As above, we have all $\al_i$ and $\be_i$ equal to zero and so all of $e_2,\ldots,e_{n}$ are zeros of $y(x)$. From (\ref{e1}) it is clear that $y(e_1)\lee0$. So if we denote the zeros of $y(x)$ by $y_1$ and $y_2$ with $y_1\lee y_2$, then we have $e_10$ implying that $e_1=\te_1$. This yields the same result as in Case~3. Consequently, we found that all the cases lead to a contradiction except for the case $r=m_1$ and $t=m_2$ which in turn implies that $\e=\p$. The proof is now complete. }\end{proof} \noi{\bf Example.} The celebrated Petersen graph has many fascinating properties. Concerning optimality, this distinguished graph shows another interesting and unique character. In \cite{fgkt}, an algorithm is developed which searches for optimal designs within $\D_{v,b,k}$. Implementing that algorithm, we looked for the optimal designs in the family of graphs with 10 vertices and 15 edges. As result, the Petersen graph was pumped out as the A-, D-, and E-optimal design in that family. This was in fact one of our motivations for this work. Now, as a demonstration of Theorem~\ref{main}, we prove the general optimality property that {\em for all $p>0$, the Petersen graph is the unique $\Phi_p$-optimal and also D- and E-optimal graph among all connected simple graphs on $10$ vertices and $15$ edges.} This follows from Theorem~\ref{main} and Proposition~\ref{te} below. Note that, since we restrict to simple graphs, that the Petersen graph minimizes $\tr(C^2)$ is trivial. Meanwhile, the uniqueness of Petersen graph as D- and E-optimal design is concluded from the equality cases of Proposition~\ref{te}. (We remark that the E-optimality of Petersen graph is a special case of Theorem~3.3 of \cite{ch2012}. Nonetheless we include the short reasoning for the sake of completeness.) In passing we mention that in the case of graphs, the information matrix is half its Laplacian matrix so one can consider the eigenvalues of Laplacian matrix for studying optimality. Recall that the Laplacian eigenvalues of Petersen graph are $\{5^4,2^5,0\}$. The Petersen graph is also uniquely determined by its Laplacian eigenvalues. \begin{pro}\label{te} Let $G$ be a connected graph with $10$ vertices, $15$ edges, and denote the eigenvalues of Laplacian matrix of $G$ by $\mu_1\g\cdots\g\mu_9>\mu_{10}=0$. Then \begin{itemize} \item[\rm(i)] $\mu_9\lee2$ and the equality holds only for Petersen graph, %\item[\rm(ii)] $\sum_{i=1}^{10}\mu_i^2\g120$, \item[\rm(ii)] $\prod_{i=1}^9\mu_i\lee2\cdot10^4$ and the equality holds only for Petersen graph. \end{itemize} \end{pro} \begin{proof}{Let $d_1\g\cdots\g d_{10}$ be the degree sequence of $G$. It is known that for non-complete graphs, the smallest nonzero eigenvalue of Laplacian does not exceed the minimum degree (see, e.g., \cite[p.~198]{crs}). Hence $\mu_9\lee d_{10}$. It follows that if $G$ is not regular, then $\mu_9\lee2$. So we may assume that $G$ is regular. It is a well known fact that there are exactly 21 3-regular graphs on 10 vertices out of which 19 are connected. By inspecting the table of spectra of small graphs \cite{cds}, one can verify that the 19 3-regular graphs on 10 vertices satisfy (i). % To prove (ii), let $L$ and $A$ be the Laplacian and adjacency matrix of $G$. Then, %\begin{align*} % \sum_{i=1}^{10}\mu_i^2&=\tr(L^2)=\tr(A^2)+\sum_{i=1}^{10}d_i^2\\ % &\g30+\frac{1}{10}\left(\sum_{i=1}^{10}d_i\right)^2=120. %\end{align*} There are exactly $112,618$ connected graphs on 10 vertices and 15 edges which can be extracted from the McKay's database on small graphs \cite{mc}. By a simple computation one can verify (ii) and also the equality case of (i). }\end{proof} \subsection*{Acknowledgments} We thank the referee for several fruitful comments. The research of the second author was in part supported by a grant from IPM (No. 91050114). \begin{thebibliography}{99} \bibitem{b} S. Bagchi, On the optimality of a class of designs with three concurrences, {\em Linear Algebra Appl.} {\bf417} (2006), 8--30. \bibitem{bb} B. Bagchi and S. Bagchi, Optimality of partial geometric designs, {\em Ann. Statist.} {\bf29} (2001), 577--594. \bibitem{bc} R.A. Bailey and P.J. Cameron, Combinatorics of optimal designs, in: {\em Surveys in Combinatorics 2009} (ed. S. Huczynska, J.D. Mitchell, and C.M. Roney-Dougal), London Math. Soc. Lecture Notes 365, Cambridge University Press 2009, pp. 19--73. \bibitem{bmm} R.A. Bailey, H. Monod, and J. P. Morgan, Construction and optimality of affine-resolvable designs, {\em Biometrika} {\bf82} (1995), 187--200. \bibitem{ben} G. Bennett, Meaningful sequences and the theory of majorization, {\em Houston J. Math.} {\bf35} (2009), 573--589. \bibitem{bbs} R.C. Bose, W.G. Bridges, and M.S. Shrikhande, Partial geometric designs and two-class partially balanced designs, {\em Discrete Math.} {\bf21} (1978), 97--101. \bibitem{bss} R.C. Bose, S.S. Shrikhande, and N.M. Singhi, Edge regular multigraphs and partial geometric designs with an application to the embedding of quasi-regular designs, in: {\em Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo I}, 49--81. Atti dei Convegni Lincei, 17, Accad. Naz. Lincei, Rome, 1976. \bibitem{cam} P.J. Cameron, Research problems from the 19th British Combinatorial Conference, {\em Discrete Math.} {\bf293} (2005), 313--320. \bibitem{ch78} C.-S. Cheng, Optimality of certain asymmetrical experimental designs, {\em Ann. Statist.} {\bf6} (1978), 1239--1261. \bibitem{ch80} C.-S. Cheng, On the E-optimality of some block designs, {\em J. Roy. Statist. Soc. Ser. B} {\bf42} (1980), 199--204. \bibitem{ch87} C.-S. Cheng, An optimization problem with applications to optimal design theory, {\em Ann. Statist.} {\bf15} (1987), 712--723. \bibitem{ch2012} C.-S. Cheng, A note on the E-optimality of regular line graph designs, {\em J. Stat. Theory Pract.} {\bf6} (2012), 162--168. \bibitem{cb} C.-S. Cheng and R.A. Bailey, Optimality of some two-associate-class partially balanced incomplete block designs, {\em Ann. Statist.} {\bf19} (1991), 1667--1671. \bibitem{cds} D.M. Cvetkovi\'c, M. Doob, and H. Sachs, {\em Spectra of Graphs, Theory and Applications}, Third Edition, Johann Ambrosius Barth, Heidelberg, 1995. \bibitem{crs} D.M. Cvetkovi\'c, P. Rowlinson, and S.K. Simi\'c, {\em An Introduction to the Theory of Graph Spectra}, Cambridge University Press, Cambridge, 2010. \bibitem{ds} E.R. van Dam and E. Spence, Combinatorial designs with two singular values---I: uniform multiplicative designs, {\em J. Combin. Theory Ser. A} {\bf107} (2004), 127--142. \bibitem{ds2} E.R. van Dam and E. Spence, Combinatorial designs with two singular values II. Partial geometric designs, {\em Linear Algebra Appl.} {\bf396} (2005), 303--316. \bibitem{fgkt} M.R. Faghihi, E. Ghorbani, G.B. Khosrovshahi, and S. Tat, On $\Phi_{p}$-optimality of incomplete block designs: An algorithm, submitted. \bibitem{k} J. Kiefer, Construction and optimality of generalized Youden designs, in: {\em A Survey of Statistical Design and Linear Models} (ed. J.N. Srivastava), North-Holland, Amsterdam (1975), pp. 333--353. \bibitem{j0} M. Jacroux, On the D-optimality of group divisible designs, {\em J. Statist. Plann. Inference} {\bf9} (1984), 119--129. \bibitem{j} M. Jacroux, Some sufficient conditions for the type 1 optimality of block designs, {\em J. Statist. Plann. Inference} {\bf11} (1985), 385--396. \bibitem{mf} O.L. Mangasarian and S. Fromovitz, The Fritz John necessary optimality conditions in the presence of equality and inequality constraints, {\em J. Math. Anal. Appl.} {\bf17} (1967), 37--47. \bibitem{mc} B. McKay, Combinatorial Data, {\tt http://cs.anu.edu.au/{\small$\sim$}bdm/data/}. \bibitem{book} J. Nocedal and S.J. Wright, {\em Numerical Optimization}, Second Edition, Springer, New York, 2006. \bibitem{st} A.P. Street and D.J. Street, {\em Combinatorics of Experimental Design}, Clarendon Press, Oxford, 1987. \bibitem{t} K. Takeuchi, On the optimality of certain type of PBIB designs, {\em Rep. Statist. Appl. Res. Un. Japan. Sci. Engrs.} {\bf8} (1961), 140--145. \end{thebibliography} \end{document}