Covariance eigenvalues with prescribed multiplicities

Gérard Letac^{∗}

Résumé

We give a new proof of a result due to M. Keane and J.-L. Philoche on the existence of the maximum likelihood in the Gaussian case when the covariance has constraints on the multiplicities of the eigenvalues.

Let n be a fixed integer, M be the linear space of symmetric n × n real matrices and M_{+} be the open cone of positive definite elements of M. Denote by I the set of all sequences m = (m_{1}, m_{2}, …, m_{r}) of positive integers with m_{1} +⋯+m_{r} = n. Note that the integer r is not constant on I. It is easy to see that I has 2^{n−1} elements, since the size of I is the coefficient of x^{n} in

∑_{r=1}^{∞} (\frac{x}{1 − x})^{r} = \frac{x}{1 − 2x}.

A more combinatorial way for getting this result is to associate to m in I the subset of {1, 2, …, n−1} defined by

{m_{1}, m_{1} + m_{2}, …, m_{1} + m_{2} + ⋯ + m_{r−1}}.

This is clearly a one to one correspondence between I and the family of all subsets of {1, 2, …, n−1} which has 2^{r−1} elements.

For m in I, we denote by M_{m} the set of elements Σ of M_{+} such that furthermore the highest eigenvalue μ_{1} of Σ has multiplicity m_{1}, the second highest eigenvalue μ_{2} has multiplicity m_{2} and so on. In other terms, the characteristic polynomial of Σ has the form det(Σ − λI_{n}) = (−1)^{n} ∏_{i=1}^{r}(λ − μ_{i})^{m_{i}} for some sequence μ_{1} > μ_{2} > ⋯ > μ_{r} > 0. For instance, M_{m} is the set of positive definite matrices with distinct eigenvalues when m = (1, 1, …, 1) and is the set of positive multiples of the identity matrix I_{n} when m = (n).

This set M_{m} has a relatively complicated structure. If Σ is in M_{m} with eigenvalues μ_{1} > μ_{2} > ⋯ > μ_{r} > 0, then there exists an orthogonal matrix U of order n such that

Σ = U Diag(μ_{1}I_{m_{1}}, …, μ_{r}I_{m_{r}}) U^{T} ,  (0.1)

where U^{T} is the transposed matrix. However, U is not unique, since if we consider a sequence (V_{i})_{i=1}^{r} where V_{i} is an arbitrary orthogonal matrix of order m_{i} and if we introduce the orthogonal matrix

V = Diag(V_{1}, …, V_{r})  (0.2)

then U can be replaced by UV in (0.1). Thus an element of M_{m} is parametrized by two things : the μ’s, whose set is homeomorphic to (0, ∞)^{r} by the correspondence

(μ_{1}, …, μ_{r}) ↦ (μ_{1} − μ_{2}, μ_{2} − μ_{3}, …, μ_{r−1} − μ_{r}, μ_{r});

∗Laboratoire de statistique et probabilités, Université Paul Sabatier, 31062 Toulouse, France.

the U’s, up to the V ’s, whose set is identified to the quotient of the orthogonal group O(n) by the subgroup of the orthogonal matrices of the form (0.2). We denote by O(m) this subgroup, which is isomorphic to O(m_{1}) × ⋯ × O(m_{r}). This quotient is the set of equivalence classes defined by the following equivalence relation on O(n) : we have U ∼ U_{1} if there exists V in the subgroup O(m) such that U_{1} = UV. This quotient is naturally endowed with a structure of a compact manifold. The manifold M_{m} is therefore homeomorphic to the product

(0, ∞)^{r} × (O(n)/O(m)) .  (0.3)

Finally, we introduce a partial order ≺ on I as follows : for n = (n_{1}, n_{2}, …, n_{p}) we declare that the following elements of I

m = (n_{1} + n_{2}, n_{3}, n_{4}, ⋯, n_{p}),
m = (n_{1}, n_{2} + n_{3}, n_{4}, ⋯, n_{p}), …, m = (n_{1}, n_{2}, ⋯, n_{p−1} + n_{p})

satisfy n ≺ m. Iterating the above process, we get a partial order on I for which an explicit description is a bit tedious : for m = (m_{1}, m_{2}, …, m_{r}) and n = (n_{1}, n_{2}, …, n_{p}) in I we have n ≺ m if and only if there exists an increasing sequence of integers k_{0} = 0 < k_{1} < ⋯ < k_{r} = p such that for all i = 1, …, r one has

