<figure><img src="image_1.png" /></figure>

HAL
open science

# Global optimality of the successive MaxBet Algorithm

Mohamed Hanafi, Jos M. F. Ten Berge

► To cite this version:

Mohamed Hanafi, Jos M. F. Ten Berge. Global optimality of the successive MaxBet Algorithm. Psychometrika, 2003, 68 (1), pp.97-104. hal-04473772

HAL Id: hal-04473772

https://oniris.hal.science/hal-04473772v1

Submitted on 22 Feb 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
GLOBAL OPTIMALITY OF THE SUCCESSIVE MAXBET ALGORITHM

MOHAMED HANAFI

DEPARTEMENT SMAD, ENITIAA, NANTES

JOS M.F. TEN BERGE

UNIVERSITY OF GRONINGEN

The Maxbet method is an alternative to the method of generalized canonical correlation analysis and of Procrustes analysis. Contrary to these methods, it does not maximize the inner products (covariances) between linear composites, but also takes their sums of squares (variances) into account. It is well-known that the Maxbet algorithm, which has been proven to converge monotonically, may converge to local maxima. The present paper discusses an eigenvalue criterion which is sufficient, but not necessary for global optimality. However, in two special cases, the eigenvalue criterion is shown to be necessary and sufficient for global optimality. The first case is when there are only two data sets involved; the second case is when the inner products between all variables involved are positive, regardless of the number of data sets.

Key words: canonical correlation, Procrustes rotation, multivariate eigenvalue problem, Maxbet.

Introduction

