\documentclass[12pt]{article} \usepackage{epsfig,rotating} \usepackage{doublespace,cite} \usepackage{times,mathptm} %\usepackage{maple2e} \newcommand{\msg}[1]{\par{\bf #1}\par\noindent} \newcommand{\MSE}{\mbox{MSE}} \newcommand{\SIR}{\mbox{SIR}} \newcommand{\TSC}{\mbox{TSC}} \newcommand{\TSCb}{\overline{\mbox{TSC}}} %\newcommand{\pbv}{\mbox{\boldmath{$\bar{p}$}}} %\newcommand{\nv}{\mbox{\boldmath{$n$}}} \newcommand{\pbv}{\bar{\mathbf{p}}} \newcommand{\nv}{\bar{\mathbf{n}}} \newcommand{\wv}{\mathbf{w}} \newcommand{\FIG}[1]{FIGURE~\ref{fig:#1}} \newcommand{\cv}{\mathbf{c}} %\newcommand{\cv}{\mbox{\boldmath{$c$}}} %\newcommand{\uv}{\mbox{\boldmath{$u$}}} %\newcommand{\vv}{\mbox{\boldmath{$v$}}} %\newcommand{\ubv}{\mbox{\boldmath{$\bar{u}$}}} %\newcommand{\vbv}{\mbox{\boldmath{$\bar{v}$}}} \newcommand{\uv}{\mathbf{u}} \newcommand{\vv}{\mathbf{v}} \newcommand{\ubv}{\bar{\mathbf{u}}} \newcommand{\vbv}{\bar{\mathbf{v}}} \newcommand{\equat}[1]{equation~({\ref{eq:#1}})} \newcommand{\Equat}[1]{Equation~({\ref{eq:#1}})} \newcommand{\rv}{\mathbf{r}} \newcommand{\remove}[1]{} \newcommand{\ampersand}{\&} \newcommand{\NCov}{\mathbf{W}} \newcommand{\Gmax}{\Gamma_{\max}} \newcommand{\Gs}{\Gamma} \newcommand{\Gb}{\mathbf{G}} \newcommand{\bb}{\mathbf{b}} \newcommand{\PBav}{\bar{P}_{B}} \newcommand{\lemlabel}[1]{\label{lem:#1}} \newcommand{\lemref}[1]{Lemma~\ref{lem:#1}} \newcommand{\Lemref}[1]{Lemma~\lemref{#1}} \newcommand{\Ccal}{{\cal C}} \newcommand{\Gcal}{{\cal G}} \newcommand{\Ncal}{{\cal N}} \newcommand{\ev}{\mathbf{e}} \newcommand{\sv}{\mathbf{s}} \newcommand{\svo}{\mathbf{\bar{s}}} \newcommand{\cb}{\mathbf{c}} \newcommand{\cvo}{\bar{\mathbf{c}}} \newcommand{\co}{\bar{c}} \newcommand{\so}{{\bar{s}}} \newcommand{\ro}{{\bar{r}}} \newcommand{\rvo}{\mathbf{\bar{r}}} \newcommand{\y}{\mathbf{y}} \newcommand{\zv}{\mathbf{z}} \newcommand{\pv}{\mathbf{p}} \newcommand{\qv}{\mathbf{q}} \newcommand{\xv}{\mathbf{x}} \newcommand{\av}{\mathbf{a}} \newcommand{\fv}{\mathbf{f}} \newcommand{\Qmat}{\mathbf{Q}} \newcommand{\Qmatt}{\mathbf{Q}\mathbf{Q}^\top} \newcommand{\Ximat}{\mathbf{X}} \newcommand{\Bmat}{\mathbf{B}} \newcommand{\Rmat}{\mathbf{R}} \newcommand{\Imat}{\mathbf{I}} \newcommand{\Zmat}{\mathbf{Z}} \newcommand{\Zvo}{\mathbf{\bar{z}}} \newcommand{\Zo}{\bar{z}} \newcommand{\Amat}{\mathbf{A}} \newcommand{\Hmat}{\mathbf{H}} \newcommand{\Fmat}{\mathbf{F}} \newcommand{\Pmat}{\mathbf{P}} \newcommand{\Smatb}{\bar{\mathbf{S}}} \newcommand{\Nmat}{\mathbf{N}} \newcommand{\bphistar}[1]{\bphi^*_{#1}} \newcommand{\lamstar}[1]{\lambda^*_{#1}} \newcommand{\betastar}[1]{\beta^*_{#1}} \newcommand{\Z}[1]{\mathbf{Z}_{#1}} \newcommand{\R}[1]{\mathbf{R}_{#1}} \newcommand{\e}{\mathbf{e}} \newcommand{\s}{\mathbf{s}} \newcommand{\I}{\mathbf{I}} \newcommand{\z}{\mathbf{z}} \newcommand{\p}{\mathbf{p}} \newcommand{\q}{\mathbf{q}} \newcommand{\x}{\mathbf{x}} \newcommand{\Hb}{\mathbf{H}} \newcommand{\ab}{\mathbf{a}} \newcommand{\cc}{\mathbf{c}} \newcommand{\dd}{\mathbf{d}} \newcommand{\Ab}{\mathbf{A}} \newcommand{\f}{\mathbf{f}} \newcommand{\Fb}{\mathbf{F}} \newcommand{\Smat}{\mathbf{S}} \newcommand{\Y}{\mathbf{Y}} \newcommand{\Smatt}{\mathbf{S}\mathbf{S}^\top} \newcommand{\balpha}{\mathbf{\alpha}} \newcommand{\bPsi}{\mathbf{\Psi}} \newcommand{\bpsi}{\mathbf{\psi}} \newcommand{\bchi}{\mathbf{\chi}} \newcommand{\bPhi}{\mathbf{\Phi}} \newcommand{\bphi}{\mathbf{\phi}} \newcommand{\btheta}{\mathbf{\theta}} \newcommand{\bnu}{\mathbf{\nu}} \newtheorem{cor}{Corollary} \newcommand{\corref}[1]{Corollary~\ref{cor:#1}} \newcommand{\Corlabel}[1]{\label{cor:#1}} \newcommand{\Tr}[1]{\mbox{Trace}[ #1 ]} \newcommand{\be}{\begin{equation}} \newcommand{\ee}{\end{equation}} \newcommand{\If}{I^{\rm{FA}}} \newcommand{\Imp}{I^{\rm{MPA}}} \newcommand{\Imd}{I^{\rm{MD}}} \newcommand{\Ild}{I^{\rm{LD}}} \newcommand{\Imc}{I^{\rm{MC}}} \newcommand{\Iml}{I^{\rm{ML}}} \newcommand{\Iq}{\hat{I}^{(q)}} \newcommand{\Imax}{I^{\max}} \newcommand{\Imin}{I^{\min}} \newcommand{\Iconst}[1]{I^{(#1)}} \newcommand{\nmax}[1]{\langle{#1}\rangle\!\max} \newcommand{\nmin}[1]{\langle{#1}\rangle\!\min} \newcommand{\Threequats}[3]{Equations (\ref{eq:#1}), (\ref{eq:#2}) and (\ref{eq:#3})} \newcommand{\threequats}[3]{equations (\ref{eq:#1}), (\ref{eq:#2}) and (\ref{eq:#3})} \newenvironment{minimize}[1]{\begin{array}{rll} \mbox{minimize} & #1 \\ \mbox{subject to} & \begin{array}[t]{ll}}{\end{array}\end{array}} \newenvironment{maximize}[1]{\begin{array}{rll} \mbox{maximize} & #1 \\ \mbox{subject to} & \begin{array}[t]{ll}}{\end{array}\end{array}} \newcommand{\RUaddress}{ \begin{singlespace} \begin{center} WINLAB, Dept. of Electrical and Computer Engineering\\ \small Rutgers University\\ \small 94 Brett Road\\ \small Piscataway NJ 08854-8060\\ \begin{tabular}{ll} email: & {\bf\em crose@winlab.rutgers.edu}\\ \end{tabular} \end{center} \end{singlespace} } \input{texdef} \setstretch{1.2} \textwidth 6.5 in %\textwidth 6.2 in \oddsidemargin 0.0 in \evensidemargin 0.0 in \textheight 9.25 in \topmargin -0.50 in \title{Interference Avoidance, Sum Capacity and Convergence Via Class Warfare} \author{Christopher Rose} \pagestyle{myheadings} \markboth{Rose: Convergence Via Class Warfare}{Rose: Convergence Via Class Warfare} \begin{document} \pagenumbering{roman} \maketitle \RUaddress \begin{center} {\bf Abstract} \end{center} Interference avoidance has been shown to reduce total average interference (TSC) for given ensembles of user signature waveforms (codewords) in a synchronous CDMA system. In all experiments we have conducted, sequential application of interference avoidance produces an optimal codeword set when starting from randomly chosen initial codewords. Here we provide the first formal proof of convergence to optimal codeword ensembles for greedy interference avoidance algorithms augmented by a technique called ``class warfare'' whereby users which reside in more heavily loaded areas of the signal space purposely interfere with the reception of users in less crowded areas. Coordination of deliberate interference by a complete class of aggrieved user is also sometimes necessary. Such ``attacks'' and subsequent codeword adjustment by attacked users are shown to strictly decrease TSC. Along the way we also show, using linear algebra and a variant of stochastic ordering, equivalence between minimization of total square correlation (TSC) and maximization of sum capacity. The existence proof for capacity maximizing (TSC minimizing) codeword sets is the provable convergence to optimal of interference avoidance augmented by class warfare. \newpage \tableofcontents \newpage \pagenumbering{arabic} \section{Introduction} Interference avoidance has been identified as a method to iteratively obtain optimal signature waveforms (codewords) in multiple access systems \cite{allerton98-uy, pr-allerton99,wbe_journal_UY,ruy-vt,RUY_IA}. The notion behind interference avoidance is that each user, with feedback from the receiver, is allowed to adjust its waveform to minimize interference. Empirically speaking, sequential iterative updates by all users always results in a set of codewords which maximize various measures of system capacity \cite{masseyrupf,tse,anantharam} and minimize a measure of mutual interference called the total square correlation (TSC). There are even analytic hints that interference avoidance should always converge to an optimal ensemble \cite{wbe_journal_UY}. Unfortunately, even copious empirical evidence where {\em never} has a suboptimal set been obtained starting from random codewords \cite{allerton98-uy,pr-allerton99,wbe_journal_UY,ruy-vt,RUY_IA} and strong analytic hints are unsettling and hamper work which depends on existence proofs for optimal codeword sets. Therefore, in this paper we modify the basic interference avoidance procedure to include an aggressive component whereby users who reside in a more crowded portion of the signal space deliberately interfere with other users in more sparsely populated dimensions. The procedure, dubbed {\em class warfare}, allows escape from suboptimal minima, and coupled to the finite number of possible fixed point TSC values for greedy interference avoidance, forces convergence to codeword sets which minimize the average mutual interference between codewords. Along the way it will also be shown directly via elementary linear algebra and a variant of stochastic ordering methods that TSC minimization is equivalent to sum capacity maximization, and thereby, that greedy interference avoidance with class warfare achieves signal sets which meet sum capacity bounds. We note that a slightly more compact statement of this equivalence can be obtained by an appeal to matrix majorization theory \cite{majorization,anantharam,pramodcolor}. However, the direct approach presented here is useful in that it can be wholly understood from first principles without collateral references. \section{Greedy Interference Avoidance: a brief review} We assume that user signals can be represented by $N$-vectors $\s_k$ in some arbitrary signal space. The power of each signal vector is defined as $p_k = |\s_k|^2$. Information is carried by corresponding independent zero mean, unit average power $b_k$ and the superposition bathed in some noise process, represented by a noise vector $\wv$. The result is that the received signal vector $\y$ is given by \be \label{eq:received} \y = \Smat \bb + \wv \ee where $\bb$ is the vector of modulations corresponding to each codeword and $\Smat$ has $M$ columns composed of the $\s_k$. The total interference power experienced by user $k$ assuming a simple matched filter receiver is \be \label{eq:intpower} E \left [ \left ( \frac{\s_k^\top}{|\s_k|} \left [ \Smat \bb - \s_k b_k + \wv \right ] \right )^2 \right ] = \frac{\s_k^\top(\Smatt + \NCov - \s_k \s_k^\top) \s_k }{|\s_k|^2} \ee where \be \Smatt = \Smat \Smat^\top = \sum_{k=1}^M \s_k \s_k^\top \ee and $\NCov$ is the covariance matrix of the noise vector $\wv$. \Equat{intpower} suggests that user $k$ could minimize the interference seen at the receiver by choosing $\s_k$ proportional to the eigenvector associated with the minimum eigenvalue of $\Smatt + \NCov - \s_k \s_k^\top$. This simple intuitively pleasing greedy procedure when applied sequentially by all users, results at each iteration in the reduction of a quantity called the total square correlation (TSC) -- a measure of the average interference seen by all users \cite{allerton98-uy,pr-allerton99,wbe_journal_UY,ruy-vt,RUY_IA}: \be \TSC = \Tr{(\Smatt + \NCov)^2} \ee Furthermore, empirically speaking, the fixed point reached by this iterative procedure invariably has the absolute minimum TSC attainable \cite{RUY_IA}. Other procedures have also been shown to reduce TSC \cite{allerton98-uy,wbe_journal_UY}, but here we consider only greedy procedures which reduce interference for each user if at all possible. At any fixed point of the algorithm, each $\s_k$ must obviously be an eigenvector of $\Smatt + \NCov$. Equally obvious, the $\s_k$ associated with different eigenvalues $\lambda_k$ must be orthogonal \cite{strang}. This orthogonality leads to the observation that if $\lambda_I$ is the eigenvalue for $\s_k$ and $\lambda_{II}$ the eigenvalue for $\s_\ell$, $k \ne \ell$, then we must also have $\lambda_I - p_k \le \lambda_{II}$ since otherwise user $k$ could reduce its interference by setting $\s_k=\sqrt{p_k}\s_{\ell}/|\s_{\ell}|$. \section{Convergence Via Class Warfare} It is easily seen that there may exist many such fixed points with differing TSC values. Thus, if we seek to show that greedy interference avoidance can absolutely minimize TSC, we must first provide some means of escape from local minima. Then, since interference avoidance monotonically reduces TSC toward fixed points, if we show that the possible number of fixed point TSC values is finite, eventual convergence to the absolute minimum TSC is unavoidable. To these ends we provide formal escape methods in which users ``attack'' other users by deliberate interference, or artful encroachment on less crowded portions of the signal space. It should be noted that since we assume all user signals are collected at common antennas and it is the reception point which feeds optimal codewords back to users, the notion of unilateral ``attack'' is more a useful analogy than an operational principle. That is, class warfare is more an analytic method to escape suboptimal minima than a distributed algorithmic method of guaranteeing minimum TSC ``in the wild''. Of course, as software radios become more powerful and sophisticated, a useful systems-level paradigm might have semi-autonomous software agents responsible for decoding each user's signal as opposed to the centralized multiuser architectures of today \cite{ieeepc_softrad,seskar,seskar2,hentschel,salkintzis,reichhart}. In such a case, where agents may or may not collaborate directly, a warfare analogy might be more accurate. However, since all previous numerical experiments indicate that interference avoidance algorithms seem to converge without the help of escape methods, even here the point is somewhat moot, and we reiterate that the term class warfare is a conceptual crutch for an analytic method of TSC minimization. \subsection{Pioneers: the devil you know} \label{sect:smallvoice} Assume with no loss of generality that the equilibrium codeword ensemble consists of three known sets $\{\ab_k,\bb_\ell,\cc_j \}$ such that \be \Smatt = \sum_{k=1}^{K_a} \ab_k \ab_k^\top + \sum_{\ell=1}^{K_b} \bb_\ell \bb_\ell^\top + \sum_{j=1}^{M-K_a-K_b} \cc_j \cc_j^\top \ee and $(\NCov + \Smatt) \ab_k = \lambda_I\ab_k$, $(\NCov + \Smatt) \bb_\ell = \lambda_{II}\bb_\ell$ and $(\NCov + \Smatt) \cc_j = \lambda_{j}\cc_j$ with $\lambda_I > \lambda_{II}$ and $\lambda_{j} \ne \lambda_I, \lambda_{II}$. By virtue of their different eigenvalues, codewords of different classes, $\{\ab_k,\bb_\ell,\cc_j \}$, are mutually orthogonal. Finally, since it is possible that the codewords might not span $\Re^N$, we also admit the possibility of a set $\{ \dd_m \}$ of eigenvectors for $(\NCov + \Smatt)$ with cardinality $K_d$ and associated eigenvalues $\lambda_m$ which are themselves mutually orthogonal as well as orthogonal to the codeword sets $\{\ab_k,\bb_\ell,\cc_j \}$. For equal power codewords, each codeword from the set $\{\ab_k\}$ suffers greater interference than each codeword from the set $\{\bb_\ell\}$. For unequal power, we can only say that set $\{\ab_k\}$ is in a more energetic (including the set energy) portion of the signal space than set $\{\bb_\ell\}$. The assumption that the codeword constellation be a fixed point of a greedy interference avoidance algorithm requires $\lambda_I - \lambda_i \le \min_k{|\ab_k|^2}$ where $\lambda_i$ is any other eigenvalue of $\NCov+\Smatt$. We assume a basis set $\{\bphi_i \}$, $i=1,2,\cdots,n_1$, which spans $\{\ab_k\}$ and is orthogonal to $\{\bb_\ell\}$ and $\{\cc_j\}$. Likewise we assume a basis set $\{ \bpsi_j\}$, $j=1,2,\cdots,n_2$, ($n_1+n_2 \le N$) which spans $\{\bb_\ell\}$ and is orthogonal to $\{\ab_k\}$ and $\{\cc_j\}$, and a basis set $\{ \btheta_m \}$, $m=1,2,\cdots,N-n_1-n_2$ which spans both the $\{\cc_j\}$ and $\{\dd_m\}$ and is therefore orthogonal to $\{\ab_k\}$ and $\{\bb_{\ell}\}$. We will later show (\Thmref{partition}) that we can always choose these eigenvector sets as appropriate partitions of the eigenvector set of $\NCov$. But for this case where we assume all codewords are known, we leave $\{\bphi_i \}$, $\{\bpsi_j \}$ and $\{\theta_m \}$ as convenient bases for their respective codeword sets. As a specific example, since all the elements of $\{\ab_k\}$ have the same eigenvalue, $\lambda_I$ (and similarly for $\{\bb_\ell\}$), we can assign with no loss of generality, $\bphi_1= \ab_1/|\ab_1|$ and $\bpsi_1=\bb_1/|\bb_1|$. Now consider a scenario where a single aggrieved user $\ab_1$ with eigenvalue $\lambda_I$ attacks a known user $\bb_1$ with eigenvalue $\lambda_{II}< \lambda_I$. We must have $\lambda_I - \lambda_j \le |\ab_1| = p_1$ where $\lambda_j$ is any eigenvalue of $\NCov + \Smatt$ and therefore $\lambda_I - \lambda_{II} \le p_1$. We assume that $p_1 = 1$ with no loss of generality\footnote{Note that we can always effectively set $|\ab_1| = 1$ by normalizing $\Smatt + \NCov$ with $|\ab_1|^2 = p_1$. Thus, any codeword can be used as $\ab_1$ with $|\ab_1| =1$.} so that $\bphi_1 = \ab_1$. Likewise we assume $\bb_1 = \beta \bpsi_1$ where $|\bb_1^2|= \beta^2$. The aggrieved user $\ab_1$ ``attacks'' user $\bb_1$ by adjusting its codeword to \be \label{eq:attack} \ab_1^\prime = \cos \omega \bphi_1 + \sin \omega \bpsi_1 \ee so that \be \begin{array}{rcl} \ab_1^{\prime} (\ab_1^{\prime})^\top & = & (\cos^2 \omega) \bphi_1\bphi_1^\top + (\sin^2 \omega) \bpsi_1 \bpsi_1^\top + \sin\omega\cos\omega (\bpsi_1\bphi_1^\top+\bphi_1\bpsi_1^\top)\\ & = & (\cos^2 \omega) \bphi_1\bphi_1^\top + (\sin^2 \omega)\bpsi_1 \bpsi_1^\top + \frac{1}{2}\sin(2\omega)(\bpsi_1\bphi_1^\top+\bphi_1\bpsi_1^\top) \end{array} \ee for some non-zero $\omega$. User $\bb_1$ will react to this challenge by replacing $\bb_1$ with $\bb_1^\prime$, the new minimum eigenvalue eigenvector. That is, \be (\NCov + \Smatt - \ab_1 \ab_1^\top + \ab_1^\prime (\ab_1^\prime)^\top - \bb_1 \bb_1^\top) \bb_1^\prime = \lambda^* \bb_1^\prime \ee where $\lambda^*$ is the minimum eigenvalue of \be \Gb = \NCov + \Smatt - \ab_1 \ab_1^\top + \ab_1^\prime (\ab_1^\prime)^\top - \bb_1 \bb_1^\top \ee We then note that \be \label{eq:Gb1} \Gb \bphi_i = \lambda_I\bphi_i \ee for $i=2,3,\cdots, n_1$ \be \label{eq:Gb2} \Gb\bpsi_j = \lambda_{II}\bpsi_j \ee for $j=2,3,\cdots, n_2$, and \be \label{eq:Gb3} \Gb\btheta_m = \lambda_{m}\btheta_m \ee for $m=1,2,\cdots, N-n_1-n_2$. We therefore have $N-2$ eigenvectors for $\Gb$. Since $\bphi_1$ and $\bpsi_1$ are orthogonal to these, the remaining two (new) eigenvectors must be linear superpositions of $\bphi_1$ and $\bpsi_1$, $\x = x_1 \bphi_1 + x_2 \bpsi_1$. Depending upon $\omega$, the best new codeword $\bb_1^\prime$ might be one of these two new eigenvectors, or could be another one entirely chosen from \threequats{Gb1}{Gb2}{Gb3}. However, we will restrict our attention to $\bb_1^\prime$ of the form \be \label{eq:bprime} \bb_1^{\prime} = \beta \left [ (\sin \chi) \bphi_1 + (\cos \chi) \bpsi_1 \right ] \ee and note that a potentially better choice might exist. That is, by showing suitable selection of $\chi$ in \equat{bprime} can strictly reduce TSC, we will have also shown that a better response to attack can only decrease TSC even more. With $\bb_1^\prime$ as in \equat{bprime} we then have \be \begin{array}{rcl} \bb_1^{\prime} (\bb_1^{\prime})^\top & = & \beta^2 \left [ (\sin^2 \chi) \bphi_1\bphi_1^\top + (\cos^2 \chi) \bpsi_1 \bpsi_1^\top + \sin\chi\cos\chi (\bpsi_1\bphi_1^\top+\bphi_1\bpsi_1^\top) \right ]\\ & = & \beta^2 \left [ (\sin^2 \chi) \bphi_1\bphi_1^\top + (\cos^2 \chi )\bpsi_1 \bpsi_1^\top + \frac{1}{2}\sin(2\chi)(\bpsi_1\bphi_1^\top+\bphi_1\bpsi_1^\top) \right ]\\ \end{array} \ee Now we calculate the difference in TSC after the attack and response, \be \Delta = \Tr{ (\Smatt + \NCov)^2 } - \Tr{ (\Gb + \bb_1^{\prime} (\bb_1^{\prime})^\top)^2} \ee Making the required substitutions and defining \be \label{eq:Qmatdef} \begin{array}{rcl} \Qmat(\omega,\chi) & = & \ab_1^{\prime}(\omega) (\ab_1^{\prime}(\omega))^\top - \ab_1\ab_1^\top + \bb_1^{\prime}(\chi) (\bb_1^{\prime}(\chi))^\top - \bb_1\bb_1^\top\\ & = & -(\sin^2 \omega) \bphi_1\bphi_1^\top + (\sin^2 \omega) \bpsi_1 \bpsi_1^\top + \frac{1}{2}\sin(2\omega)(\bpsi_1\bphi_1^\top+\bphi_1\bpsi_1^\top)\\ & + & \beta^2 \left [ (\sin^2 \chi) \bphi_1\bphi_1^\top - (\sin^2 \chi )\bpsi_1 \bpsi_1^\top + \frac{1}{2}\sin(2\chi)(\bpsi_1\bphi_1^\top+\bphi_1\bpsi_1^\top) \right ]\\ & = & - [\sin^2 \omega - \beta^2\sin^2 \chi ]\bphi_1\bphi_1^\top + [\sin^2 \omega - \beta^2 \sin^2 \chi] \bpsi_1 \bpsi_1^\top\\ & + & \frac{1}{2}[\sin(2\omega) + \beta^2 \sin(2\chi)] (\bpsi_1\bphi_1^\top+\bphi_1\bpsi_1^\top)\\ \end{array} \ee we obtain \be \label{eq:deltaonevoice} \begin{array}{rcl} \Delta (\omega,\chi) & = & \Tr{(\Smatt + \NCov)^2} - \Tr{ ( (\Smatt + \NCov) + \Qmat(\omega,\chi))^2 } \\ & = & -2 \Tr{ (\Smatt + \NCov)\Qmat(\omega,\chi)} - \Tr{ \Qmat(\omega,\chi)\Qmat(\omega,\chi)}\\ \end{array} \ee Performing the indicated substitution and remembering that $(\Smatt + \NCov) \bphi = \lambda_I \bphi$ and $(\Smatt + \NCov) \bpsi = \lambda_{II} \bpsi$ yields \be \label{eq:Delta1} \begin{array}{rcl} \frac{1}{2}\Delta (\omega,\chi) & = & \delta(\sin^2\omega - \beta^2 \sin^2 \chi) - [\sin^2 \omega - \beta^2\sin^2 \chi ]^2 - \frac{1}{4}[\sin(2\omega) + \beta^2 \sin(2\chi)]^2\\ \end{array} \ee where $\delta = \lambda_I - \lambda_{II}$. We note that $0 < \delta \le 1$. We need to determine whether $\Delta > 0$ for some choices of $\omega$. However, we first note that for any given $\omega$, the response $\bb_1^\prime(\chi)$ to the attack by $\ab_1^\prime(\omega)$ will maximize $\Delta$ \cite{RUY_IA}. Therefore, we first seek the maximizing $\chi$ for \equat{Delta1}. Algebraic manipulations and trigonometric identities applied to \equat{Delta1} yield,\footnote{A derivation is provided in Appendix \ref{app:deltasimp1}, although the interested reader might simply compare \equat{Delta1} and \equat{Delta2} with a symbolic mathematics program such as Maple\copyright.} \be \label{eq:Delta2} \begin{array}{rcl} \frac{1}{2}\Delta (\omega,\chi) & = & (\delta-(1-\beta^2))\sin^2\omega - \frac{1}{2}\beta^2(\delta+\beta^2)\\ & + & \frac{1}{2}\beta^2 \left [ (\delta - (1-\beta^2)) \cos(2\chi) + \cos(2\chi+2\omega) \right ]\\ \end{array} \ee We then note that $A \cos 2x + B \cos(2x+2\omega)$ has extremal values $\pm \sqrt { (A + B\cos2\omega)^2 + B^2 \sin^2 2\omega}$. Therefore letting $\Gamma = \delta +\beta^2$ we have for $A = \Gamma -1$ and $B=1$, \be \label{eq:ineq1} \begin{array}{rcl} {\displaystyle \max_{\chi}} \frac{1}{2}\Delta (\omega,\chi) & = & (\Gamma-1) \sin^2 \omega \\ & - & \frac{1}{2}(\Gamma-\delta) \Gamma \left [ 1 -\sqrt{ 1 - 4\frac{\Gamma-1}{\Gamma^2} \sin^2 \omega} \right ] \end{array} \ee We then note that $\Delta(\omega,\chi) > 0$ relies on having $\Gamma - 1 > 0$ which in turn implies $\Gamma - \delta > 0$ since $\delta \le 1$. Thus, the positivity of \equat{ineq1} rests on whether $\exists \omega$ such that \be \label{eq:ineq2} (\Gamma-1) \sin^2 \omega > \frac{1}{2}(\Gamma-\delta) \Gamma \left [ 1 -\sqrt{ 1 - 4\frac{\Gamma-1}{\Gamma^2} \sin^2 \omega} \right ] \ee and we note that the term inside the radical is non-negative so that the right hand side of \equat{ineq2} is non-negative. Rearranging we have \be \label{eq:ineq3} 1 - 2 \frac{\Gamma - 1}{\Gamma - \delta} \frac{1}{\Gamma} \sin^2 \omega < \sqrt{ 1 - 4\frac{\Gamma-1}{\Gamma^2} \sin^2 \omega} \ee and we again note that since the term inside the radical is non-negative ($4(\Gamma-1)\sin^2\omega/\Gamma^2 \le 1 $) that the left hand side of \equat{ineq3} is non-negative as well. So, squaring both sides and simplifying leads to \be \frac{\Gamma - 1}{\Gamma - \delta} \sin^2 \omega < \delta \ee which is true for some small enough $\omega$ so long as $\delta > 0$. Thus, \be \label{eq:onevoicebound2} \delta > 0 \ee and \be \label{eq:onevoicebound} \Gamma - 1 = \delta - (1-\beta^2) > 0 \ee suffice for the existence of an $\omega$ such that $\Delta(\omega,\chi) >0$. We summarize and generalize the result as a theorem: \begin{theorem}{\thmlabel{onevoicebound3}} Suppose a single user with codeword power $\alpha^2$ and eigenvalue $\lambda_I$ attacks another user with codeword power $\beta^2$ and eigenvalue $\lambda_{II} < \lambda_{I}$ by adjusting its codeword according to \equat{attack}. Further suppose that the attacked user responds by adjusting its codeword to obtain the maximum possible SINR. Then there exists an attack parameter $\omega$ that will be successful in {\em strictly} reducing TSC if $\delta = \lambda_I - \lambda_{II}> 0$ and $\delta > \alpha^2 - \beta^2$. \end{theorem} This result is intuitively pleasing since it makes little sense to engage in warfare if at best what you gain ($\lambda_{II}-\beta^2$) is no better than what you already have ($\lambda_{I} - \alpha^2$). Reworking these two expressions leads directly to $\beta^2 > \alpha^2-\delta$. Another looser but more memorable condition can be had by noting that since $\delta > 0$, any $\beta ^2 \ge \alpha^2$ allows $\Delta(\omega,\chi) > 0$. Since $\beta^2 =\alpha^2$ implies equal power aggrieved and offending users, $\beta^2 > \alpha^2$ implies a weaker user attacking a stronger user. Thus, we may say that TSC can always be strictly reduced whenever a less powerful user with associated eigenvalue $\lambda_I$ attacks an equal or more powerful user with associated eigenvalue $\lambda_{II} < \lambda_I$. \subsection{Pioneers: the devil you don't} \label{sect:dimensional} Now suppose that user codewords in one class are unknown to those in another so that a directed attack against a particular user is infeasible. However, if the background noise covariance $\NCov$ is known to all users, then an aggrieved user could measure the signal energy along dimensions (eigenvectors) of the noise covariance and attack specific offending dimensions. We will find the following two theorems useful. The first theorem pertains to the relationship between equilibrium codeword sets and the eigenspace of the noise covariance matrix $\NCov$. \begin{theorem}{\thmlabel{partition}} At equilibrium, codewords with different eigenvalues reside in mutually orthogonal spaces. These spaces are spanned by mutually orthogonal partitions of the eigenvector set for $\NCov$. Furthermore, the eigenvectors of $\NCov$ are also eigenvectors of $\Smatt+\NCov$. \end{theorem} \begin{Proof}{\bf \Thmref{partition}} Consider a set of codewords $\{ \ab_i \}$ with cardinality $m_1$, dimensionality $n_1$ and associated unique eigenvalue $\lambda_a$. Let us then define \be \Smatt = \Amat \Amat^\top + \Zmat \Zmat^\top \ee where \be \Amat\Amat^\top = \sum_{i=1}^{m_1} \ab_i \ab_i^\top \ee and $\Zmat$ is a matrix containing the codewords with eigenvalues other than $\lambda_a$. We then have \be (\Smatt + \NCov) \ab_i = (\Amat \Amat^\top + \Zmat \Zmat^\top + \NCov) \ab_i = (\Amat \Amat^\top + \NCov)\ab_i = \lambda_a \ab_i \ee Now consider vectors $\bphi_m$ in the $N-n_1$-dimensional orthogonal complement of $\{\ab_i \}$. Construct a basis for this set such that \be (\Amat \Amat^\top + \NCov) \bphi_m = \NCov \bphi_m = \lambda_m \bphi_m \ee Since there are exactly $N-n_1$ of these eigenvectors, the remaining $n_1$ eigenvectors $\bphi_i$, $i=1,2,\cdots, n_1$ of $\NCov$ must form the basis for the set $\{\ab_i\}$. Extending this result, we see that for all sets of codeword with the same eigenvalue, there must be an associated set of eigenvectors of $\NCov$ which exactly spans the space of these codewords. Therefore, equilibrium codewords which share different eigenvalues reside in different partitions of the noise covariance signal space. Finally, each of the eigenvectors of $\NCov$ which span the codeword space can be expressed as a suitable linear combination of codewords \be \sum_{i=1}^{m_1} \mu_{ij} \ab_i = \bphi_j \ee $j=1,2,\cdots,n_1$. Therefore, since $(\Smatt + \NCov)\s_k = \lambda_a \s_k$ we also have $(\Smatt + \NCov)\bphi_j = \lambda_a \bphi_j$ and all the $\bphi_j$ are eigenvectors of $\Smatt + \NCov$ with eigenvalue $\lambda_a$ which completes the proof. \end{Proof} It is worth mentioning that from this point onward we will express codewords as linear superpositions of the noise covariance eigenvector partition in which they reside as opposed to the arbitrary basis set used in section~\ref{sect:smallvoice}. The next theorem establishes a relationship between the mutual correlations of codewords in a given class and their projections onto a noise covariance eigenvector contained in that class. \begin{theorem}{\thmlabel{zeroterm}} Let $\bphi_i$, $i=1,2,\cdots,N$ be the eigenvectors of $\NCov$ with eigenvalues $\sigma_i$. Assume $\{ \bphi_i \}$, $i=1,2,\cdots,L$ exactly spans the set of codewords $\s_k$, $k=1,2,\cdots,K$ which share the same eigenvalue $\lambda$, $(\Smatt+ \NCov)\s_k = \lambda \s_k$. If we define $\alpha_{k\ell} = \s_k^\top \bphi_{\ell}$, then for $\rho_{ij} = \s_i^\top \s_j$ we must have \be \sum_{j=1}^{K} \alpha_{i\ell} \alpha_{j\ell} \left ( \rho_{ij} - \alpha_{i\ell} \alpha_{j\ell} \right ) = 0 \ee \end{theorem} \begin{Proof}{\bf \Thmref{zeroterm}} By \Thmref{partition} and Mercer's theorem \cite{vantrees} we have \be \Smatt + \NCov = \lambda \sum_{i=1}^L \bphi_i \bphi_i^\top + \sum_{i=L+1}^N \lambda_i \bphi_i \bphi_i^\top \ee where the $\{ \bphi_i \}$ is the complete eigenvector set for $\NCov$. Since the $\{ \s_k \}$, $k=1,2,\cdots,K$ are exactly spanned by the $\bphi_i$, $i=1,2,\cdots,L$ we then have \be \lambda \sum_{i=1}^L \bphi_i \bphi_i^\top = \sum_{k=1}^K \s_k \s_k^\top + \sum_{i=1}^L \sigma_i \bphi_i \bphi_i^\top \ee which implies \be \sum_{k=1}^K \s_k \s_k^\top = \sum_{i=1}^L (\lambda - \sigma_i) \bphi_i \bphi_i^\top \ee We define $E_i = \lambda - \sigma_i$, the codeword energy along eigenvector $\bphi_i$ and note that for $\alpha_{ki} = \bphi_{i}^\top \s_k$ we have $E_i = \sum_{k=1}^K \alpha_{ki}^2$. We then have \be \sum_{j=1}^{K} \alpha_{i\ell} \alpha_{j\ell} \left ( \rho_{ij} - \alpha_{i\ell} \alpha_{j\ell} \right ) = \sum_{j=1}^{K} \alpha_{i\ell} \rho_{ij}\alpha_{j\ell} - \alpha_{i\ell}^2 E_{\ell} \ee and note that \be \sum_{j=1}^{K} \alpha_{i\ell} \rho_{ij}\alpha_{j\ell} = \sum_{j=1}^{K} \bphi_{\ell}^\top (\s_i \s_i^\top)(\s_j \s_j^\top) \bphi_{\ell} = \bphi_{\ell}^\top (\s_i \s_i^\top) \left ( \sum_{i=1}^{L} E_i \bphi_i \bphi_i^\top \right ) \bphi_{\ell}^\top = \alpha_{i\ell}^2E_{\ell} \ee which completes the proof. \end{Proof} Now, let ${\cal A}$ be the aggrieved set of codewords with elements $\ab_i$ such that $(\Smatt + \NCov)\ab_i = \lambda_I \ab_i$. We can write \be \ab_i = \alpha_i \bphi_{1} + \x_i \ee where $\bphi_1$ is one of the eigenvectors of $\NCov$ which spans the aggrieved codeword set. We note that $(\Smatt + \NCov) \bphi_1 = \lambda_{I}\bphi_1$, that $\NCov \bphi_1 = \sigma_1\bphi_1$ and that $(\Smatt + \NCov) \x_i = \lambda_{I} \x_i$. Let $\cal S$ be the (non-empty) set of offending codewords with eigenvalue $\lambda_{II} < \lambda_I$. And by \Thmref{partition} let the noise covariance dimension $\bphi_N$ be contained in the span of ${\cal S}$ with $(\Smatt + \NCov)\bphi_N = \lambda_{II} \bphi_N$. For the codewords $\{ \s_i \}$, ${i\in {\cal S}}$ in this set we write \be \s_i = \beta_i \bphi_N + \y_i \ee with $\beta_i = \bphi_N^\top \s_i$. As for $\ab$ we note that $(\Smatt + \NCov) \bphi_N = \lambda_{II}\bphi_N$, that $\NCov \bphi_N = \sigma_N\bphi_N$ and that $(\Smatt + \NCov) \y_i = \lambda_{II} \y_i$. To attack, we rotate each $\ab_i$ into $\bphi_N$ as \be \ab_i^{\prime} = \alpha_i (\cos\omega \bphi_{1} + \sin\omega \bphi_{N}) + \x_i \ee and then script the evasion response by the offending set as \be \s_i^{\prime} = \beta_i (\cos\chi \bphi_N + \sin\chi \bphi_1) + \y_i \ee To calculate the change in TSC we first form \be \ab_i \ab_i^\top = \alpha_i^2 \bphi_1 \bphi_1^\top + \x_i \x_i^\top + \alpha_i(\bphi_1 \x_i^\top + \x_i\bphi_1^\top) \ee and \be \s_i\s_i^\top = \beta_i^2 \bphi_N \bphi_N^\top + \y_i\y_i^\top + \beta_i ( \bphi_N \y_i^\top + \y_i \bphi_N^\top) \ee and then \be \begin{array}{rcl} \ab_i^\prime (\ab_i^\prime)^\top & = & \alpha_i^2 \left [\cos^2\omega \bphi_1 \bphi_1^\top + \sin^2\omega \bphi_N \bphi_N^\top + \cos\omega\sin\omega (\bphi_1 \bphi_N^\top + \bphi_N \bphi_1^\top) \right ]\\ & + & \x_i \x_i^\top + \alpha_i\cos\omega(\bphi_1 \x_i^\top + \x_i\bphi_1^\top) + \alpha_i\sin\omega(\bphi_N \x_i^\top + \x_i\bphi_N^\top)\\ \end{array} \ee and \be \begin{array}{rcl} \s_i^\prime (\s_i^\prime)^\top & = & \beta_i^2 \left [\cos^2\chi \bphi_N \bphi_N^\top + \sin^2\chi \bphi_1 \bphi_1^\top + \cos\chi\sin\chi (\bphi_1 \bphi_N^\top + \bphi_N \bphi_1^\top) \right ]\\ & + & \y_i \y_i^\top + \beta_i\cos\chi(\bphi_N \y_i^\top + \y_i\bphi_N^\top) + \beta_i \sin\chi(\bphi_1 \y_i^\top + \y_i\bphi_1^\top)\\ \end{array} \ee which allows us to write \be \begin{array}{rcl} \ab_i^\prime (\ab_i^\prime)^\top & = & \ab_i\ab_i^\top + \alpha_i^2 \left [ \sin^2\omega \bphi_N \bphi_N^\top -\sin^2\omega \bphi_1 \bphi_1^\top + \cos\omega\sin\omega (\bphi_1 \bphi_N^\top + \bphi_N \bphi_1^\top) \right ]\\ & + & \alpha_i(\cos\omega - 1)(\bphi_1 \x_i^\top + \x_i\bphi_1^\top) + \alpha_i\sin\omega(\bphi_N \x_i^\top + \x_i\bphi_N^\top)\\ \end{array} \ee and \be \begin{array}{rcl} \s_i^\prime (\s_i^\prime)^\top & = & \s_i \s_i^\top + \beta_i^2 \left [ \sin^2\chi \bphi_1 \bphi_1^\top -\sin^2\chi \bphi_N \bphi_N^\top + \cos\chi\sin\chi (\bphi_1 \bphi_N^\top + \bphi_N \bphi_1^\top) \right ]\\ & + & \beta_i(\cos\chi-1)(\bphi_N \y_i^\top + \y_i\bphi_N^\top) + \beta_i \sin\chi(\bphi_1 \y_i^\top + \y_i\bphi_1^\top)\\ \end{array} \ee which in turn allows us to write \be \begin{array}{rcl} \Smat^\prime ( \Smat^\prime)^\top & = & \Smatt + {\displaystyle \sum_{i\in {\cal A}}} \alpha_i^2 \left [ \sin^2\omega \bphi_N \bphi_N^\top -\sin^2\omega \bphi_1 \bphi_1^\top + \cos\omega\sin\omega (\bphi_1 \bphi_N^\top + \bphi_N \bphi_1^\top) \right ]\\ & + & {\displaystyle \sum_{i\in {\cal A}}} \alpha_i(\cos\omega - 1)(\bphi_1 \x_i^\top + \x_i\bphi_1^\top) + {\displaystyle \sum_{i\in {\cal A}}} \alpha_i\sin\omega(\bphi_N \x_i^\top + \x_i\bphi_N^\top)\\ & + & {\displaystyle \sum_{i\in {\cal S}}}\beta_i^2 \left [ \sin^2\chi \bphi_1 \bphi_1^\top -\sin^2\chi \bphi_N \bphi_N^\top + \cos\chi\sin\chi (\bphi_1 \bphi_N^\top + \bphi_N \bphi_1^\top) \right ]\\ & + & {\displaystyle \sum_{i\in {\cal S}}} \beta_i(\cos\chi-1)(\bphi_N \y_i^\top + \y_i\bphi_N^\top) + {\displaystyle \sum_{i\in {\cal S}}} \beta_i \sin\chi(\bphi_1 \y_i^\top + \y_i\bphi_1^\top)\\ \end{array} \ee We then define the total aggrieved codeword energy in $\bphi_1$ as $\alpha^2 = {\displaystyle \sum_{i\in {\cal A}}} \alpha_i^2$, the total offending codeword energy in dimension $\bphi_N$ as $\beta^2 = {\displaystyle \sum_{i\in {\cal S}}} \beta_i^2$ and form $Q(\omega,\chi)$ as in section \ref{sect:smallvoice}; \be \begin{array}{rcl} \Qmat(\omega, \chi) & = & (\alpha^2 \sin^2\omega - \beta^2 \sin^2\chi ) \left ( \bphi_N \bphi_N^\top -\bphi_1 \bphi_1^\top \right )\\ & + & (\alpha^2 \cos\omega\sin\omega + \beta^2 \cos\chi\sin\chi) (\bphi_1 \bphi_N^\top + \bphi_N \bphi_1^\top) \\ & + & {\displaystyle \sum_{i\in {\cal A}}} \alpha_i(\cos\omega - 1)(\bphi_1 \x_i^\top + \x_i\bphi_1^\top) + {\displaystyle \sum_{i\in {\cal A}}} \alpha_i\sin\omega(\bphi_N \x_i^\top + \x_i\bphi_N^\top)\\ & + & {\displaystyle \sum_{i\in {\cal S}}} \beta_i(\cos\chi-1)(\bphi_N \y_i^\top + \y_i\bphi_N^\top) + {\displaystyle \sum_{i\in {\cal S}}} \beta_i \sin\chi(\bphi_1 \y_i^\top + \y_i\bphi_1^\top)\\ \end{array} \ee We then define $\Delta(\omega,\chi)$ as in \equat{deltaonevoice} and reduce it to \be \label{eq:dimensionattack} \begin{array}{rcl} \frac{1}{2}\Delta(\omega,\chi) & = & \delta (\alpha^2 \sin^2 \omega - \beta^2 \sin^2 \chi) - (\alpha^2\sin^2 \omega - \beta^2 \sin^2 \chi)^2 - \frac{1}{4}(\beta^2 \sin 2\chi + \alpha^2 \sin 2\omega)^2 \\ & - & ((\cos\omega-1)^2 + \sin^2\omega) {\displaystyle \sum_{i,j\in {\cal A}}} \alpha_i\alpha_j (\kappa_{ij} - \alpha_i\alpha_j)\\ & - & ((\cos\chi -1)^2 + \sin^2\chi) {\displaystyle \sum_{i,j\in {\cal S}}} \beta_i\beta_j (\rho_{ij} - \beta_i\beta_j) \end{array} \ee where $\kappa_{ij} = \ab_i^\top \ab_j$, $i,j \in {\cal A}$ and $\rho_{ij} = \s_i^\top \s_j$, $i,j \in {\cal S}$. By \Thmref{zeroterm} the terms in $(\cos\omega -1)^2 + \sin^2\omega$ and $(\cos\chi -1)^2 + \sin^2\chi$ must be identically zero so we have \be \label{eq:dimensionattack2} \begin{array}{rcl} \frac{1}{2}\Delta(\omega,\chi) & = & \delta (\alpha^2 \sin^2 \omega - \beta^2 \sin^2 \chi) - (\alpha^2\sin^2 \omega - \beta^2 \sin^2 \chi)^2 - \frac{1}{4}(\beta^2 \sin 2\chi + \alpha^2 \sin 2\omega)^2 \\ & = & \alpha^4 \left [ \frac{\delta}{\alpha^2} (\sin^2 \omega - \frac{\beta^2}{\alpha^2} \sin^2 \chi) - (\sin^2 \omega - \frac{\beta^2}{\alpha^2} \sin^2 \chi)^2 - \frac{1}{4}(\sin 2\omega + \frac{\beta^2}{\alpha^2} \sin 2\chi )^2 \right ] \\ \end{array} \ee \Equat{dimensionattack} is identical to \equat{Delta1} within a factor of $\alpha^4$ if we define $\tilde{\delta} = \delta/\alpha^2$ and $\tilde{\beta} = \beta/\alpha^2$. Therefore the result is identical to that in section \ref{sect:smallvoice}: TSC will be strictly reduced by dimensional attack so long as $\tilde{\delta} >0$ and $\tilde{\delta} > 1 - \tilde{\beta}^2$ which reduces to $\delta > 0$ and $\delta > \alpha^2 - \beta^2$. The only difference is that we have launched a coordinated attack and have ``scripted'' an ensemble response (specifically, a rotation by all offending users from the attacked dimension $\bphi_N$ toward the attacking signal dimension $\bphi_1$) as opposed to assuming individual greedy responses by each codeword. \subsection{Manifest Destiny} \label{sect:manifest} Now suppose that application of greedy interference avoidance has resulted in a fixed point such that there exists an eigenvector $\bpsi$ of $\Smatt + \NCov$ with eigenvalue $\lambda_{II} < \lambda_I$ where $\lambda_I$ is the eigenvalue of one of the user codewords. Further, suppose that no sufficiently powerful codeword (or none at all) resides in the offending dimension $\bpsi$ so that attack and response warfare will be ineffective.\footnote{See Appendix \ref{warfail} for an example.} We will show that in such a case a {\em coordinated migration} into the offending dimension will strictly reduce TSC unless a simple set of conditions is violated. As with dimensional attack assume there exist codewords $\{ \s_i \}$, $i=1,2,\cdots,K$ such that $(\Smatt + \NCov) \s_i = \lambda_I \s_i$ and we assume the codewords occupy $n 0$ for any of the $\omega_i$ nonzero, we can always find a set of suitably small $\{ \omega_i \}$ for which $\Delta(\Omega) > 0$. We summarize the result as a theorem: \begin{theorem}{\thmlabel{manifest}} Let $\{\s_i\}$ be the set of all codewords which share a common eigenvalue $\lambda_I$. Let $\bpsi$ be an eigenvector of $\NCov$ orthogonal to all the $\{ \s_i \}$ and for which $(\Smatt + \NCov)\bpsi = \lambda_{II} \bpsi$ where $\lambda_I - \lambda_{II} = \delta > 0$. TSC can be strictly reduced by coordinated attack on dimension $\bpsi$ if the number of codewords is at least one more than the number of dimensions they span. \end{theorem} We call this ``migration'' strategy {\em manifest destiny} after geographic expansion policies of the $19^{\mbox{th}}$ century United States. \section{Sum Capacity and TSC} \label{sect:equivalence} In \cite{RUY_IA} equivalence between TSC minimization and sum capacity maximization was obtained simply through application of majorization theory \cite{majorization, tse, anantharam}. However, an approach based directly on elementary linear algebra \cite{strang} and a variant of stochastic ordering is also useful and possibly accessible to a wider audience. Specifically, sum capacity maximization and TSC minimization both depend on the eigenvalues of the received signal covariance matrix. The sum capacity function is concave and the TSC convex in these eigenvalues. We establish that both TSC and sum capacity are optimized when identical bounds on the eigenvalues are met with equality thereby establishing an equivalence between TSC minimization and sum capacity maximization. \subsection{Sum Capacity and TSC} We modify the approach in \cite{masseyrupf} to include the nonwhite, possibly correlated Gaussian channel described by \equat{received}. The mutual information between $\Y$ and $\bb$ is \cite{cover} \be I(\Y;\bb) = h(\Y) - h(\Y|\bb) = h(\Y) - h({\wv}) \ee This quantity is upper bounded by assuming that $\Y$ is a Gaussian random vector. Since $\bb$ and ${\wv}$ are assumed zero mean and independent and the components of $b$ are also assumed independent, we have $\mbox{cov}(\Y) = \Smatt + \NCov$ where $\NCov$ is the covariance of the noise vector. This leads directly to \cite{cover,gallagerit} \be \label{sum_cap} C_{\s}=\frac{1}{2}\log \left [ (2 \pi e)^N \left | \Smatt + \NCov \right | \right ] - \frac{1}{2}\log \left [ (2 \pi e)^N \left |\NCov \right | \right ] \ee which reduces to \be \label{sum_cap2} C_{\s}=\frac{1}{2}\log \left | \Smatt + \NCov \right | - \frac{1}{2}\log |\NCov| \ee We then define the eigenvalues of the noise covariance matrix $\NCov$ as $\{ \sigma_i \}$, $i=1,\cdots, N$. Likewise we define the eigenvalues of the matrix $\Smatt + \NCov$ as $\{ \lambda_i \}$, $i=1,\cdots, N$ and obtain the sum capacity in terms of eigenvalues \begin{equation} \label{eq:sumcapeval} C_{\s}= \frac{1}{2} \sum_{i=1}^N \log \lambda_i - \frac{1}{2} \sum_{i=1}^N \log \sigma_i \end{equation} Since the eigenvalues $\{ \sigma_i \}$ are fixed, capacity maximization depends only on the choice of the $\{ \lambda_i\}$. We note that the codeword energies $\{ p_k \}$ are fixed which leads to \be \label{eq:lambda_constraint} \sum_{i=1}^N \lambda_i = \Tr{\NCov + \Smatt} = \sum_{k=1}^M p_k + \sum_{i=1}^N \sigma_i \ee since the trace of a square matrix is identical to the sum of its eigenvalues \cite{strang} and $|\s_k|^2 =p_k$.\footnote{Please note that {\em unlike} \cite{anantharam} and much of the multiuser detection literature, we incorporate the fixed signal power into the signal vector power (i.e., $p_k= |s_k|^2$) for notational simplicity.} The received vector $Y$ has covariance matrix $\Smatt + \NCov$. Thus, the total square correlation \cite{allerton98-uy,wbe_journal_UY,ruy-vt,RUY_IA} is defined as \be \label{eq:tsceval} \TSC = \Tr{(\Smatt + \NCov)^2} = \sum_{i=1}^N \lambda_i^2 \ee where again, the $\{ \lambda_i \}$ are the eigenvalues of $\Smatt + \NCov$ and the sum constraint of \equat{lambda_constraint} still holds. We then note that were we to pursue the constrained optimization \cite{hild,bertlag} of \equat{sumcapeval} and \equat{tsceval}, that the stationary point equations would be virtually identical. Specifically, for the optimization of sum capacity, define the Lagrange multiplier as $\Omega$ and we obtain \be \Gcal_{C}({\mathbf{\lambda}}) = \frac{1}{2} \sum_{i=1}^N \log \lambda_i - \frac{1}{2} \sum_{i=1}^N \log \sigma_i + \Omega \left [ \sum_{i=1}^N \lambda_i - \sum_{k=1}^M p_k - \sum_{i=1}^N \sigma_i \right ] \ee which results after partial differentiation with respect to each $\lambda_i$ in \be \label{eq:lagrange} \frac{\partial \Gcal_{C}({\mathbf{\lambda}})}{\partial \lambda_i} = \frac{1}{2\lambda_i} + \Omega \ee The second partials are negative and the cross partials are zero. Therefore the equality-constrained sum capacity is concave in the $\lambda_i$. Setting \equat{lagrange} to zero yields \be \label{eq:lagrange2} \lambda_i = -\frac{1}{2\Omega} \ee Likewise for TSC we have \be \Gcal_{\TSC}({\mathbf{\lambda}}) = \sum_{i=1}^N \lambda_i^2 + \Xi \left [ \sum_{i=1}^N \lambda_i - \sum_{k=1}^M p_k - \sum_{i=1}^N \sigma_i \right ] \ee Taking partials as before results in \be \label{eq:TSClagrange} \frac{\partial \Gcal_{\TSC}(\mathbf{\lambda})}{\partial \lambda_i} = 2 \lambda_i + \Xi \ee The second partials with respect to the $\lambda_i$ are positive and the cross partials are zero which implies $\Gcal_{\TSC}(\mathbf{\lambda})$ is convex in the $\{\lambda_i\}$. Setting \equat{TSClagrange} to zero yields \be \label{eq:TSClagrange2} 2 \lambda_i + \Xi = 0 \ee which is {\em identical} in form to \equat{lagrange2}. The $\lambda$-{\em constellation} which maximizes and minimizes \equat{lagrange2} and \equat{TSClagrange2} respectively will be identical, depending on the convexity of the $\lambda$-constellation solution space \cite{nemh,hild} -- the classic Kuhn-Tucker conditions. That is, unless the uniform $\lambda_i$ solution implied by the two extremal equations is contained in the solution space, the solution will lie in a ``corner'' of a convex solution space. In the next sections we derive bounds on possible $\lambda$-constellations with an implicitly convex $\lambda$-constellation solution space. We will then show that when the bound is met with equality, TSC and sum capacity are minimized and maximized respectively. \subsection{Properties of $\lambda$-Constellations} As in previous sections we define the eigenvalue and eigenvector set of the noise covariance matrix $\NCov$ as $\{ \sigma_i \}$ and $\{ \bphi_i \}$ respectively, $i=1,2, \cdots, N$. With no loss of generality, we assume that the $\{ \sigma_i \}$ and the signal energies $\{ p_k \}$, $k=1,2, \cdots, M$ are ordered as $\sigma_i \ge \sigma_{i+1}$ and $p_k \ge p_{k+1}$. For convenience, we also define $P = \sum_{k=1}^M p_k$ and $U = \sum_{i=1}^N \sigma_i$. We will assume at least as many codewords as dimensions ($M\ge N$) since if not, optimality dictates that the codewords be contained in the space spanned by the $M$ least noisy dimensions -- those with energies $\sigma_N, \sigma_{N-1}, \cdots, \sigma_{N-M+1}$. Our basic approach is to find upper and lower bounds to sums of ordered eigenvalues of $\Smatt + \NCov$, $\lambda_i \ge \lambda_{i+1}$. It is clear from the definition that if $\lambda$-constellations $\underline{\lambda}_1$ and $\underline{\lambda}_2$ satisfy the bounds, then for $0\le \alpha \le 1$, so does $\underline{\lambda}_3 = \alpha \underline{\lambda}_1 + (1-\alpha)\underline{\lambda}_2$. The solution space is therefore convex. Now, for any matrix $\Qmat$ with eigenvalues $\{ \mu_i \}$ ordered from largest to smallest we have \cite{strang}, \be \max_{\x_i^\top \x_j = \delta_{ij}} \sum_{i=1}^k \x_i^\top \Qmat \x_i = \sum_{i=1}^k \mu_i \ee %and similarly %\be %%\min_{\x_i^\top \x_j = \delta_{ij}} %\sum_{i=1}^k \x_i^\top \Qmat \x_i %= %\sum_{i=1}^k \mu_{N-i+1} %\ee Consider then \be \label{eq:kernel} \Smatt + \NCov = \sum_{i=1}^M \s_i \s_i^\top + \sum_{j=1}^N \sigma_i \bphi_i \bphi_i^\top \ee and that \be \max_{|\x|=1} \x^\top (\Smatt + \NCov) \x = \lambda_1 \ee It follows immediately that $\lambda_1 \ge \sigma_1$ and $\lambda_1 \ge |\s_1|^2 + \sigma_N = p_1 + \sigma_N$. Equally obvious is that $\lambda_1 \ge (P+U)/N$ \cite{RUY_IA,masseyrupf,anantharam}. Slightly less obvious is that \be \lambda_1 \ge \frac{1}{k} \sum_{i=1}^k (p_i + \sigma_{N-i+1}) \ee for $k=1,2,\cdots, N-1$. This may be shown by noting that $\sum_{i=1}^k \lambda_i \ge \sum_{i=1}^k (p_i + \sigma_{N-i+1})$ and that the minimum maximum $\lambda_1$ must then be at least this quantity divided by $k$. Therefore, we must have in total \be \label{eq:l1bound} \lambda_1 \ge \max \left [ \sigma_1, \max_{0 < k < N} \frac{1}{k}\sum_{i=1}^k (p_i + \sigma_{N-i+1}), \frac{P+U}{N} \right ] \ee and we will show that \equat{l1bound} may be used recursively to bound the quantity $\displaystyle{\sum_{i=1}^n} \lambda_i$. In what follows we denote the eigenvector of $(\Smatt + \NCov)$ associated with $\lambda_i$ as $\bpsi_i$. Suppose $\sigma_1$ is the minmax $\lambda_1$ bound. To meet the bound, no codeword can have energy along $\bphi_1$ since otherwise we must have $\lambda_1 > \sigma_1$. So, if $\bpsi_1 = \alpha \x + \sqrt{1-\alpha} \bphi_1$ where $\x \perp \bphi_1$ is the eigenvector with largest eigenvalue $\sigma_1$, then we must also have \be (\Smatt + \NCov) \x = \sigma_1 \x \ee which implies that $\exists \y \perp \bpsi_1$ also with eigenvalue $\sigma_1$. The overall implication is that we must have $\lambda_2 \ge \sigma_1$ as well. Now consider that with $\bpsi_1=\bphi_1$ we have \be \label{eq:l2bound} \lambda_2 \ge \max \left [ \sigma_2, \max_{0< k < N-1} \frac{1}{k}\sum_{i=1}^k (p_i + \sigma_{N-i+1}),\frac{P+U - \sigma_1}{N-1} \right ] \ee and we note that since we have \be \max \left [ \sigma_1, \max_{0 |\s_i|$. Then codeword $\s_1$ can attack codeword $\x$ and reduce TSC since $\delta > |s_i|^2 - |\x|^2$. \end{Proof} \begin{theorem}{\thmlabel{smallsigma}} Let $\{\s_k \}$ be the set of all codewords with eigenvalue $\lambda_I$. Suppose there exists a signal dimension $\bpsi$, an eigenvector of $\NCov$ with $(\Smatt+\NCov) \bpsi = \lambda_{II}\bpsi$, $\NCov \bpsi = \gamma\bpsi$ and $\lambda_{II} < \lambda_I$ but TSC cannot be reduced by dimensional attack. Then the partition of noise covariance eigenvectors $\bphi_i$ which spans $\{\s_k \}$ must all have eigenvalues $\{ \sigma_i \}$ no larger than $\gamma$, the noise covariance eigenvalue associated with $\bpsi$. \end{theorem} \begin{Proof}{\Thmref{smallsigma}} Let $E_{\phi}$ be the signal energy along dimension $\bphi$. We then have $\lambda_I = E_{\phi} + \sigma_{\phi}$. Likewise define the signal energy $E_{\psi}$ as the signal energy along $\bpsi$ so that $\lambda_{II} = E_{\psi}+\gamma$. For dimensional attack to be ineffective, we must have $\delta \le E_{\phi} - E_{\psi}$ which implies $E_{\phi}+\sigma_{\phi} - (E_{\psi}+\gamma) \le E_{\phi} - E_{\psi}$ which in turn implies $\sigma_{\phi} - \gamma \le 0$ for any $\bphi$ in the spanning set of $\{ \s_k \}$ thus proving the theorem. \end{Proof} The following theorem is implied directly by \Thmref{largecw} and \Thmref{smallsigma} and is stated without proof. \begin{theorem}{\thmlabel{biginsmall}} Let $\s_i$ and $\s_j$ be codewords with eigenvalues $\lambda_I$ and $\lambda_{II}$ respectively. Let each reside in spaces which contain largest noise covariances $\gamma_i$ and $\gamma_j$ respectively. If $|s_i| \ge |s_j|$, then $\lambda_I \ge \lambda_{II}$ (\Thmref{largecw}) and $\gamma_i \le \gamma_j$ (\Thmref{smallsigma}). In words, at equilibrium a higher power codeword has an eigenvalue at least as large as that of a lower power codeword. In addition, a higher power codeword resides in a partition of the noise covariance space with variances at least as small the space in which a lower power codewords resides. \end{theorem} \subsection{The Bounds of \Equat{l1bound}} The next three theorems address the three terms inside the $\max$ function of \equat{l1bound} and will be used directly to show that the warfare procedure produces eigenvalue sets which meet the lower bound specified by recursive application of \equat{l1bound}. \begin{theorem}{\thmlabel{bigsigma}} {\bf [Minmax $\sigma_1$]}: If $\sigma_1$ is the minmax eigenvalue bound in \equat{l1bound} then at equilibrium, all codewords must be orthogonal to $\bphi_1$. \end{theorem} \begin{Proof}{\Thmref{bigsigma}} Suppose at some equilibrium $\exists s_1$ with nonzero projection onto the eigenvector $\bphi_1$ associated with $\sigma_1$. This codeword must then have eigenvalue $\lambda_I > \sigma_1$. Now we note that since $\sigma_1$ is the minmax eigenvalue bound we must also have by \equat{l1bound} that $\sigma_1 \ge (P+U)/N$ where $P$ is the total codeword energy and $U$ is the total noise energy. Since the eigenvalues of $\Smatt + \NCov$ must sum to $P + U$, if $\exists \lambda_I > \sigma_1 \ge (P+U)/N$ then $\exists\lambda_{II}$ with $\lambda_{II} < \sigma_1 < \lambda_I$ which in turn implies that $\exists \bphi_i$ with $(\Smatt + \NCov) \bphi_i = \lambda_{II}\bphi_i$ and $\NCov \bphi_i = \sigma_i\bphi_i$ with $\sigma_i < \sigma_1$ since $\lambda_{II} \ge \sigma_i$. This contradicts \Thmref{smallsigma}. Thus, no codeword energy can exist along dimension $\bphi_1$ at equilibrium if $\sigma_1$ is the minmax bound for $\lambda_1$. \end{Proof} \begin{theorem}{\thmlabel{overpack}} {\bf [Minmax $\frac{1}{k}{\displaystyle \sum_{i=1}^k} (p_i + \sigma_{N-i+1})$]}: Define \be \label{eq:gamma} \gamma = \frac{1}{k} \sum_{i=1}^k (p_i + \sigma_{N-i+1}) \ee where $k$ is the largest integer $ k$. Then $\lambda_1 = \lambda_{I} \le \gamma$ and $\lambda_1 \ge \gamma$ is a direct contradiction owing to the ``largest $k$'' stipulation in the definition of $\gamma$. That is, there exists no $n>k$ such that $\lambda_I \ge \gamma$. Thus, we must have $n=k$. So in summary, if $\gamma$ as defined in \equat{gamma} is the minmax bound on $\lambda_1$, then at any equilibrium where warfare cannot be used to reduce TSC, the $k$ highest power codewords must reside in the $k$ lowest power noise dimensions and share the same eigenvalue $\gamma$, unique and the largest over all codewords. \end{Proof} \begin{theorem}{\thmlabel{uniform}} {\bf [ Minmax $\frac{P+U}{N}$]}: If the minmax bound for $\lambda_1$ is $(P+U)/N$, then all codewords must share the same eigenvalue $\lambda_I = (P+U)/N$ at an equilibrium where warfare cannot reduce TSC. \end{theorem} \begin{Proof}{\Thmref{uniform}} As in \Thmref{overpack}, let $\cal S$ be the set of $L$ highest power codewords residing in the $n$ lowest power noise dimensions. By \Thmref{manifest}, unless $L=n$, any difference in eigenvalues can be exploited to reduce TSC. Therefore, unless all the eigenvalues are already equal to $(P+U)/N$, we must have \be \lambda_I = \sum_{i=1}^n (p_i + \sigma_{N-i+1}) \ee However, since $(P+U)/N$ is the minmax value of $\lambda_1$, the structure of \equat{l1bound} requires $\lambda_I \ge (P+U)/N$, a condition which can only be met if $\lambda_I = (P+U)/N$. By the assumed monotonicity of eigenvalues for $\Smatt+\NCov$, if $\lambda_1 = (P+U)/N$, then all the eigenvalues must be $(P+U)/N$ thus completing the proof. \end{Proof} \subsection{The $\lambda$-Constellation Bound Is the Stopping Condition} \label{stopping} \Thmref{bigsigma}, \Thmref{overpack} and \Thmref{uniform} along with the recursive nature of the eigenvalue bound in \equat{l1bound} lead directly to the following theorem. \begin{theorem}{\thmlabel{stablepoint}} The only stable codeword ensembles for warfare-augmented greedy interference avoidance are those which which meet with equality the eigenvalue bound generated by recursive application of \equat{l1bound}. \end{theorem} \begin{Proof}{\Thmref{stablepoint}} Suppose the conditions of \Thmref{bigsigma} are satisfied. Then at equilibrium the bound on $\lambda_1$ specified by \equat{l1bound} is met with equality since no codeword energy resides in $\bphi_1$. All the codewords and remaining dimensions are orthogonal to $\bphi_1$. Alternately, suppose that the conditions of \Thmref{overpack} are satisfied for some $k