m_{i} = ∑_{k_{i−1}<j≤k_{i}} n_{j}.  (0.4)

Note that for n ≺ m, this sequence (k_{i}) is unique. For given m = (m_{1}, m_{2}, …, m_{r}) there are exactly 2^{(m_{1}−1)+···+(m_{r}−1)} = 2^{n−r} elements n ∈ I such that n ≺ m. Similarly, for given n = (n_{1}, n_{2}, …, n_{p}) there are exactly 2^{p−1} elements m ∈ I such that n ≺ m. The elements m = (1, 1, …, 1) and m = (n) are respectively the minimal and maximal elements of I. We are going to prove the following result by elementary inequalities :

Theorem 1. Let n = (n_{1}, …, n_{p}) and m = (m_{1}, …, m_{r}) be in in I such that n ≺ m. Let us fix S in M_{n} with its diagonalized form

S = U_{0} Diag(s_{1}I_{n_{1}}, …, s_{p}I_{n_{p}}) U_{0}^{T} ,  (0.5)

where U_{0} is an orthogonal matrix of order n and where s_{1} > s_{2} > ⋯ > s_{p} > 0. Consider the function F on M_{m} defined by

Σ ↦ F (Σ) = − log(det Σ) − trace (SΣ^{−1}).

Then F has a maximum on M_{m}. If for all i = 1, …, r one defines

μ_{i}^{0} = \frac{1}{m_{i}} ∑_{k_{i−1}<j≤k_{i}} n_{i}s_{j}  (0.6)

where the (k_{i})’s are defined by (0.4), then the maximum of F is reached at the point

Σ_{0} = U_{0} Diag(μ_{1}^{0}I_{m_{1}}, …, μ_{r}^{0}I_{m_{r}}) U_{0}^{T}  (0.7)

and only at this point. Finally, if (Σ_{t})_{t≥1} is a sequence of M_{m}, we have

lim_{t→∞} F (Σ_{t}) = F (Σ_{0}) ⇔ lim_{t→∞} Σ_{t} = Σ_{0}.  (0.8)

Proof. Note that we have μ_{1}^{0} > μ_{2}^{0} > ⋯ > μ_{r}^{0} > 0. Leaning on the fact that M_{m} is essentially the

product of two sets (see (0.3)), we prove the result in two steps – Step 1 : We assume first that Σ has eigenvalues μ_{1} > μ_{2} > ⋯ > μ_{r} > 0 and we prove the

inequality

trace (SΣ^{−1}) ≥ ∑_{i=1}^{r} \frac{1}{μ_{i}} ∑_{k_{i−1}<j≤k_{i}} n_{j}s_{j}  (0.9)

and the equality is reached if and only if Σ has the form

Σ = U_{0} Diag(μ_{1}I_{m_{1}}, …, μ_{r}I_{m_{r}}) U_{0}^{T}  (0.10)

where U_{0} is defined in (0.5).

– Step 2 : We prove that the maximum of

(μ_{1}, μ_{2}, ⋯, μ_{r}) ↦ − ∑_{i=1}^{r}(m_{i} log μ_{i} + \frac{1}{μ_{i}} ∑_{k_{i−1}<j≤k_{i}} n_{j}s_{j}).  (0.11)

is reached if and only if μ_{i} = μ_{i}^{0} for all i = 1, …, r. We prove now Step 1. We start with a Lemma :

Lemma 2 Let n = (n_{1}, …, n_{p}) and m = (m_{1}, …, m_{r}) be in in I such that n ≺ m. Consider a matrix q = (q_{ij}) with non negative elements with r rows and p columns such that for all i = 1, …, r and j = 1, …, p

∑_{i=1}^{r} q_{ij} = n_{j}, ∑_{j=1}^{p} q_{ij} = m_{i}.  (0.12)

Consider also the matrix q^{0} with r rows and p columns defined by q_{ij}^{0} = n_{j} if k_{i−1} < j ≤ k_{i} and q_{ij}^{0} = 0 if not (the k_{i}’s are defined by (0.4)). Then for all u = 1, …, r and v = 1, …, p one has

∑_{i=u}^{r} ∑_{j=1}^{v} q_{ij} ≥ ∑_{i=u}^{r} ∑_{j=1}^{v} q_{ij}^{0},  (0.13)