The canonical correlation method (Hotelling, 1936; Kettenring, 1971) yields, for column-wise centered data matrices $X_1(n \times k_1)$ and $X_2(n \times k_2)$, linear combinations $X_1u_1$ and $X_2u_2$ which correlate as highly as possible. It is well-known that these linear combinations capitalize on the relations between the sets of variables, possibly accounting for little variance within the sets. Similarly, in certain methods of successive Procrustes analysis, rotations are sought which maximize the sum of inner products (weighted congruence coefficients; Tucker, 1951) between rotated components, that possibly explain very little variance. To mitigate this problem, van de Geer (1984) has proposed the Maxbet method, which does take the internally explained variance into account. It can be applied to any number of matrices $X_1, \dots, X_m$ of order $n \times k_i$. Specifically, let $X = [X_1|\dots|X_m]$ be column-centered data matrices (centering should be omitted in case of Procrustes rotation of loading matrices). Let $u = [u'_1|u'_2|\dots|u'_m]'$, with subvectors of order $k_i \times 1$. Then Maxbet maximizes the function

$$f(\mathbf{u}) = \mathbf{u}'\mathbf{X}'\mathbf{X}\mathbf{u} \quad (1)$$

subject to the constraint that $\mathbf{u}$ is block-normed, that is, $u'_i u_i = 1, i = 1, \dots, m$. Clearly, $f(\mathbf{u})$ is not just a function of the inner product ($n \times$ covariance) $u'_i X'_i X_j u_j (i \neq j)$ between the linear composites, but also takes their sums of squares (variance) $u'_i X'_i X_i u_i$ into account. Once a vector $\mathbf{u} = \mathbf{u}^{(1)}$ has been obtained, another block-normed vector $\mathbf{u}^{(2)}$ can be determined in the residual space, after replacing $X_i$ by $X_i (I_{k_i} - u'_i u'_i)$, $i = 1, \dots, m$, where $I_{k_i}$ is the identity matrix of order $k_i$. That is, we are concerned here with Maxbet as a successive method. Simultaneous variants have also been proposed, but will not be discussed here.

An iterative Maxbet algorithm, essentially based on a method by Horst (1961), has been proven to converge monotonically by ten Berge (1988), and also by Chu and Watterson (1993)

The authors are obliged to Henk Kiers for critical comments on a previous draft.

Requests for reprints should be sent to Mohamed Hanafi, ENITIAA, Rue de la Geraudiere, 44322 Nantes, CEDEX 03, FRANCE. E-Mail: hanafi@enitiaa-nantes.fr
who studied the Maxbet problem as the multivariate eigenvalue problem. However, there is no guarantee that the global maximum will be obtained. In fact, Chu and Watterson have shown that convergence to a strictly local maximum is possible. This implies that one should run the method from different (random) starts, and pick the solution with the highest function value, hoping that this represents the global maximum. Although there is no reason to question the validity of this procedure in general, a more straightforward alternative can be proposed. The present paper offers an explicit criterion which distinguishes between local and global maxima right away when $m = 2$. For $m > 2$, the criterion is not necessarily conclusive when some of the elements of $X'X$ are negative.

## The Maxbet Algorithm and a Sufficient Condition for Global Optimality

Because the Maxbet algorithm uses inner products only, we define, for $i, j = 1, \dots, m$, $A_{ij} = X_i'X_j$, and collect these inner product matrices in the supermatrix

$$A = X'X = \begin{bmatrix} A_{11} & A_{12} & \cdots & A_{1m} \\ A_{21} & A_{22} & \cdots & A_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ A_{m1} & A_{m2} & \cdots & A_{mm} \end{bmatrix}. \quad (2)$$

The Maxbet problem now reduces to maximizing

$$f(\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_m) = \mathbf{u}'A\mathbf{u} = \sum_{i,j=1}^{m} \mathbf{u}_i' A_{ij} \mathbf{u}_j \quad (3)$$

subject to $\mathbf{u}_1'\mathbf{u}_1 = \dots = \mathbf{u}_m'\mathbf{u}_m = 1$. Because $f$ is continuous, and the unit sphere is compact in finite dimensional space, a maximum for (3) does exist. Consider the following Maxbet algorithm:

1. Take arbitrary initial unit length vectors $\mathbf{u}_i, i = 1, 2, \dots, m$

2. For $i = 1, 2, \dots, m$, compute

$$\mathbf{v}_i = \sum_{j=1}^{m} A_{ij} \mathbf{u}_j$$

3. For $i = 1, 2, \dots, m$, rescale $\mathbf{v}_i$ to unit length, and set $\mathbf{u}_i = \mathbf{v}_i$.

4. Repeat Steps 2 and 3 until convergence.

After convergence, $\mathbf{u}$ satisfies the stationary equation

$$A \begin{bmatrix} \mathbf{u}_1 \\ \mathbf{u}_2 \\ \vdots \\ \mathbf{u}_m \end{bmatrix} = \begin{bmatrix} \lambda_1 \mathbf{u}_1 \\ \lambda_2 \mathbf{u}_2 \\ \vdots \\ \lambda_m \mathbf{u}_m \end{bmatrix}, \quad \mathbf{u}_i' \mathbf{u}_i = 1, i = 1, 2, \dots, m \quad (4)$$

for certain scalars $\lambda_i, i = 1, 2, \dots, m$ (van de Geer, 1984; ten Berge, 1988). The associated value of $f$, see (3), is $\mathbf{u}'A\mathbf{u} = \lambda_1 + \lambda_2 + \dots + \lambda_m$. Upon defining the matrix

$$A_{\lambda} = A_{\{\lambda_1, \lambda_2, \dots, \lambda_m\}} = \begin{bmatrix} A_{11} - \lambda_1 \mathbf{I}_{k_1} & A_{12} & \cdots & A_{1m} \\ A_{21} & A_{22} - \lambda_2 \mathbf{I}_{k_2} & \cdots & A_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ A_{m1} & A_{m2} & \cdots & A_{mm} - \lambda_m \mathbf{I}_{k_m} \end{bmatrix} \quad (5)$$
it is clear from (4) that **u** is a block-normed eigenvector of **A**_λ_, associated with an eigenvalue zero. The following result is straightforward:

*Result 1.* When, for a solution {$\mathbf{u}, \lambda_1, \lambda_2, \dots, \lambda_m$} satisfying (4), the implied $\mathbf{A}_\lambda$ is negative semidefinite, $\mathbf{u}$ yields the global maximum of $f$.

*Proof.* Let $\mathbf{A}_\lambda$ be negative semidefinite, so $\mathbf{x}'\mathbf{A}_\lambda\mathbf{x} \le 0$ for every $\mathbf{x}$. In particular, for every block-normed vector $\mathbf{v}$ we have

$$ \mathbf{v}'\mathbf{A}_\lambda\mathbf{v} = \mathbf{v}'\mathbf{A}\mathbf{v} - \lambda_1\mathbf{v}'_1\mathbf{v}_1 - \lambda_2\mathbf{v}'_2\mathbf{v}_2 - \dots - \lambda_m\mathbf{v}'_m\mathbf{v}_m = f(\mathbf{v}) - \lambda_1 - \lambda_2 - \dots - \lambda_m, $$

and hence $f(\mathbf{v}) \le \lambda_1 + \lambda_2 + \dots + \lambda_m$, constituting an upper bound to $f$. The fact that $\mathbf{u}$ is block-normed and attains the upper bound, because $f(\mathbf{u}) = \lambda_1 + \lambda_2 + \dots + \lambda_m$, shows that $\mathbf{u}$ is globally optimal for the function $f$ over all block-normed vectors. $\square$

### A Criterion for Global Optimality when $m = 2$

It will be shown in the sequel that the sufficient condition for global optimality, pinpointed in Result 1, is not necessary for global optimality. However, in the special case of $m = 2$, the condition is necessary and sufficient for global optimality. Before proving this, we need two preliminary results:

*Result 2.* Let $\mathbf{u}$, containing two blocks $\mathbf{u}_1$ and $\mathbf{u}_2$, be a block-normed vector. Let $\mathbf{w} = [\mathbf{w}'_1 \mathbf{w}'_2]'$ be a unit length vector orthogonal to $\mathbf{u}$, and let $\mathbf{w}'_1 \mathbf{w}_1 \neq \mathbf{w}'_2 \mathbf{w}_2$. Then there exists a linear combination $\mathbf{v} = \alpha \mathbf{u} + \beta \mathbf{w}$ (with $\beta \neq 0$) which is again block-normed, unless $\mathbf{w} = [\mathbf{w}'_1 \mathbf{w}'_2]'$ is block-orthogonal to $\mathbf{u}$, that is, unless $\mathbf{u}'_1 \mathbf{w}_1 = \mathbf{u}'_2 \mathbf{w}_2 = 0$.

*Proof.* Suppose there exists a block-normed $\mathbf{v} = \alpha \mathbf{u} + \beta \mathbf{w}$ with $\beta \neq 0$. Then

$$ \alpha^2 + \beta^2 \mathbf{w}'_1 \mathbf{w}_1 + 2\alpha\beta \mathbf{u}'_1 \mathbf{w}_1 = 1 \quad \text{and} \quad \alpha^2 + \beta^2 \mathbf{w}'_2 \mathbf{w}_2 + 2\alpha\beta \mathbf{u}'_2 \mathbf{w}_2 = 1. \quad (6) $$

Adding these yields

$$ 2\alpha^2 + \beta^2 = 2, \quad (7) $$

and subtracting yields

$$ \beta^2(\mathbf{w}'_1 \mathbf{w}_1 - \mathbf{w}'_2 \mathbf{w}_2) = 2\alpha\beta(\mathbf{u}'_2 \mathbf{w}_2 - \mathbf{u}'_1 \mathbf{w}_1). \quad (8) $$

Dividing (8) by $\beta$ and using $\mathbf{u}'\mathbf{w} = 0$, hence $\mathbf{u}'_1 \mathbf{w}_1 = -\mathbf{u}'_2 \mathbf{w}_2$, yields

$$ \beta(\mathbf{w}'_1 \mathbf{w}_1 - \mathbf{w}'_2 \mathbf{w}_2) = 4\alpha(\mathbf{u}'_2 \mathbf{w}_2). \quad (9) $$

Hence, because $\mathbf{w}'_1 \mathbf{w}_1 \neq \mathbf{w}'_2 \mathbf{w}_2$,

$$ \beta = \alpha(4\mathbf{u}'_2 \mathbf{w}_2)/(\mathbf{w}'_1 \mathbf{w}_1 - \mathbf{w}'_2 \mathbf{w}_2). \quad (10) $$

Squaring (10) and combining it with (7) readily yields

$$ \alpha^2 = \frac{(\mathbf{w}'_1 \mathbf{w}_1 - \mathbf{w}'_2 \mathbf{w}_2)^2}{(\mathbf{w}'_1 \mathbf{w}_1 - \mathbf{w}'_2 \mathbf{w}_2)^2 + 8(\mathbf{u}'_2 \mathbf{w}_2)^2}. \quad (11) $$

Taking the square root, with arbitrary sign, gives $\alpha$, and then $\beta$ follows from (10).
It is easy to verify that $\alpha$ and $\beta$ defined by (11) and (10) do produce a block-normed $\mathbf{v}$. That is, when we obtain $\alpha$ from the square root of (11), and $\beta$ from (10), it is immediate that (7) and (8) are satisfied. Next, rewriting (8) into $\beta^2 \mathbf{w}'_1 \mathbf{w}_1 + 2\alpha\beta \mathbf{u}'_1 \mathbf{w}_1 = \beta^2 \mathbf{w}'_2 \mathbf{w}_2 + 2\alpha\beta \mathbf{u}'_2 \mathbf{w}_2$, and adding $\alpha^2$ to both sides, shows that both blocks of $\mathbf{v} = \alpha \mathbf{u} + \beta \mathbf{w}$ have the same sum of squares. Finally, using (7), these sums of squares can be shown to be 1.

This solution is unique up to a joint sign change of $\alpha$ and $\beta$. However, it will produce $\beta = 0$ if and only if $\mathbf{u}'_2 \mathbf{w}_2 = 0$. In that case, it follows from $\mathbf{u}'\mathbf{w} = 0$ that $\mathbf{w}$ is block-orthogonal to $\mathbf{u}$, that is

$$ \mathbf{u}'_1 \mathbf{w}_1 = \mathbf{u}'_2 \mathbf{w}_2 = 0. \qquad (12) $$

□

*Result 3.* Let a vector $\mathbf{w}$ be block-orthogonal to a vector $\mathbf{u}$. Then there exist vectors $\mathbf{w}^*$, orthogonal, but not block-orthogonal to $\mathbf{u}$.

*Proof.* Let $\mathbf{u}$ and $\mathbf{w}$ satisfy (12). Choose a pair of vectors $\mathbf{d}_1$ not orthogonal to $\mathbf{u}_1$ and $\mathbf{d}_2$ not orthogonal to $\mathbf{u}_2$. Construct the vector

$$ \mathbf{q} = \begin{bmatrix} (\mathbf{d}'_2 \mathbf{u}_2) \mathbf{d}_1 \\ -(\mathbf{d}'_1 \mathbf{u}_1) \mathbf{d}_2 \end{bmatrix}. \qquad (13) $$

Then $\mathbf{q}$ is orthogonal, but not block-orthogonal to $\mathbf{u}$. Now taking $\mathbf{w}^* = t\mathbf{q} + \mathbf{w}$, for an arbitrary nonzero scalar $t$, generates a vector $\mathbf{w}^*$ which is likewise orthogonal, but not block-orthogonal to $\mathbf{u}$. Note that (12) already implies $\mathbf{u}'\mathbf{w} = 0$. □

We can now formulate our main result for the case $m = 2$:

*Result 4.* When a solution $\{\mathbf{u}, \lambda_1, \lambda_2\}$ to (4) is globally optimal, $A_\lambda$ is negative semidefinite.

*Proof.* Suppose $A_\lambda$ has a positive eigenvalue $\sigma$, with $\mathbf{w}$ the associated eigenvector. Suppose that $\mathbf{w}$ is block-normed, possibly after rescaling. Then $\mathbf{w}'A_\lambda \mathbf{w} > 0$ implies $\mathbf{w}'A\mathbf{w} - \lambda_1 - \lambda_2 > 0$, hence $\mathbf{w}'A\mathbf{w} > \lambda_1 + \lambda_2 = \mathbf{u}'A\mathbf{u}$, showing that $\mathbf{w}$ is a better solution than $\mathbf{u}$. Else, when $\mathbf{w}$ is not block-orthogonal to $\mathbf{u}$, we can invoke Result 2 to find a block-normed vector $\mathbf{v} = \alpha\mathbf{u} + \beta\mathbf{w}$, with $\beta \neq 0$, which is better than $\mathbf{u}$ (the block-normed eigenvector of $A_\lambda$ associated with eigenvalue zero) because $\mathbf{v}'A_\lambda\mathbf{v} = (\alpha\mathbf{u} + \beta\mathbf{w})'A_\lambda(\alpha\mathbf{u} + \beta\mathbf{w}) = \beta^2\mathbf{w}'A_\lambda\mathbf{w} > 0$.

Finally, if $\mathbf{w}$ is block-orthogonal to $\mathbf{u}$, we can take a vector $\mathbf{w}^*$ as defined in Result 3, with $t$ small enough (details to be specified below) to preserve $\mathbf{w}^*A_\lambda\mathbf{w}^* > 0$, and scale it to unit length. This $\mathbf{w}^*$ is not block-orthogonal to $\mathbf{u}$. If $\mathbf{w}^*$ is block-normed, it is better than $\mathbf{u}$. Else, Result 2 can be applied to find a vector $\mathbf{v}^* = \alpha\mathbf{u} + \beta\mathbf{w}^*$ to arrive at a solution with $\mathbf{v}^*A_\lambda\mathbf{v}^* = \beta^2\mathbf{w}^*A_\lambda\mathbf{w}^* > 0$. This again implies that $\mathbf{v}^*$ is a block-normed vector which is better than $\mathbf{u}$. Hence, in all possible cases, $\mathbf{u}$ is not globally optimal when $A_\lambda$ has at least one strictly positive eigenvalue. □

The above can be summarized and further specified in an algorithm to construct a better solution than $\mathbf{u}$, in case $A_\lambda$ has a positive eigenvalue.

1. Take $\mathbf{w}$ as the eigenvector of $A_\lambda$, associated with the positive eigenvalue $\sigma$. If $\mathbf{w}$ is block-normed, it is a better solution than $\mathbf{u}$.

2. Else, compute $\mathbf{u}'_2 \mathbf{w}_2$. If it is nonzero, use (10) and (11) to find a $\mathbf{v}$ better than $\mathbf{u}$.

3. Else, find vectors $\mathbf{d}_1$ not orthogonal to $\mathbf{u}_1$ and $\mathbf{d}_2$ not orthogonal to $\mathbf{u}_2$, and construct $\mathbf{q}$ by (13). If $\mathbf{q}'A_\lambda\mathbf{q} > 0$, take any nonzero $t$ with the same sign as $\mathbf{q}'A_\lambda\mathbf{w}$. This guarantees that
$\mathbf{w}^* = t\mathbf{q} + \mathbf{w}$ will have $\mathbf{w}^{*'}\mathbf{A}_\lambda\mathbf{w}^* > 0$. If $\mathbf{q}'\mathbf{A}_\lambda\mathbf{q} < 0$, take $t$ nonzero yet close enough to zero to have $\mathbf{w}^*\mathbf{A}_\lambda\mathbf{w}^* = t^2\mathbf{q}'\mathbf{A}_\lambda\mathbf{q} + 2t\mathbf{q}'\mathbf{A}_\lambda\mathbf{w} + \sigma > 0$. That is, pick $t$ to yield a positive value for the quadratic function $t^2\mathbf{q}'\mathbf{A}_\lambda\mathbf{q} + 2t\mathbf{q}'\mathbf{A}_\lambda\mathbf{w} + \sigma$. Because this function represents a concave parabola, with a strictly positive value for $t = 0$, there exist nonzero values for $t$, close to 0, still yielding positive function values. Take any of these values for $t$. Next, rescale $\mathbf{w}^*$ to have a sum of squares 2.

4. When $\mathbf{w}^*$ is block-normed, it is a better solution than $\mathbf{u}$. Else, apply Result 2 to $\mathbf{u}$ and $\mathbf{w}^*$, scaled to unit length. Because $\mathbf{w}^*$ is not block-orthogonal to $\mathbf{u}$, we find $\beta^2 > 0$, and hence we have found a $\mathbf{v}^*$ better than $\mathbf{u}$.

Combining Result 1 and Result 4 implies that having $\mathbf{A}_\lambda$ negative semidefinite is necessary and sufficient for global optimality in the case of $m = 2$. An immediate application is the following. Chu and Watterson (1993, p. 1104) have given an example with two blocks and noted that the Maxbet algorithm tends to converge to two different solutions, depending on the start. It is readily verified that $\mathbf{A}_\lambda$ is negative semidefinite in the case with the highest function value, and that it has a positive eigenvalue in the other case. Result 1 implies at once that the former solution is globally optimal; Result 4 implies that the latter solution is a local optimum.

Another Look at the Case $m > 2$

When $m > 2$, we still have the sufficient condition of Result 1, implying that the global maximum has been attained when $\mathbf{A}_\lambda$ is negative semidefinite. However, the condition now does not seem to be necessary. For instance, when $m = 3$ and

$$ \mathbf{A} = \begin{bmatrix} 45 & -20 & 5 & 6 & 16 & 3 \\ -20 & 77 & -20 & -25 & -8 & -21 \\ \hline 5 & -20 & 74 & 47 & 18 & -32 \\ 6 & -25 & 47 & 54 & 7 & -11 \\ \hline 16 & -8 & 18 & 7 & 21 & -7 \\ 3 & -21 & -32 & -11 & -7 & 70 \end{bmatrix}, \quad (14) $$

and we start the iterations with $\mathbf{u} = \mathbf{1}$, we find $\mathbf{u} = [.4921, -.8705, .8004, .5995, .5648, -.8228]'$ after convergence, with $f(\mathbf{u}) = 378.9624$ and largest eigenvalue .4819 for $\mathbf{A}_\lambda$. However, when we start with $\mathbf{u} = [1 1 1 -1 -1 -1]'$, we find an inferior $\mathbf{u} = [-.4003, .9164, .8847, .4661, .1191, -.9929]'$, with $f(\mathbf{u}) = 314.6556$ and largest eigenvalue 40.88 for $\mathbf{A}_\lambda$. Other solutions never seem to occur. In addition, a random search of 10,000,000 vectors with elements from the uniform $[-.5, .5]$ distribution, rescaled block-wise to unit length, failed to produce an $f$ in excess of 378.9624. This indicates that the condition is not necessary when $m > 2$.

Random construction of data indicates that very often a negative semidefinite $\mathbf{A}_\lambda$ does arise at convergence. In particular, when all elements of $\mathbf{A}$ are positive, the condition of negative semidefinite $\mathbf{A}_\lambda$ does again constitute a necessary and sufficient condition for global optimality of the Maxbet function, as will now be proven.

**Result 5.** When all elements of $\mathbf{A}$ are positive, having $\mathbf{A}_\lambda$ negative semidefinite is necessary and sufficient for a global maximum of $f$.

*Proof.* Sufficiency follows from Result 1. To prove necessity, let $k = k_1 + k_2 + \dots + k_m$, let $a_{gh}, g, h = 1, \dots, k$, be the elements of $\mathbf{A}$, let $\mathbf{u} = [\mathbf{u}_1, \dots, \mathbf{u}_m]'$, and let $\mathbf{A}_\lambda\mathbf{u} = \mathbf{0}$, for some block-normed vector $\mathbf{u}$, such that $\mathbf{u}'\mathbf{A}\mathbf{u}$ is the global maximum of the Maxbet function $f$ over all block-normed vectors. Let the largest eigenvalue of $\mathbf{A}_\lambda$ be positive, and let $\mathbf{w}(\mathbf{w}'\mathbf{w} = 1)$ be the
associated eigenvector. From $a_{gh} > 0, g, h = 1, \dots, k$, we have

$$ \mathbf{u}'\mathbf{A}\mathbf{u} = \sum_{g,h}^{k} u_g u_h a_{gh} \leq \sum_{g,h}^{k} |u_g u_h| a_{gh}, \qquad (15) $$

with equality if and only if $|u_g u_h| = u_g u_h, g, h = 1, \dots, k$. Noting that sign changes preserve the block-normed form of $\mathbf{u}$, it can be inferred from the maximality of $\mathbf{u}'\mathbf{A}\mathbf{u}$ that $\mathbf{u}$ has all elements of the same sign.

On the other hand, because $\mathbf{w}$ is associated with the largest eigenvalue of $\mathbf{A}_\lambda$, $\mathbf{w}'\mathbf{A}_\lambda\mathbf{w}$ is a maximum of $\mathbf{x}'\mathbf{A}_\lambda\mathbf{x}$ over all unit-length vectors $\mathbf{x}$. That is,

$$ \mathbf{w}'\mathbf{A}_\lambda\mathbf{w} \geq \mathbf{x}'\mathbf{A}_\lambda\mathbf{x} \qquad (16) $$

for all $\mathbf{x}$ with $\mathbf{x}'\mathbf{x} = 1$. Also note that

$$ \mathbf{w}'\mathbf{A}_\lambda\mathbf{w} = \mathbf{w}'\mathbf{A}\mathbf{w} - \sum_g w_g^2 \lambda_g, \qquad (17) $$

where $\sum_g w_g^2 \lambda_g$ is constant under sign reflections of elements of $\mathbf{w}$. Hence, the optimality of $\mathbf{w}$ implies that no such sign reflection can increase the value of $\mathbf{w}'\mathbf{A}\mathbf{w}$. Therefore, $\mathbf{w}$ also has all elements of the same sign. This is impossible because $\mathbf{u}$ and $\mathbf{w}$, being eigenvectors of a symmetric matrix, associated with distinct eigenvalues, are necessarily orthogonal. The contradiction implies that $\mathbf{A}_\lambda$ cannot have a positive eigenvalue at the global maximum. $\square$

Result 5 is closely related to the well-known Perron-Frobenius lemma (Frobenius, 1912; Perron, 1907). It might be christened the Perron-Frobenius lemma for the multivariate eigenvalue problem. In retrospect, it allows us to verify that the positive eigenvalue at what seems to be the global maximum for the example of (14) does indeed imply that some elements of $\mathbf{A}$ are negative. Had these elements all been positive, Result 5 would have precluded the occurrence of a positive eigenvalue of $\mathbf{A}_\lambda$ at the global maximum.

## Discussion

The results of the previous sections have obvious implications for successive Maxbet algorithms, whether applied to data matrices, as an alternative to canonical correlation analysis, or to matrices of factor loadings, in an orthogonal Procrustes context. After convergence, inspection of the largest eigenvalue of $\mathbf{A}_\lambda$ should be standard practice. When it is zero, we have attained the global maximum. When it is nonzero, and $m = 2$, we are at a local maximum. When it is nonzero, and all elements of $\mathbf{A}$ are positive, we are also at a local maximum. When $m > 2$ and $\mathbf{A}$ has one or more negative elements, a positive eigenvalue is inconclusive: We may or may not have attained the global maximum. It is not clear how many or how small the negative elements of $\mathbf{A}$ have to be to invalidate Result 5.

Sometimes, the Maxbet algorithm is applied to column-wise orthonormal data matrices. In such cases, Maxbet coincides with inner product maximization. The $m = 2$ case of that problem has a closed-form solution, for example, ten Berge (1988). It is readily verified that this solution satisfies our necessary and sufficient condition for the $m = 2$ case. When $m > 2$, there is no closed-form solution, and the sufficient condition of the present paper applies. Even with orthonormalized data, the condition is still not necessary for a global maximum, although cases where it fails to be satisfied at the global optimum tend to be extremely rare.

## References

Chu, M.T., & Watterson, J.L. (1993). On a multivariate eigenvalue problem, Part I: Algebraic theory and a power method. *SIAM Journal on Scientific Computing*, 14(5), 1089-1106.
Frobenius, G. (1912). Über Matrizen aus nicht negativen Elementen [On matrices of nonnegative elements]. *Sitzungs- berichte Preussische Akademie der Wissenschaft* [Proceedings of the Prussian Academy of Science] (pp. 456–477). Berlin.

Horst, P. (1961). Relations among *m* sets of measures. *Psychometrika*, *26*, 129–149.

Hotelling, H. (1936). Relations between two sets of variates. *Biometrika*, *28*, 321–377.

Kettenring, J.R. (1971). Canonical analysis of several sets of variables. *Biometrika*, 58, 433–451.

Perron, O. (1907). Grundlagen für eine Theorie des Jacobischen Kettenbruchalgorithmus. [Foundations for a theory of the Jacobian continued fraction algorithm.] *Mathematische Annalen*, 64, 11–76.

ten Berge, J.M.F. (1988). Generalized approaches to the MAXBET problem and the MAXDIFF problem, with applications to canonical correlations. *Psychometrika*, *53*, 487–494.

Tucker, R.L. (1951). *A method for synthesis of factor analysis studies* (Personnel Research Section Rep. No. 984). Washington DC: Department of the Army.

van de Geer, J.P. (1984). Linear relations among *k* sets of variables. *Psychometrika*, *49*, 79–94.

Manuscript received 18 MAY 2001

Final version received 20 MAY 2002