and the equality holds for all u and v if and only if q = q^{0}.

Proof of Lemma 2. Since ∑_{i=1}^{r} q_{ij} = ∑_{i=1}^{r} q_{ij}^{0} = n_{j} we have

∑_{i=u}^{r} ∑_{j=1}^{v}(q_{ij} − q_{ij}^{0}) = ∑_{i=u}^{r} ∑_{j=v+1}^{p}(q_{ij}^{0} − q_{ij}).

Now the matrix q^{0} has the following form :

q^{0} = [ \begin{matrix}n_{1} & … & n_{k_{1}} & 0 & … & 0 & 0 & … & 0 & … & 0 \\ 0 & … & 0 & n_{k_{1}+1} & … & n_{k_{2}} & 0 & … & 0 & … & 0 \\ … & … & … & … & … & … & … & … & … & … & … \\ 0 & … & 0 & 0 & … & 0 & 0 & … & n_{k_{r−1}+1} & … & n_{k_{r}} \end{matrix} ] .  (0.14)

The idea of the proof is to discuss the position of (u − 1, v + 1) in the above array : either it is in the upper part of zeros, namely k_{u−1} ≤ v, or not.

Suppose first that k_{u−1} ≤ v. Then for all j > v the i such that k_{i−1} < j ≤ k_{i} satisfies u ≤ i. This implies ∑_{i=u}^{r} q_{ij}^{0} = n_{j} and we obtain

∑_{j=v+1}^{p} ∑_{i=u}^{r} q_{ij} ≤ ∑_{j=v+1}^{p} n_{j} = ∑_{i=u}^{r} ∑_{j=v+1}^{p} q_{ij}^{0}.  (0.15)

Suppose now that v < k_{u−1}. Then for u ≤ i one has

∑_{j=v+1}^{p} q_{ij}^{0} = ∑_{k_{i−1}<j≤k_{i}} q_{ij}^{0} = ∑_{k_{i−1}<j≤k_{i}} n_{j} = m_{i},

and we obtain

∑_{i=u}^{r} ∑_{j=v+1}^{p} q_{ij} ≤ ∑_{i=u}^{r} m_{i} = ∑_{i=u}^{r} ∑_{j=v+1}^{p} q_{ij}^{0}.  (0.16)

The case of equality is easily studied : if equality holds in (0.15) for all (u, v) such that k_{u−1} ≤ v, this implies that q_{ij} = 0 for the upper part of zeros in the array (0.14). Similarly, if equality holds in (0.16) for all (u, v) such that k_{u−1} > v, this implies that q_{ij} = 0 for the lower part of zeros in the array (0.14). Because of (0.12), equality in (0.13) thus implies q_{ij} = q_{ij}^{0} for all (i, j) : Lemma 2 is proved.

Since S has the form (0.5) and since Σ has the form (0.1) for some U of O(n) then the matrix Q = U^{T} U_{0} is in O(n) and satisfies

trace (SΣ^{−1}) = trace (Q Diag(s_{1}I_{n_{1}}, …, s_{p}I_{n_{p}})Q^{T} Diag(\frac{1}{μ_{1}} I_{m_{1}}, …, \frac{1}{μ_{r}} I_{m_{r}})).  (0.17)

We write the orthogonal matrix Q by blocks Q_{ij} of n_{j} rows and m_{i} columns. Consider the matrix q = (q_{ij}) with r rows and p columns defined by q_{ij} = trace (Q_{ij}Q_{ij}^{T}). The equality (0.17) becomes

trace (SΣ^{−1}) = ∑_{j=1}^{p} ∑_{i=1}^{r} \frac{s_{j}}{μ_{i}} q_{ij}.  (0.18)

Now, the fact that Q is an orthogonal matrix implies that

Q^{T} Q = Diag(I_{n_{1}}, …, I_{n_{p}}), QQ^{T} = Diag(I_{m_{1}}, …, I_{m_{r}}),

from which one easily sees that (q_{ij}) satisfies (0.12). For instance, if Q is the identity matrix, or more generally, if Q belongs to the subgroup O(m), then the matrix q = (q_{ij}) is the matrix q^{0} defined in Lemma 2. Note also that the converse is true : if Q in O(n) is such that q = q^{0}, then Q is in O(m). Thus we have to show that (0.18) as a function of q reaches its minimum if and only if q = q^{0}. In order to prove this, we write for i = 1, …, r and j = 1, …, p :

\frac{1}{μ_{i}} = ∑_{u=1}^{i} a_{u}, s_{j} = ∑_{v=j}^{p} b_{v},

where the a_{u}’s and b_{v}’s are positive numbers (since the sequences (μ_{i}) and (s_{j}) are strictly decreasing). Then we obtain

∑_{j=1}^{p} ∑_{i=1}^{r} \frac{s_{j}}{μ_{i}} q_{ij} = ∑_{u=1}^{r} ∑_{v=1}^{p} a_{u}b_{v} ∑_{i=u}^{r} ∑_{j=1}^{v} q_{ij}

≥ ∑_{u=1}^{r} ∑_{v=1}^{p} a_{u}b_{v} ∑_{i=u}^{r} ∑_{j=1}^{v} q_{ij}^{0}  (0.19)

= ∑_{i=1}^{r} \frac{1}{μ_{i}} ∑_{k_{i−1}<j≤k_{i}} n_{j}s_{j}.

In this chain of equalities and inequalities, the crucial point (0.19) comes from Lemma 2. Clearly also from Lemma 2 the equality is reached if and only if Σ has the form (0.10) and Step 1 is completely proved. The above proof based on Lemma 2 is quite natural : we have been dealing with the bilinear form B(a, b) on (IR^{r}, IR^{p}) defined by

B(a, b) = ∑_{u=1}^{r} ∑_{v=1}^{p} a_{u}b_{v}c_{uv}

where c_{uv} = ∑_{i=u}^{r} ∑_{j=1}^{v}(q_{ij} − q_{ij}^{0}). But it is clear that such a bilinear form B(a, b) is non negative for all (a, b) in (0, ∞)^{r} × (0, ∞)^{p} if and only if c_{uv} ≥ 0 for all u and v.

Step 2 is rather trivial. For a > 0, define the function φ_{a} for x > 0 by φ_{a}(x) = log x + \frac{a}{x}. Thus by studying the variations of φ_{a} one has φ_{a}(x) ≥ φ_{a}(a), and the equality is reached if and only if x = a. Since (0.11) can be written

− ∑_{i=1}^{r} m_{i}φ_{μ_{i}^{0}}(μ_{i})

the proof of the first part of Theorem 1 is complete.

We now show (0.8). For this, we reformulate steps 1 and 2 in the following way. If Σ in M_{m} is given by (0.1), denote by k the class of U in the quotient O(n)/O(m) and denote by μ the decreasing sequence of the eigenvalues of Σ. Clearly, Σ depends only on the pair (μ, k) and we denote F (Σ) = F (μ, k). If (μ^{0}, k_{0}) are associated to Σ_{0} defined by (0.7), then steps 1 and 2 are rewritten by the two following inequalities

F (μ, k) ≤ F (μ, k_{0}) ≤ F (μ^{0}, k_{0}),  (0.20)

where equality is reached in the first only if k = k_{0} and in the second only if μ = μ^{0}.

In (0.8), only the only if part needs a proof. We suppose that lim_{t→∞} F (μ^{t}, k_{t}) = F (μ^{0}, k_{0}). From step 1, namely the first inequality in (0.20), this implies lim_{t→∞} F (μ^{t}, k_{0}) = F (μ^{0}, k_{0}). Now, clearly in step 2, for a sequence of positive numbers (x_{t})_{t≥1}, if we have lim_{t→∞} φ_{a}(x_{t}) = φ_{a}(a), then this implies lim_{t→∞} x_{t} = a. Thus lim_{t→∞} μ^{t} = μ^{0}.

Now, since the manifold O(n)/O(m) is compact, one can find a k_{0}^{∗} and a converging subsequence (k_{n_{t}}) such that lim_{t→∞} k_{n_{t}} = k_{0}^{∗}. Thus

lim_{t→∞} F (μ^{n_{t}}, k_{n_{t}}) = F (μ^{0}, k_{0}^{∗}).

This implies F (μ^{0}, k_{0}^{∗}) = F (μ^{0}, k_{0}). From the equality case in step 1 (see (0.20)) we get k_{0}^{∗} = k_{0}. This reasoning holds for any convergent subsequence (k_{n_{t}}) and we obtain lim_{t→∞} k_{t} = k_{0}, which completes the proof of (0.8).