# Expansions of the Characteristic Polynomial of a Perturbed Positive
Semidefinite Matrix and Convergence Analysis of Alternating Projections

Hiroyuki Ochiai  Institute of Mathematics for Industry, Kyushu University, 744
Motooka, Nishi-ku, Fukuoka 819-0395, Japan<EMAIL_ADDRESS><EMAIL_ADDRESS>,  Yoshiyuki Sekiguchi  Graduate School of Marine
Science and Technology, Etchujima 2-1-8, Koto-ku, Tokyo 135-8533, Japan
<EMAIL_ADDRESS>and  Hayato Waki

###### Abstract.

We observe that the characteristic polynomial of a linearly perturbed
semidefinite matrix can be used to give the convergence rate of alternating
projections for the positive semidefinite cone and a line. As a consequence,
we show that such alternating projections converge at $O(k^{-\frac{1}{2}})$,
independently of the singularity degree. A sufficient condition for the linear
convergence is also obtained. Our method directly analyzes the defining
equation for an alternating projection sequence and does not use error bounds.

###### Key words and phrases:

characteristic polynomial, positive semidefinite cone, Newton diagram,
alternating projection method, nontransversal intersection

###### 2010 Mathematics Subject Classification:

Primary 90C25, 41A25; Secondary 65K10

##  1\. Introduction

Let $\mathbb{S}^{n}$ and $\mathbb{S}^{n}_{+}$ be the sets of $n\times n$
symmetric matrices and positive semidefinite matrices respectively. For an
affine subspace $E$ of $\mathbb{S}^{n}$, the alternating projection method
constructs $\\{U_{k}\\}$ by $U_{k+1}=P_{E}\circ
P_{\mathbb{S}^{n}_{+}}(U_{k})$, where $P_{E}$ and $P_{\mathbb{S}^{n}_{+}}$ are
projections onto $E$ and $\mathbb{S}^{n}_{+}$ respectively. We consider the
case that $E\cap\mathbb{S}^{n}_{+}$ is nonempty. It is known that if $E$
intersects with $\mathbb{S}^{n}_{+}$ transversely, then $\\{U_{k}\\}$
converges linearly [1]. In addition, if $E$ intersects with
$\mathbb{S}^{n}_{+}$ nontransversely, then $\\{U_{k}\\}$ converges sublinearly
and an upper bound of the rate is given by the singularity degree of
$E\cap\mathbb{S}^{n}_{+}$ [3].

In this paper, we consider the case that $E$ is a line and
$E\cap\mathbb{S}^{n}_{+}$ is a singleton. For this case, we seek new upper
bounds for the convergence rate of $\\{U_{k}\\}$, and discuss the tightness of
the upper bound. To show the tightness, we can not use the previous results
using error bounds since we need a lower bound too. The key is the analytic
formula in Proposition 5.1 for the paremeters in $U_{k+1}$ and $U_{k}$, which
uses eigenvalues of the parametric expression of $U_{k}$. Although the
eigenvalues of a parametric matrix is hard to obtain, Proposition 5.1 is
useful for our case since the leading term of an eigenvalue of a one-parameter
matrix is efficiently determined by the Newton diagram associated with the
characteristic polynomial.

Thus we first obtain an expansion formula for the characteristic polynomial
(Proposition 3.2). Moreover, considering the Newton polytope of the
characteristic polynomial, we further expand the characteristic polynomial
using sums of squares of minors (Theorem 3.6) and obtain sufficient conditions
for the coefficients to be zero (Theorem 3.8). Then we show that the leading
term of every eigenvalue of a one-parameter perturbation of a positive
semidefinite matrix has degree less than or equal to $2$, by using the Newton
diagram (Theorem 4.1).

These results are applied to the convergence analysis of alternating
projections via Proposition 5.1. We show that $O(k^{-\frac{1}{2}})$ is an
upper bound for the convergence rate of the alternating projection method,
independently of the sigularity degree (Theorem 5.3). Moreover, if a submatrix
of the perturbing matrix satisfies a rank condition, then the alternate
projections converge linearly. We also show that the upper bound
$O(k^{-\frac{1}{2}})$ is tight if the sigularity degree is $2$ (Proposition
5.7).

The paper is organized as follows. Section 2 provides the basic notation and
some examples. The expansion formula for the characteristic polynomial for a
general matrix is given Section 3.1. Section 3.2 contains a formula for the
sum of the principal minors. The expansion formula for the characteristic
polynomial using the Newton polytope is obtained in Section 3.3. Section 4
deals with the convergence analysis of alternating projections.

##  2\. Preliminaries

For $n\times n$ symmetric matrices $U$ and $V$, $\langle
U,V\rangle=\mathop{\mathrm{missing}}{tr}(UV)$ and $\|U\|=\sqrt{\langle
U,U\rangle}$. Define the projection $P_{H}(U)$ of $U$ onto a subset $H$ of
$\mathbb{S}^{n}$ by $P_{H}(U)=\mathop{\mathrm{missing}}{argmin}_{X\in
H}\|X-U\|$.

We also consider a general $n\times m$ matrix $A$. Let $[n]=\\{1,\ldots,n\\}$.
For $\gamma\in[n]$, let $|\gamma|$ and $\\#\gamma$ be the sum of the elements
and the number of elements of $\gamma$, respectively. For
$\alpha\subset[m],\beta\subset[n]$, we denote by $A[\alpha,\beta]$ the
submatrix whose entries are those in the rows of $A$ indexed by $\alpha$ and
the columns of $A$ indexed by $\beta$. In the case $\alpha=\beta$, we simply
write $A[\alpha,\alpha]$ as $A[\alpha]$. For $N=\min\\{m,n\\}$, we denote by
$\sum_{N\times N}|A|^{2}$ the sum of the squares of $N\times N$ minors of $A$.
If $A$ is a square matrix, we denote by $\sum_{d\times d}|A|$ the sum of
$d\times d$ principal minors of $A$. We define $\sum_{0\times
0}|A|=\sum_{0\times 0}|A|^{2}=1$.

We define a compound matrix, a higher order adjugate matrix and other related
matrices. See [5, Section $0.8.1,\ 0.8.12$] for basic properties and examples
below.

Compound matrices. For $\alpha\subset[m]$, we denote by
$\langle\alpha\rangle_{k}$ the partially ordered set which consists of all the
subsets of $\alpha$ with $k$ elements and are ordered lexicographically. We
define $\langle m\rangle_{k}=\langle[m]\rangle_{k}$. For
$A\in\mathbb{R}^{m\times n}$ and $k\leq\min\\{m,n\\}$, the $k$-th compound
matrix $C_{k}(A)$ is the $\binom{m}{k}\times\binom{n}{k}$ matrix whose
$(\alpha,\beta)$ entry is

$C_{k}(A)_{\alpha,\beta}=\det A[\alpha,\beta]\ \text{for all }\alpha\in\langle
m\rangle_{k},\ \beta\in\langle n\rangle_{k}.$

We define $C_{0}(A)=1$ and $C_{k}(A)=0$ for $k<0$. For $d\leq
k\leq\min\\{m,n\\}$, we denote by $C_{k}^{d}(A)$ the
$\binom{m}{k}\times\binom{n}{k}$ matrix whose $(\alpha,\beta)$ entry is

$C_{k}^{d}(A)_{\alpha,\beta}=\sum_{d\times d}|A[\alpha,\beta]|\ \text{ for
}\alpha\in\langle m\rangle_{k},\ \beta\in\langle n\rangle_{k}.$

For $d<0$, we define $C_{k}^{d}(A)$ as the zero matrix of size
$\binom{m}{k}\times\binom{n}{k}$. In addition, for $m=n$, we define
$C_{k}^{0}(A)$ as the identity matrix of size $\binom{n}{k}$.

$k$-th adjugate matrices. For $m=n$ and $0<k<n$, the $k$-th adjugate matrix
$\mathrm{adj}_{k}(A)$ is the $\binom{n}{k}\times\binom{n}{k}$ matrix whose
$(\alpha,\beta)$ entry is

$\mathrm{adj}_{k}(A)_{\alpha,\beta}=(-1)^{|\alpha|+|\beta|}\det
A[\beta^{c},\alpha^{c}],\text{for all }\alpha,\beta\in\langle n\rangle_{k}.$

where $\alpha^{c}=[n]\setminus\alpha$. We see that $\mathrm{adj}_{0}(A)=\det
A$ and $\mathrm{adj}_{1}(A)$ is the standard adjugate matrix $\mathrm{adj}A$.
We define $\mathrm{adj}_{n}(A)=1$ and $\mathrm{adj}_{k}(A)=0$ for $k<0$. For
$m<n$, the adjugate vector $\mathrm{adjv}(A)$ is the $\binom{n}{n-m}$ row
vector whose entry is

$\mathrm{adjv}(A)_{\alpha}=(-1)^{|\alpha|}\det A[[m],\alpha^{c}],\text{ for
all }\alpha\in\langle n\rangle_{n-m}.$

For $m>n$, $\mathrm{adjv}(A)$ is similarly defined as the corresponding column
vector.

######  Example 2.1.

Let $A=\left(\begin{smallmatrix}a&b&c\\\ b&d&e\\\ c&e&f\\\
\end{smallmatrix}\right)$. Then $C_{1}(A)=A,\ C_{0}(A)=1,\ C_{3}(A)=\det B$,

$C_{2}(A)=\blockarray{cccc}[1,2]&[1,3][2,3]\\\
\block{(ccc)c}\begin{vmatrix}a&b\\\ b&d\end{vmatrix}\begin{vmatrix}a&c\\\
b&e\end{vmatrix}\begin{vmatrix}b&c\\\ d&e\end{vmatrix}[1,2]\\\
\begin{vmatrix}a&b\\\ c&e\end{vmatrix}\begin{vmatrix}a&c\\\
c&f\end{vmatrix}\begin{vmatrix}b&c\\\ e&f\end{vmatrix}[1,3]\\\
\begin{vmatrix}b&d\\\ c&e\end{vmatrix}\begin{vmatrix}b&e\\\
c&f\end{vmatrix}\begin{vmatrix}d&e\\\ e&f\end{vmatrix}[2,3]\\\ ,\quad
C_{2}^{1}(A)=\blockarray{cccc}[1,2]&[1,3][2,3]\\\
\block{(ccc)c}a+da+eb+e[1,2]\\\ a+ea+fb+f[1,3]\\\ b+eb+fd+f[2,3]\\\ $

$C_{2}^{2}(A)=C_{2}(A)$. Note that $C_{2}^{0}(A)$ is the identity matrix of
size $3$ and $C_{3}^{0}(A)=1$.

######  Example 2.2.

Let $A=\left(\begin{smallmatrix}a&b&c\\\ b&d&e\\\
c&e&f\end{smallmatrix}\right)$. Then $\mathrm{adj}_{0}(A)=\det A,\
\mathrm{adj}_{3}(A)=1$,

$\mathrm{adj}_{1}(A)=\blockarray{cccc}[1]&[2][3]\\\
\block{(ccc)c}\begin{vmatrix}d&e\\\ e&f\end{vmatrix}-\begin{vmatrix}b&c\\\
e&f\end{vmatrix}\begin{vmatrix}b&c\\\ d&e\end{vmatrix}[1]\\\
-\begin{vmatrix}b&c\\\ e&f\end{vmatrix}\begin{vmatrix}a&c\\\
c&f\end{vmatrix}-\begin{vmatrix}a&c\\\ b&e\end{vmatrix}[2]\\\
\begin{vmatrix}b&d\\\ c&e\end{vmatrix}-\begin{vmatrix}a&b\\\
c&e\end{vmatrix}\begin{vmatrix}a&b\\\ b&d\end{vmatrix}[3]\\\ ,\
\mathrm{adj}_{2}(A)=\blockarray{cccc}[1,2]&[1,3][2,3]\\\
\block{(ccc)c}f-ec[1,2]\\\ -ed-b[1,3]\\\ c-ba[2,3]\\\ .$

######  Example 2.3.

Let $A=\left(\begin{smallmatrix}a&b&c\\\ d&e&f\end{smallmatrix}\right)$. Then
$\mathrm{adjv}(A)=\left(\begin{vmatrix}b&c\\\ e&f\end{vmatrix},\
-\begin{vmatrix}a&c\\\ d&f\end{vmatrix},\ \begin{vmatrix}a&b\\\
d&e\end{vmatrix}\right)$.

##  3\. Characteristic polynomial

###  3.1. Expansion of the characteristic polynomial of a perturbed diagonal
matrix

We have the following expansion of the determinant for the general matrices
$A,B\in\mathbb{R}^{n\times n}$.

######  Lemma 3.1 ([5]).

$\det(A+tB)=\sum_{i=0}^{n}\langle\mathrm{adj}_{i}(A),C_{i}(B)\rangle t^{i}.$

By the definitions of $\mathrm{adj}_{i}(A)$ and $C_{i}(B)$, we see that

$\langle\mathrm{adj}_{i}(A),C_{i}(B)\rangle=\sum_{\alpha,\beta\in\langle
n\rangle_{i}}(-1)^{|\alpha|+|\beta|}\det A[\beta^{c},\alpha^{c}]\det
B[\alpha,\beta].$

Here, we use the convention $\det A[\emptyset,\emptyset]=1$. In particular, if
$A$ is diagonal, then $\mathrm{adj}_{j}(A)$ is also diagonal and we can write

$\langle\mathrm{adj}_{i}(A),C_{i}(B)\rangle=\sum_{\alpha\in\langle
n\rangle_{i}}\det A[\alpha^{c}]\det B[\alpha]=\sum_{\alpha\in\langle
n\rangle_{n-i}}\det A[\alpha]\det B[\alpha^{c}].$

A direct application of Lemma 3.1 to a diagonal matrix $A$ gives the following
proposition, which is needed in later sections. Recall that for
$B\in\mathbb{R}^{n\times n}$, we defined $C_{i+j}^{j}(B)=1$ for $j=0$ and
$C_{i+j}^{j}(B)=0$ for $j<0$.

######  Proposition 3.2.

For $m,n\in\mathbb{N}$ with $m<n$, and $p_{k}>0\ (k\in[n-m])$, let
$A=\mathrm{diag}(p_{1},\ldots,p_{n-m},0,\ldots,0)$, $B\in\mathbb{S}^{n}$. Then
the characteristic polynomial $p_{A+tB}(x)$ of $A+tB$ is written by

$p_{A+tB}(x)=\sum_{i=0}^{n}\sum_{j=m-i}^{n-i}(-1)^{n-i}\langle\mathrm{adj}_{i+j}(A),C_{i+j}^{j}(B)\rangle\,t^{j}x^{i}.$

###### Proof.

Let $I\in\mathbb{R}^{n\times n}$ be the identity matrix. By repeatedly
applying Lemma 3.1, we obtain

$\displaystyle p_{A+tB}(x)$ $\displaystyle=\det(xI-A-
tB)=\sum_{i=0}^{n}\langle\mathrm{adj}_{n-i}(xI),C_{n-i}(-A-tB)\rangle$
$\displaystyle=\sum_{i=0}^{n}(-1)^{n-i}\mathop{\mathrm{missing}}{tr}C_{n-i}(A+tB)x^{i}=\sum_{i=0}^{n}(-1)^{n-i}\sum_{\alpha\in\langle
n\rangle_{n-i}}\det((A+tB)[\alpha])x^{i}$
$\displaystyle=\sum_{i=0}^{n}(-1)^{n-i}\sum_{\alpha\in\langle
n\rangle_{n-i}}\sum_{j=0}^{n-i}\langle\mathrm{adj}_{j}(A[\alpha]),C_{j}(B[\alpha])\rangle
t^{j}x^{i}.$

Since $A=\mathrm{diag}(p_{1},\ldots,p_{n-m},0,\ldots,0)$, we see that
$\mathrm{adj}_{j}(A[\alpha])=O$ for $\\#\alpha\geq n-m+1$ and
$j=0,1,\ldots,\\#\alpha-n+m-1$. Thus if $\\#\alpha=n-i$ for some
$i=0,\ldots,m-1$, then $\mathrm{adj}_{j}(A[\alpha])=O$ for $j=0,\ldots,m-i-1$.
We recall that $\mathrm{adj}_{j}(A)=0$ and $C_{j}(A)=0$ for $j<0$. Then we
have

$\displaystyle p_{A+tB}(x)$
$\displaystyle=\left(\sum_{i=0}^{m-1}+\sum_{i=m}^{n}\right)(-1)^{n-i}\sum_{\alpha\in\langle
n\rangle_{n-i}}\sum_{j=0}^{n-i}\langle\mathrm{adj}_{j}(A[\alpha]),C_{j}(B[\alpha])\rangle
t^{j}x^{i}$ $\displaystyle=\sum_{i=0}^{m-1}(-1)^{n-i}\sum_{\alpha\in\langle
n\rangle_{n-i}}\sum_{j=m-i}^{n-i}\langle\mathrm{adj}_{j}(A[\alpha]),C_{j}(B[\alpha])\rangle
t^{j}x^{i}$ $\displaystyle\hskip
30.00005pt+\sum_{i=m}^{n}(-1)^{n-i}\sum_{\alpha\in\langle
n\rangle_{n-i}}\sum_{j=0}^{n-i}\langle\mathrm{adj}_{j}(A[\alpha]),C_{j}(B[\alpha])\rangle
t^{j}x^{i}$ $\displaystyle=\sum_{i=0}^{n}(-1)^{n-i}\sum_{\alpha\in\langle
n\rangle_{n-i}}\sum_{j=m-i}^{n-i}\langle\mathrm{adj}_{j}(A[\alpha]),C_{j}(B[\alpha])\rangle
t^{j}x^{i}$
$\displaystyle=\sum_{i=0}^{n}(-1)^{n-i}\sum_{j=m-i}^{n-i}\sum_{\alpha\in\langle
n\rangle_{n-i}}\langle\mathrm{adj}_{j}(A[\alpha]),C_{j}(B[\alpha])\rangle
t^{j}x^{i}.$

Let $i=0,\ldots,n,\ j=m-i,\ldots,n-i$ be fixed. To obtain the result, we will
show

(1) $\sum_{\alpha\in\langle
n\rangle_{n-i}}\langle\mathrm{adj}_{j}(A[\alpha]),C_{j}(B[\alpha])\rangle=\langle\mathrm{adj}_{i+j}(A),C_{i+j}^{j}(B)\rangle.$

Since $\mathrm{adj}_{j}(A[\alpha])$ is diagonal, the definition implies

$\langle\mathrm{adj}_{j}(A[\alpha]),C_{j}(B[\alpha])\rangle=\sum_{\beta\in\langle\alpha\rangle_{j}}\det(A[\alpha\setminus\beta])\det(B[\beta]).$

Since $A=\mathrm{diag}(p_{1},\ldots,p_{n-m},0,\ldots,0)$, for
$\beta\subset\alpha$, we have $\det(A[\alpha\setminus\beta])\neq 0$ if and
only if $\alpha\cap\\{n-m+1,\ldots,n\\}=\beta\cap\\{n-m+1,\ldots,n\\}$. Thus
by putting

$D=\\{(\alpha,\beta)\subset[n]\times[n]:\beta\subset\alpha,\ \\#\alpha=n-i,\
\\#\beta=j,\ \alpha\setminus[n-m]=\beta\setminus[n-m]\\},$

we can write

$\sum_{\alpha\in\langle
n\rangle_{n-i}}\langle\mathrm{adj}_{j}(A[\alpha]),C_{j}(B[\alpha])\rangle=\sum_{(\alpha,\beta)\in
D}\det(A[\alpha\setminus\beta])\det(B[\beta]).$

Let

$D^{\prime}=\\{(\gamma,\beta)\subset[n]\times[n]:\gamma\subset[n-m],\
\beta\subset[n]\setminus\gamma,\ \\#\gamma=n-i-j,\ \\#\beta=j\\}.$

Then $(\alpha,\beta)\in D$ if and only if $(\alpha\setminus\beta,\beta)\in
D^{\prime}$. Thus we have

$\displaystyle\sum_{(\alpha,\beta)\in
D}\det(A[\alpha\setminus\beta])\det(B[\beta])=\sum_{(\gamma,\beta)\in
D^{\prime}}\det(A[\gamma])\det(B[\beta])$
$\displaystyle=\sum_{\overset{\gamma\subset[n-m]}{\\#\gamma=n-i-j}}\sum_{\overset{\beta\subset[n]\setminus\gamma}{\\#\beta=j}}\det(A[\gamma])\det(B[\beta])=\sum_{\gamma\in\langle
n-m\rangle_{n-i-j}}\det(A[\gamma])\sum_{j\times
j}\begin{vmatrix}B[\gamma^{c}]\end{vmatrix}.$

Now the diagonality of $\mathrm{adj}_{i+j}(A)$ and the definition of
$C_{i+j}^{j}(B)$ give that

$\langle\mathrm{adj}_{i+j}(A),C_{i+j}^{j}(B)\rangle=\sum_{\alpha\in\langle
n\rangle_{i+j}}\det(A[\alpha^{c}])\sum_{j\times
j}\begin{vmatrix}B[\alpha]\end{vmatrix}.$

Since $\det(A[\alpha^{c}])=0$ if
$\alpha\cap\\{n-m+1,\ldots,n\\}\neq\emptyset$, we obtain

$\sum_{\alpha\in\langle n\rangle_{i+j}}\det(A[\alpha^{c}])\sum_{j\times
j}\begin{vmatrix}B[\alpha]\end{vmatrix}=\sum_{\gamma\in\langle
n-m\rangle_{n-i-j}}\det(A[\gamma])\sum_{j\times
j}\begin{vmatrix}B[\gamma^{c}]\end{vmatrix}.$

Therefore, we have shown the equation $(\ref{eq:adjcomp})$. This completes the
proof. ∎

######  Example 3.3.

For $p,q>0$, let

$A=\begin{pmatrix}p&0&0&0\\\ 0&q&0&0\\\ 0&0&0&0\\\ 0&0&0&0\end{pmatrix},\quad
B=\begin{pmatrix}a&b&c&d\\\ b&e&f&g\\\ c&f&h&i\\\ d&g&i&j\end{pmatrix}$

Then Proposition 3.2 implies that $p_{A+tB}(x)$ is given as

$\displaystyle x^{4}-\left((a+e+h+j)t+p+q\right)x^{3}+\left(\sum_{2\times
2}\begin{vmatrix}B\end{vmatrix}t^{2}+\left(p(e+h+j)+q(a+h+j)\right)t+pq\right)x^{2}$
$\displaystyle-\left(\sum_{3\times
3}\begin{vmatrix}B\end{vmatrix}t^{3}+\left(p\sum_{2\times
2}\begin{vmatrix}e&f&g\\\ f&h&i\\\ g&i&j\end{vmatrix}+q\sum_{2\times
2}\begin{vmatrix}a&c&d\\\ c&h&i\\\
d&i&j\end{vmatrix}\right)t^{2}+pq(h+j)t\right)x$
$\displaystyle+\begin{vmatrix}B\end{vmatrix}t^{4}+\left(p\begin{vmatrix}e&f&g\\\
f&h&i\\\ g&i&j\end{vmatrix}+q\begin{vmatrix}a&c&d\\\ c&h&i\\\
d&i&j\end{vmatrix}\right)t^{3}+pq\begin{vmatrix}h&i\\\ i&j\end{vmatrix}t^{2}.$

###  3.2. The sum of the principal minors

We further expand an entry of $C_{i+j}^{j}(B)$ in the expansion in Proposition
3.2, which is the sum of principal minors. For $m,\ell\in\mathbb{N}$, consider
the matrix

(2)
$M=\begin{array}[b]{cl}\phantom{(}\begin{array}[]{cc}\mathmakebox[1em]{\ell}&\mathmakebox[3em]{m}\end{array}\phantom{)}&\\\
\left(\begin{array}[]{@{}c@{\,}|ccc}M_{11}&&M_{12}&\\\ \hline\cr\\\
M_{21}&&M_{22}\\\ &\end{array}\right)&\begin{array}[]{l}\ell\\\ \\\ m\\\
\phantom{1}\end{array}\end{array}.$

We assume $M_{22}=CDF$, where $r\in\mathbb{N}\cap\\{0\\}$ with $r+\ell\leq m$,
$C\in\mathbb{R}^{m\times r}$, $D\in\mathbb{R}^{r\times r}$,
$F\in\mathbb{R}^{r\times m}$. Here, we note
$\mathop{\mathrm{missing}}{rank}(CDF)\leq r$. We put

(3)
$X=\begin{array}[b]{cl}\phantom{(}\begin{array}[]{ccc}\mathmakebox[1em]{\ell}&\mathmakebox[1em]{\ell}&\mathmakebox[1em]{r}\end{array}\phantom{)}&\\\
\left(\begin{array}[]{@{\,}c|@{\,}c@{\,}|c@{\,}}I&O&O\\\
\hline\cr&&\\\\[3.59995pt] O&M_{21}&C\\\\[3.59995pt]
&&\end{array}\right)&\begin{array}[]{l}\ell\\\ \\\\[3.59995pt]
m\\\\[3.59995pt] \phantom{1}\end{array}\end{array},\
Y=\begin{array}[b]{cl}\phantom{(}\begin{array}[]{ccc}\hskip
4.5pt\mathmakebox[1em]{\ell}&\mathmakebox[1em]{\ell}&\mathmakebox[1em]{r}\end{array}\phantom{)}&\\\
\left(\begin{array}[]{@{\,}c@{\,}|c|c@{\,}}M_{11}&I&O\\\ \hline\cr I&O&O\\\
\hline\cr O&O&D\end{array}\right)&\begin{array}[]{l}\ell\\\ \ell\\\
r\end{array}\end{array},\
Z=\begin{array}[b]{cl}\phantom{(}\begin{array}[]{cc}\mathmakebox[1em]{\ell}&\mathmakebox[3em]{m}\end{array}\phantom{)}&\\\
\left(\begin{array}[]{c|ccc}I&&O&\\\ \hline\cr O&&M_{12}&\\\ \hline\cr
O&&F&\end{array}\right)&\begin{array}[]{l}\ell\\\ \ell\\\
r\end{array}\end{array}.$

In the case $r=0$, there are no blocks corresponding to $C,D$ or $F$. Then we
obtain $M=XYZ$. With this relation, we have the following factorization for
the $(m-r-\ell)$-th adugate matrix of $M$.

######  Lemma 3.4.

In case $r>0$, let

$\widetilde{M}=(-1)^{\ell}\det
D\cdot\mathrm{adjv}\left(\begin{array}[]{@{}c@{\,}c@{}}\\\ M_{21}&C\\\
\phantom{1}\end{array}\right)\mathrm{adjv}\left(\begin{array}[]{ccc}&M_{12}&\\\
&F&\end{array}\right)\in\mathbb{R}^{\binom{m}{r+\ell}\times\binom{m}{r+\ell}}.$

Then

$\mathrm{adj}_{m-r-\ell}(M)=\begin{pmatrix}O&O\\\
O&\widetilde{M}\end{pmatrix}\in\mathbb{R}^{\binom{m+\ell}{r+2\ell}\times\binom{m+\ell}{r+2\ell}}.$

In case $r=0$, the same equality holds for
$\widetilde{M}=(-1)^{\ell}\mathrm{adjv}\begin{pmatrix}M_{21}\end{pmatrix}\mathrm{adjv}\begin{pmatrix}M_{12}\end{pmatrix}$.

###### Proof.

Suppose $r>0$. Recall that $X\in\mathbb{R}^{(m+\ell)\times(r+2\ell)}$,
$Z\in\mathbb{R}^{(r+2\ell)\times(m+\ell)}$ and $r+\ell\leq m$. Then
$r+2\ell\leq m+\ell$. For $\alpha,\beta\in\langle m+\ell\rangle_{m-r-\ell}$,
we see that

$M\left[\beta^{c},\alpha^{c}\right]=X[\beta^{c},[r+2\ell]]\,Y\,Z[[r+2\ell],\alpha^{c}].$

Note that $\\#(\alpha^{c})=\\#(\beta^{c})=r+2\ell$. Since $\det
Y=(-1)^{\ell}\det D$, we obtain

$\det M\left[\beta^{c},\alpha^{c}\right]=(-1)^{\ell}\det D\cdot\det
X[\beta^{c},[r+2\ell]]\cdot\det Z[[r+2\ell],\alpha^{c}].$

If $\alpha\cap[\ell]=\emptyset$, then

$\det Z[[r+2\ell],\alpha^{c}]=\det\left(\left(\begin{array}[]{ccc}&M_{12}&\\\
&F&\end{array}\right)[[r+\ell],\alpha^{c}\setminus[\ell]]\right).$

If $\alpha\cap[\ell]\neq\emptyset$, then $\det Z[[r+2\ell],\alpha^{c}]=0$.
Similar relations hold for $X[\beta^{c},[r+2\ell]]$. Therefore, if
$\alpha\cap[\ell]=\emptyset$ and $\beta\cap[\ell]=\emptyset$, then we obtain

$\displaystyle\det M\left[\beta^{c},\alpha^{c}\right]$
$\displaystyle=(-1)^{\ell}\det
D\cdot\det\left(\left(\begin{array}[]{@{}c@{\,}c@{}}\\\ M_{21}&C\\\
\phantom{1}\end{array}\right)[\beta^{c}\setminus[\ell],[r+\ell]]\right)\cdot\det\left(\left(\begin{array}[]{ccc}&M_{12}&\\\
&F&\end{array}\right)[[r+\ell],\alpha^{c}\setminus[\ell]]\right).$

Since $(-1)^{|\alpha|+|\beta|}\det M\left[\beta^{c},\alpha^{c}\right]$ is
$(\alpha,\beta)$-entry of $\mathrm{adj}_{m-r-\ell}(M)$, we have the equality.

In case $r=0$, we have $M=\left(\begin{smallmatrix}I&O\\\
O&M_{21}\end{smallmatrix}\right)\left(\begin{smallmatrix}M_{11}&I\\\
I&O\end{smallmatrix}\right)\left(\begin{smallmatrix}I&O\\\
O&M_{12}\end{smallmatrix}\right)$ and similar arguments for this relation give
the result. ∎

We consider a symmetric matrix $M$ satisfying the following assumptions;

######  Assumptions ($*$).

  1. (i)

$M\in\mathbb{S}^{\ell+m}$ is a matrix partitioned as $(\ref{eq:partition})$
for some $\ell,m\in\mathbb{N}$ with $M_{11}\in\mathbb{S}^{\ell}$ and
$M_{12}=M_{21}^{T}$;

  2. (ii)

$M_{21}=\begin{pmatrix}b_{1}&\cdots&b_{\ell}\end{pmatrix}\in\mathbb{R}^{m\times\ell}$
for some $b_{k}\in\mathbb{R}^{m}\ (k\in[\ell])$;

  3. (iii)

$M_{22}=CDC^{T}$ for some $r\in\mathbb{N}\cup\\{0\\}$,
$C=\begin{pmatrix}c_{1}&\cdots&c_{r}\end{pmatrix}\in\mathbb{R}^{m\times r}$,
$D=\mathrm{diag}(u_{1},\ldots,u_{r})$, $u_{k}\in\mathbb{R}\ (k\in[r])$;

  4. (iv)

$r+\ell\leq m$.

We see $CDC^{T}=\sum_{k=1}^{r}u_{k}c_{k}c_{k}^{T}$. Note that (i), (ii), (iii)
give notation and (iv) is the required property.

######  Proposition 3.5.

Let $M\in\mathbb{S}^{\ell+m}$ satisfy the assumptions $(*)$. In case $r>0$, we
have

$\sum_{(r+2\ell)\times(r+2\ell)}|M|=(-1)^{\ell}u_{1}\cdots
u_{r}\sum_{(r+\ell)\times(r+\ell)}\begin{vmatrix}b_{1}&\cdots&b_{\ell}&c_{1}&\cdots&c_{r}\end{vmatrix}^{2}.$

In case $r=0$, we have $\sum_{2\ell\times
2\ell}|M|=(-1)^{\ell}\sum_{\ell\times\ell}\begin{vmatrix}b_{1}&\cdots&b_{\ell}\end{vmatrix}^{2}$.

###### Proof.

If $r>0$, Lemma 3.4 implies that
$\mathrm{adj}_{m-r-\ell}(M)=\left(\begin{smallmatrix}O&O\\\
O&\widetilde{M}\end{smallmatrix}\right)$, where

$\widetilde{M}=(-1)^{\ell}\det
D\cdot\mathrm{adjv}\begin{pmatrix}M_{21}&C\end{pmatrix}\mathrm{adjv}\begin{pmatrix}M_{21}^{T}\\\
C^{T}\end{pmatrix}.$

By the definitions, we see that the entries of $\mathrm{adj}_{m-r-\ell}(M)$
are minors of size $r+2\ell$, and that the entries of the column vector
$\mathrm{adjv}\begin{pmatrix}M_{21}&C\end{pmatrix}$ and the row vector
$\mathrm{adjv}\begin{pmatrix}M_{21}^{T}\\\ C^{T}\\\ \end{pmatrix}$ are minors
of size $r+\ell$. Since
$\sum_{(r+2\ell)\times(r+2\ell)}|M|=\mathop{\mathrm{missing}}{tr}\mathrm{adj}_{m-r-\ell}(M)=\mathop{\mathrm{missing}}{tr}\widetilde{M}$,
we obtain the desired equality. The case $r=0$ is shown similarly. ∎

###  3.3. The Newton polytope

$\gamma_{1}$$\gamma_{2}$$m$$m$$n$$n$$2m-r$$E_{1}$$E_{2}$$E_{3}$$(r,m-r)$

$\gamma_{1}$$\gamma_{2}$$m$$m$$n$$n$$Q$$E_{1}$$E_{2}$$E_{3}$$(r,m-r)$

Figure 1. $D_{0}$ and the Newton polytope, where $Q$ is $(2n-2m+r,2m-r-n)$.
The left and the right figures correspond to the case $m-r<n-m$ and to the
case $m-r>n-m$ respectively.

In this section, we will show that the coefficients of the expansion in
Proposition 3.2 are simplified if the terms correspond to some points on the
boundary of the Newton polytope of the characteristic polynomial. For a
$k$-variable polynomial
$f(x)=\sum_{\gamma}f_{\gamma}x^{\gamma}\in\mathbb{R}[x]$ where
$x^{\gamma}=x_{1}^{\gamma_{1}}\cdots x_{k}^{\gamma_{k}}$, let
$\mathrm{supp}f=\\{\gamma\in\mathbb{Z}^{k}:f_{\gamma}\neq 0\\}$. Then the
convex hull of $\mathrm{supp}f$ is called the Newton polytope of $f$.

For $m,n\in\mathbb{N}$ with $m<n$, and $p_{k}>0\ (k\in[n-m])$, let
$A=\mathrm{diag}(p_{1},\ldots,p_{n-m},0,\ldots,0)$, $B\in\mathbb{S}^{n}$. We
define $D_{0}=\\{\gamma\in\mathbb{Z}^{2}:0\leq\gamma_{1}\leq n,\
m\leq\gamma_{1}+\gamma_{2}\leq n\\}$. Then Proposition 3.2 gives that

$p_{A+tB}(x)=\sum_{\gamma\in
D_{0}}(-1)^{n-\gamma_{2}}\langle\mathrm{adj}_{|\gamma|}(A),C_{|\gamma|}^{\gamma_{1}}(B)\rangle
t^{\gamma_{1}}x^{\gamma_{2}},$

where $|\gamma|=\gamma_{1}+\gamma_{2}$. Let $d_{\gamma}$ be the coefficient of
$t^{\gamma_{1}}x^{\gamma_{2}}$ in $p_{A+tB}(x)$. We will further calculate
$d_{\gamma}$. Suppose that $B$ is partitioned as

(4)
$B=\begin{array}[b]{cl}\phantom{(}\begin{array}[]{ll}\mathmakebox[2em]{n-m}&\mathmakebox[2em]{m}\end{array}\phantom{)}&\\\
\left(\begin{array}[]{c|c}B_{11}&B_{21}^{T}\\\ \hline\cr
B_{21}&B_{22}\end{array}\right)&\begin{array}[]{l}n-m\\\
m\end{array}\end{array},$

and $B_{22}=CDC^{T}$ for some $r\in\mathbb{N}$,
$C=\begin{pmatrix}c_{1}&\cdots&c_{r}\end{pmatrix}\in\mathbb{R}^{m\times
r}\setminus\\{O\\}$, $D=\mathrm{diag}(u_{1},\ldots,u_{r})$,
$u_{k}\in\mathbb{R}\setminus\\{0\\}\ (k\in[r])$. Note that
$\mathop{\mathrm{missing}}{rank}B_{22}=r$. In the following Theorem, the
expressions in (i), (ii), (iii) and (iv) correspond to the cases that $\gamma$
is on the edge $E_{1}$, $E_{2}$, $E_{3}$ and below the edge $E_{3}$ in Figure
1, respectively. Recall that we defined $\sum_{0\times 0}|A|=1$.

######  Theorem 3.6.

  1. (i)

If $\gamma=\begin{pmatrix}0\\\ n\end{pmatrix}+\eta\begin{pmatrix}0\\\
-1\end{pmatrix},\ \eta=0,\ldots,n-m$, then
$d_{\gamma}=(-1)^{\eta}\sum_{\eta\times\eta}|A|.$

  2. (ii)

If $\gamma=\begin{pmatrix}0\\\ m\end{pmatrix}+\eta\begin{pmatrix}1\\\
-1\end{pmatrix},\ \eta=1,\ldots,r$, then

$d_{\gamma}=(-1)^{n-m+\eta}\cdot p_{1}\cdots
p_{n-m}\cdot\sum_{\eta\times\eta}\begin{vmatrix}B_{22}\end{vmatrix}.$

  3. (iii)

If $r>0$ and $\gamma=\begin{pmatrix}r\\\
m-r\end{pmatrix}+\mu\begin{pmatrix}2\\\ -1\end{pmatrix},\
\mu=1,\ldots,\min\\{m-r,n-m\\}$, then

$\displaystyle d_{\gamma}$ $\displaystyle=(-1)^{n-m+r+2\mu}\cdot u_{1}\cdots
u_{r}\cdot$
$\displaystyle\sum_{\\{k_{1},\ldots,k_{\mu}\\}\subset[n-m]}\prod_{k\in[n-m]\setminus\\{k_{1},\ldots,k_{\mu}\\}}p_{k}\sum_{(r+\mu)\times(r+\mu)}\begin{vmatrix}b_{k_{1}}&\cdots&b_{k_{\mu}}&c_{1}&\cdots&c_{r}\end{vmatrix}^{2}.$

If $r=0$, then $u_{1}\cdots u_{r}$ is replaced by $1$ in the equality above.

  4. (iv)

If $\gamma=\begin{pmatrix}r\\\ m-r\end{pmatrix}+\eta\begin{pmatrix}1\\\
-1\end{pmatrix}+\mu\begin{pmatrix}2\\\ -1\end{pmatrix},\
\mu=0,\ldots,\min\\{m-r,n-m\\}-1,\ \eta=1,\ldots,m-r-\mu$, then
$d_{\gamma}=0$.

###### Proof.

Since
$d_{\gamma}=(-1)^{n-\gamma_{2}}\langle\mathrm{adj}_{|\gamma|}(A),C_{|\gamma|}^{\gamma_{1}}(B)\rangle$,
we calculate
$\langle\mathrm{adj}_{|\gamma|}(A),C_{|\gamma|}^{\gamma_{1}}(B)\rangle$.

(i) Since $\gamma_{1}=0$, we have that $C_{|\gamma|}^{\gamma_{1}}(B)$ is the
identity matrix and hence
$\langle\mathrm{adj}_{|\gamma|}(A),C_{|\gamma|}^{\gamma_{1}}(B)\rangle=\mathop{\mathrm{missing}}{tr}\mathrm{adj}_{|\gamma|}(A)=\mathop{\mathrm{missing}}{tr}\mathrm{adj}_{n-\eta}(A)=\sum_{\eta\times\eta}|A|$.

(ii) Since $|\gamma|=m$, we see that an entry of
$\mathrm{adj}_{|\gamma|}(A)=\mathrm{adj}_{m}(A)$ is a cofactor of size $n-m$.
Since $A=\mathrm{diag}(p_{1},\ldots,p_{n-m},0,\ldots,0)$, the unique nonzero
entry of the diagonal matrix $\mathrm{adj}_{m}(A)$ is $\det
A\big{[}\\{1,\ldots,n-m\\}\big{]}=p_{1}\cdots p_{n-m}$. If $\eta\neq 0$, then
$C_{|\gamma|}^{\gamma_{1}}(B)\big{[}\\{n-m+1,\ldots,n\\}\big{]}=\sum_{\gamma_{1}\times\gamma_{1}}\begin{vmatrix}B\big{[}\\{n-m+1,\ldots,n\\}\big{]}\end{vmatrix}=\sum_{\eta\times\eta}\begin{vmatrix}B_{22}\end{vmatrix}$.
If $\eta=0$, then
$C_{|\gamma|}^{\gamma_{1}}(B)\big{[}\\{n-m+1,\ldots,n\\}\big{]}=1$.

(iii) Note that $n-m-\mu\geq n-m-\min\\{m-r,n-m\\}\geq\max\\{n-2m+r,0\\}\geq
0$ and that an entry of $\mathrm{adj}_{|\gamma|}(A)=\mathrm{adj}_{m+\mu}(A)$
is a cofactor of size $n-m-\mu$. Since
$A=\mathrm{diag}(p_{1},\ldots,p_{n-m},0,\ldots,0)$, a nonzero entry of
$\mathrm{adj}_{m+\mu}(A)$ is given as

$\det
A\big{[}[n-m]\setminus\\{k_{1},\ldots,k_{\mu}\\}\big{]}=\prod_{k\in[n-m]\setminus\\{k_{1},\ldots,k_{\mu}\\}}p_{k},$

where $\\{k_{1},\ldots,k_{\mu}\\}\subset[n-m]$. Then the corresponding entry
of $C_{|\gamma|}^{\gamma_{1}}(A)=C_{m+\mu}^{r+2\mu}(B)$ to
$A\big{[}[n-m]\setminus\\{k_{1},\ldots,k_{\mu}\\}\big{]}$ is

(5)
$\displaystyle\sum_{(r+2\mu)\times(r+2\mu)}\begin{vmatrix}B\big{[}\\{k_{1},\ldots,k_{\mu},n-m+1,\ldots,n\\}\big{]}\end{vmatrix}$
$\displaystyle=\sum_{(r+2\mu)\times(r+2\mu)}\begin{vmatrix}&&&&b_{k_{1}}^{T}&\\\
&B[\\{k_{1},\ldots,k_{\mu}\\}]&&&\vdots&\\\ &&&&b_{k_{\mu}}^{T}&\\\ &&&&\\\
b_{k_{1}}&\cdots&b_{k_{\mu}}&&CDC^{T}&&&&\end{vmatrix}.$

Here, we see that $B\big{[}\\{k_{1},\ldots,k_{\mu},n-m+1,\ldots,n\\}\big{]}$
satisfies the assumptions $(*)$ since $r+\mu\leq m$ and the matrix has size
$m+\mu$. Thus Proposition 3.5 implies that $(\ref{eq:sum_minors})$ is equal to

$(-1)^{\mu}u_{1}\cdots
u_{r}\sum_{(r+\mu)\times(r+\mu)}\begin{vmatrix}b_{k_{1}}&\cdots&b_{k_{\mu}}&c_{1}&\cdots&c_{r}\end{vmatrix}^{2}.$

(iv) Since $|\gamma|=m+\mu$, a nonzero entry of $\mathrm{adj}_{|\gamma|}(A)$
is the one obtained in the proof of (iii). The corresponding entry of
$C_{|\gamma|}^{\gamma_{1}}(B)=C_{m+\mu}^{r+2\mu+\eta}(B)$ is

(6)
$\sum_{(r+2\mu+\eta)\times(r+2\mu+\eta)}\begin{vmatrix}B\big{[}\\{k_{1},\ldots,k_{\ell},n-m+1,\ldots,n\\}\big{]}\end{vmatrix},$

which is the sum of the principal minors of
$B\big{[}\\{k_{1},\ldots,k_{\mu},n-m+1,\ldots,n\\}\big{]}$ of size
$r+2\mu+\eta$, while the proof of (iii) considers the principal minors of the
same matrix of size $r+2\mu$. Since
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}b_{k_{1}}&\cdots&b_{k_{\mu}}&CDC^{T}\end{pmatrix}\leq
r+\mu$, we see that

$\mathop{\mathrm{missing}}{rank}B\big{[}\\{k_{1},\ldots,k_{\mu},n-m+1,\ldots,n\\}\big{]}\leq\mu+r+\mu<r+2\mu+\eta.$

Thus all summands of $(\ref{eq:sum_minors0})$ are zero. Therefore, we obtain
$\langle\mathrm{adj}_{|\gamma|}(A),C_{|\gamma|}^{\gamma_{1}}(B)\rangle=0$.

∎

######  Example 3.7.

For $A,B$ in Example 3.3, we further assume that $\begin{pmatrix}h&i\\\
i&j\end{pmatrix}=u_{1}\begin{pmatrix}h_{1}\\\
i_{1}\end{pmatrix}\begin{pmatrix}h_{1}&i_{1}\end{pmatrix}.$ Then Theorem 3.6
gives

$p_{A+tB}(x)=x^{4}-\left(p+q+O(t)\right)x^{3}+(pq+O(t))x^{2}-\left(pqu_{1}(h_{1}^{2}+i_{1}^{2})t+O(t^{2})\right)x\\\
+u_{1}\left(p\begin{vmatrix}f&g\\\
h_{1}&i_{1}\end{vmatrix}^{2}+q\begin{vmatrix}c&d\\\
h_{1}&i_{1}\end{vmatrix}^{2}\right)t^{3}+\begin{vmatrix}B\end{vmatrix}t^{4}.$

Next, we consider the case that there exists $\gamma$ in the case (iii) of
Theorem 3.6 such that
$\langle\mathrm{adj}_{|\gamma|}(A),C_{|\gamma|}^{\gamma_{1}}(B)\rangle=0$. In
this case, the theorem below shows that all the terms of $p_{A+tB}$
corresponding to the points that are located right and lower to $\gamma$ in
the plane of the Newton polytope are zero.

$\gamma_{1}$$\gamma_{2}$$n$$m$$E_{1}$$E_{2}$$E_{3}$$(r,m-r)$$(r+2\tilde{\mu},m-r-\tilde{\mu})$
Figure 2. the Newton polytope in a degenerate case

######  Theorem 3.8.

Let $\tilde{\mu}\in[\min\\{m-r,n-m\\}]$. Then $d_{\tilde{\gamma}}=0$ for
$\tilde{\gamma}=\begin{pmatrix}r\\\
m-r\end{pmatrix}+\tilde{\mu}\begin{pmatrix}2\\\ -1\end{pmatrix}$ if and only
if
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}<r+\tilde{\mu}$.
In this case, we have $d_{\gamma}=0$ for $\gamma=\begin{pmatrix}r\\\
m-r\end{pmatrix}+\mu\begin{pmatrix}2\\\ -1\end{pmatrix}+\nu\begin{pmatrix}1\\\
0\end{pmatrix},\ \mu=\tilde{\mu},\ldots,\min\\{m-r,n-m\\},\
\nu=0,1,\ldots,n-m-\mu$.

###### Proof.

If
$d_{\tilde{\gamma}}=(-1)^{n-\tilde{\gamma}_{2}}\langle\mathrm{adj}_{|\tilde{\gamma}|}(A),C_{|\tilde{\gamma}|}^{\tilde{\gamma}_{1}}(B)\rangle=0$,
then (iii) of Theorem 3.6 gives that

$\sum_{(r+\tilde{\mu})\times(r+\tilde{\mu})}\begin{vmatrix}b_{k_{1}}&\cdots&b_{k_{\tilde{\mu}}}&c_{1}&\cdots&c_{r}\end{vmatrix}^{2}=0$

and hence
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}b_{k_{1}}&\cdots&b_{k_{\tilde{\mu}}}&c_{1}&\cdots&c_{r}\end{pmatrix}<r+\tilde{\mu}$
for all $\\{k_{1},\ldots,k_{\tilde{\mu}}\\}\subset[n-m]$. Suppose
$q:=\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}\geq
r+\tilde{\mu}$. Since $c_{1},\ldots,c_{r}$ are linearly independent and span
the column space of $B_{22}$, there are $q-r$ column vectors
$b^{\prime}_{k_{1}},\ldots,b^{\prime}_{k_{q-r}}$ of $B_{21}$ such that
$c_{1},\ldots,c_{r},b^{\prime}_{k_{1}},\ldots,b^{\prime}_{k_{q-r}}$ form a
basis for the column space of $\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}$.
Since $q-r\geq\tilde{\mu}$, we have
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}b^{\prime}_{k_{1}}&\cdots&b^{\prime}_{k_{\tilde{\mu}}}&c_{1}&\cdots&c_{r}\end{pmatrix}=r+\tilde{\mu}$.
Thus
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}\geq
r+\tilde{\mu}$. The converse is obvious.

Next, suppose
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}<r+\tilde{\mu}$.
For $\mu=\tilde{\mu},\ldots,\min\\{m-r,n-m\\}$, $\nu=0,1,\ldots,n-m-\mu$, an
entry of $\mathrm{adj}_{|\gamma|}(A)=\mathrm{adj}_{m+\mu+\nu}(A)$ is a
cofactor of size $n-m-\mu-\nu$. Since
$A=\mathrm{diag}(p_{1},\dots,p_{n-m},0,\ldots,0)$, a nonzero entry of
$\mathrm{adj}_{m+\mu+\nu}(A)$ is given as

$\det
A\big{[}[n-m]\setminus\\{k_{1},\ldots,k_{\mu+\nu}\\}\big{]}=\prod_{k\in[n-m]\setminus\\{k_{1},\ldots,k_{\mu+\nu}\\}}p_{k}$

for some $\\{k_{1},\ldots,k_{\mu+\nu}\\}\subset[\min\\{m-r,n-m\\}]$. The
corresponding entry of
$C_{|\gamma|}^{\gamma_{1}}=C_{m+\mu+\nu}^{r+2\mu+\nu}(B)$ is

(7)
$\sum_{(r+2\mu+\nu)\times(r+2\mu+\nu)}\begin{vmatrix}B\big{[}\\{k_{1},\ldots,k_{\mu+\nu},n-m+1,\ldots,n\\}\big{]}\end{vmatrix}.$

Since
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}<r+\tilde{\mu}$,
we have

$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B\big{[}\\{k_{1},\ldots,k_{\mu+\nu},n-m+1,\ldots,n\\}\big{]}\end{pmatrix}<r+\tilde{\mu}+\mu+\nu\leq
r+2\mu+\nu.$

Thus all summands in $(\ref{eq:sum_minors1})$ are zero. Therefore, we obtain
$d_{\gamma}=(-1)^{n-\gamma_{2}}\langle\mathrm{adj}_{|\gamma|}(A),C_{|\gamma|}^{\gamma_{1}}(B)\rangle=0$.
∎

######  Example 3.9.

Consider $p_{A+tB}(x)$ in Example 3.7. If the coefficients
$d_{(1,0)}=pu_{1}\left|\begin{smallmatrix}f&g\\\
h_{1}&i_{1}\end{smallmatrix}\right|^{2}+qu_{1}\left|\begin{smallmatrix}c&d\\\
h_{1}&i_{1}\end{smallmatrix}\right|^{2}=0$, then
$d_{(2,0)}=\begin{vmatrix}B\end{vmatrix}=0.$

##  4\. Leading terms of eigenvalues and the method of the Newton diagram

For $A,B\in\mathbb{S}^{n}$ and a characteristic polynomial $p_{A+tB}(x)$, we
consider the Newton diagram constructed in the following way. First, draw the
the Newton polytope of $p_{A+tB}$ as a polynomial in $(t,x)$. Second,
translate this Newton polytope so that the point $(0,n)$ coincides with the
origin, and rotate it by $90^{\circ}$ degree. Finally, extend the line segment
containing the right most point until it intersects with the line
$\gamma_{2}=n$. The obtained diagram is called the Newton diagram associated
with $p_{A+tB}(x)$. Figure 3 is the Newton diagram constructed from the Newton
polytope in Figure 2.

It is well-known that the slope $d$ of the edge $\Gamma$ of the Newton diagram
coincides with the leading degree of $k$ eigenvalues of $p_{A+tB}$, where $k$
is the length of the projection of $\Gamma$ onto $\gamma_{2}$ axis. In
addition, for $f(t,x)=p_{A+tB}(x)$, we write
$f(t,x)=\sum_{\gamma}f_{\gamma}t^{\gamma_{1}}x^{\gamma_{2}}$ for some
$f_{\gamma}\in\mathbb{R}$ and define
$f_{\Gamma}(x)=\sum\\{f_{\gamma}x^{\gamma_{2}}:\gamma\in\Gamma\cap\mathrm{supp}f\\}$.
Then, the leading coefficients of the eigenvalues whose leading terms have
degree $d$ are the nonzero solutions to the equation $f_{\Gamma}(x)=0$; see,
e.g. [7], [8].

$\gamma_{2}$$\gamma_{1}$$n-m$$(n,2m-r)$$n$$O$$(n-m+r+\tilde{\mu},r+2\tilde{\mu})$$(n-m+r,r)$$E^{\prime}_{1}$$E^{\prime}_{2}$$E^{\prime}_{3}$
Figure 3. The Newton diagram associated with the characteristic polynomial

######  Theorem 4.1.

Let $A\in\mathbb{S}^{n}_{+}$ and $B\in\mathbb{S}^{n}$. Then every eigenvalue
of $A+tB$ is an analytic function of $t$ whose leading term has degree less
than or equal to $2$.

###### Proof.

It is well-known that every eigenvalue of $A+tB$ is an analytic function of
$t$; see, e.g. [6, Theorem $6.1$ in Chapter II]. Since the result obviously
holds if $A$ has the full rank, $A=O$, or $B=O$, we may assume that
$A=\mathrm{diag}(p_{1},\ldots,p_{n-m},0,\ldots,0)$ for some $m\in\mathbb{N}$
with $m<n$ and $p_{k}>0\ (k\in[n-m])$. In addition, we assume that $B$ is
partitioned as in $(\ref{eq:partition0})$ and
$B_{22}=CDC^{T}\in\mathbb{S}^{m}$ for some $r\in\mathbb{N}$,
$C=\begin{pmatrix}c_{1}&\cdots&c_{r}\end{pmatrix}\in\mathbb{R}^{m\times r}$
with $\mathop{\mathrm{missing}}{rank}C=r$,
$D=\mathrm{diag}(u_{1},\ldots,u_{r})$, $u_{k}\in\mathbb{R}\setminus\\{0\\}\
(k\in[r])$. Note that $\mathop{\mathrm{missing}}{rank}B_{22}=r$.

In this proof, the Newton diagram associated with the characteristic
polynomial $p_{A+tB}$ is simply called the Newton diagram. We will show that
every slope of the Newton diagram is less than or equal to $2$. By Proposition
3.2, we define three polynomials $P_{1},P_{2},P_{3}$ by

$\displaystyle p_{A+tB}(x)$
$\displaystyle=\sum_{i=m}^{n}\sum_{j=m-i}^{n-i}(-1)^{n-i}\langle\mathrm{adj}_{i+j}(A),C_{i+j}^{j}(B)\rangle
t^{j}x^{i}$
$\displaystyle+\sum_{i=m-r}^{m-1}\sum_{j=m-i}^{n-i}(-1)^{n-i}\langle\mathrm{adj}_{i+j}(A),C_{i+j}^{j}(B)\rangle
t^{j}x^{i}$
$\displaystyle+\sum_{i=0}^{m-r-1}\sum_{j=m-i}^{n-i}(-1)^{n-i}\langle\mathrm{adj}_{i+j}(A),C_{i+j}^{j}(B)\rangle
t^{j}x^{i}$ $\displaystyle=:P_{1}(x)+P_{2}(x)+P_{3}(x).$

Note that exponents of $(t,x)$ in $P_{1},P_{2}$ and $P_{3}$ correspond to
points on the edges $E_{1}$, $E_{2}$ and $E_{3}$ in Figure 1. Since
$C_{i+j}^{j}(B)$ is the zero matrix for $j<0$, we see that for $i=m,\ldots,n$,

$\displaystyle\sum_{j=m-i}^{n-i}(-1)^{n-i}\langle\mathrm{adj}_{i+j}(A),C_{i+j}^{j}(B)\rangle
t^{j}x^{i}$
$\displaystyle=(-1)^{n-i}\langle\mathrm{adj}_{i}(A),C_{i}^{0}(B)\rangle
x^{i}+\sum_{j=1}^{n-i}(-1)^{n-i}\langle\mathrm{adj}_{i+j}(A),C_{i+j}^{j}(B)\rangle
t^{j}x^{i}.$

Here,
$\langle\mathrm{adj}_{i}(A),C_{i}^{0}(B)\rangle=\mathop{\mathrm{missing}}{tr}\mathrm{adj}_{i}(A)>0$
and hence each coefficient of $x^{m},x^{m+1},\ldots,x^{n}$, which appears in
$P_{1}$, has a nonzero constant term. Thus the Newton diagram has the vertices
at $(0,0)$ and $(n-m,0)$.

If $r=m$, then $p_{A+tB}(x)=P_{1}(x)+P_{2}(x)$. By (ii) of Theorem 3.6, the
leading term of $P_{2}(0)$ is

$(-1)^{n}\langle\mathrm{adj}_{m}(A),C_{m}(B)\rangle t^{m}=(-1)^{n}p_{1}\cdots
p_{n-m}\begin{vmatrix}B_{22}\end{vmatrix}t^{m},$

where $|B_{22}|\neq 0$. Thus the Newton diagram has a vertex at $(n,m)$. Since
the slope of the line passing through $(n-m,0)$ and $(n,m)$ is $1$ and every
eigenvalue of $A+tB$ is analytic, there is no vertex below the line.
Therefore, the vertices of the Newton diagram consist of $(0,0)$, $(n-m,0)$,
$(n,m)$ and hence a slope of the Newton diagram is $0$ or $1$.

Thus it is sufficient to consider that the case $r<m$. Now, $P_{2}$ has
$x^{m-r},x^{m-r+1},\ldots,x^{m-1}$ and their leading terms are

$(-1)^{n-m+\eta}\langle\mathrm{adj}_{m}(A),C_{m}^{\eta}(B)\rangle
t^{\eta}=(-1)^{n-m+\eta}p_{1}\cdots
p_{n-m}\cdot\sum_{\eta\times\eta}\begin{vmatrix}B_{22}\end{vmatrix}t^{\eta},\quad(\eta=1,\ldots,r),$

by (ii) of Theorem 3.6. Thus $(n-m+r,r)$ is a possible vertex of the Newton
diagram. Next, we consider $P_{3}$ which has $x^{m-r-\mu}$ for
$\mu=1,\ldots,\min\\{m-r,n-m\\}$. The leading term of $x^{m-r-\mu}$
corresponds to the point $\gamma=(m-r-\mu,r+2\mu)$ in Figure 1, and (iii) of
Theorem 3.6 gives that

(8)
$\displaystyle(-1)^{n-m+r+\mu}\langle\mathrm{adj}_{m+\mu}(A),C_{m+\mu}^{r+2\mu}(B)\rangle
t^{r+2\mu}$ $\displaystyle=$
$\displaystyle(-1)^{n-m+r+2\mu}\cdot\sum_{\\{k_{1},\ldots,k_{\mu}\\}\subset[n-m]}\left(\prod_{k\in\\{k_{1},\ldots,k_{\mu}\\}^{c}}p_{k}\right)\cdot
u_{1}\cdots u_{r}$
$\displaystyle\phantom{(-1)^{n-m+r+2\mu}\cdot\sum_{\\{k_{1},\ldots,k_{\mu}\\}\subset[n-m]}}\cdot\sum_{(r+\mu)\times(r+\mu)}\begin{vmatrix}b_{k_{1}}&\cdots&b_{k_{\mu}}&c_{1}&\cdots&c_{r}\end{vmatrix}^{2}t^{r+2\mu}.$

Then Theorem 3.8 ensures that $(\ref{eq:leading})$ is $0$ if and only if
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{12}&B_{22}\end{pmatrix}<r+\mu.$

If
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}=r$,
then Theorem 3.8 implies that all the coefficients of $x^{0},x^{1},\ldots,$
$x^{m-r-1}$ are zero. Thus the nonzero term of $p_{A+tB}$ with the lowest
degree with respect to $x$ is $x^{m-r}$. Since the line passing through
$(n-m,0)$ and $(n-m+r,r)$ also passes through $(n,m)$, the vertices of the
Newton diagram consist of $(0,0)$, $(n-m,0)$, $(n,m)$. Therefore, a slope of
the Newton diagram is $0$ or $1$.

If
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}=r+\tilde{\mu}$
for some $\tilde{\mu}\in[\min\\{m-r,n-m\\}]$, then Theorem 3.8 implies that
all the coefficients of $x^{0},x^{1},\ldots,x^{m-r-\tilde{\mu}-1}$ are zero.
Here, we see that $x^{m-r-\tilde{\mu}}$ corresponds to
$(n-m+r+\tilde{\mu},r+2\tilde{\mu})$ on the plane of the Newton diagram and
this is the right most point corresponds to a nonzero term of $p_{A+tB}$. Thus
the vertices of the Newton diagram consist of $(0,0)$, $(n-m,0)$, $(n-m+r,r)$,
$(n,2m-r)$. Therefore, a slope of the Newton diagram is $0$, $1$, or $2$. ∎

By considering the case
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}=r$
in the proof, we obtain the following.

######  Corollary 4.2.

For $m,n\in\mathbb{N}$ with $m<n$, and $p_{k}>0\ (k\in[n-m])$, let
$A=\mathrm{diag}(p_{1},\ldots,p_{n-m},0,\ldots,0)\in\mathbb{S}^{n}$ and
$B\in\mathbb{S}^{n}$. Suppose that $B$ is partitioned as in
$(\ref{eq:partition0})$. If
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}=\mathop{\mathrm{missing}}{rank}B_{22}$,
then the leading coefficients of the eigenvalues $A+tB$ are less than or equal
to $1$.

##  5\. Convergence Analysis of the Alternating Projection Method

###  5.1. Alternating Projections

For $A\in\mathbb{S}^{n}_{+}\setminus\\{O\\}$ and
$B\in\mathbb{S}^{n}\setminus\\{O\\}$, let $E=\\{A+tB:t\in\mathbb{R}\\}$ and
$\varphi(t)=A+tB$. We show the following proposition which connects the
eigenvalues of $A+tB$ and the convergence rate of alternating projections. A
formula is obtained for a general affine space in [10]. We include a proof for
the case that the affine space is a line for completeness of the paper.

######  Proposition 5.1.

Let $\varphi(t)=A+tB$, $T=\varphi^{-1}\circ P_{E}\circ
P_{\mathbb{S}^{n}_{+}}\circ\varphi(t)$ and
$\lambda_{1}(t),\ldots,\lambda_{n}(t)$ be the eigenvalues of $\varphi(t)$.
Suppose $E\cap\mathbb{S}^{n}_{+}=\\{A\\}$. Then we have

$T=t-\frac{1}{\|B\|^{2}}\frac{d}{dt}\sum_{i\in
n(t)}\frac{1}{2}\lambda_{i}^{2}(t),$

where $n(t)=\\{i\in[n]:\lambda_{i}(t)<0\\}$ and $\|B\|$ is the Frobenius norm
of $B$.

###### Proof.

Let $V(t)=P_{\mathbb{S}^{n}_{+}}(\varphi(t))$ and $v_{i}(t)$ be the
orthonormal eigenvectors of $\varphi(t)$ associated with $\lambda_{i}(t)$ for
$i\in[n]$. Then $V(t)=\varphi(t)-\sum_{i\in
n(t)}\lambda_{i}(t)v_{i}(t)v_{i}(t)^{T}$. Since $P_{E}$ is the orthogonal
projection onto $E$, we can easily show that $P_{E}(V(t))=U_{*}+\frac{\langle
B,V(t)-U_{*}\rangle}{\|B\|^{2}}B$. Thus

$\displaystyle\varphi(T)$ $\displaystyle=P_{E}(V(t))=U_{*}+\frac{\langle
B,\varphi(t)\rangle}{\|B\|^{2}}B-\sum_{i\in n(t)}\lambda_{i}(t)\frac{\langle
B,v_{i}(t)v_{i}(t)^{T}\rangle}{\|B\|^{2}}B-\frac{\langle
B,U_{*}\rangle}{\|B\|^{2}}B$ $\displaystyle=P_{E}(\varphi(t))-\sum_{i\in
n(t)}\lambda_{i}(t)\frac{\langle
B,v_{i}(t)v_{i}(t)^{T}\rangle}{\|B\|^{2}}B=\varphi(t)-\sum_{i\in
n(t)}\lambda_{i}(t)\frac{v_{i}(t)^{T}Bv_{i}(t)}{\|B\|^{2}}B,$

and hence $\displaystyle T=t-\sum_{i\in
n(t)}\lambda_{i}(t)\frac{v_{i}(t)^{T}Bv_{i}(t)}{\|B\|^{2}}$. Since $A,B$ are
symmetric, we see that $\lambda_{i}(t)$, $v_{i}(t)$ are analytic by [6,
Theorem 6.1 and Section 6.2 in Chapter II] and
$\frac{d}{dt}\lambda_{i}(t)=v_{i}(t)^{T}Bv_{i}(t)$. This completes the proof.
∎

Let $\widetilde{E}=\\{Q^{T}(A+tB)Q:t\in\mathbb{R}\\}$ for an orthogonal matrix
$Q$. For $U\in E$, we have $P_{E}\circ
P_{\mathbb{S}^{n}_{+}}(U)=Q[P_{\widetilde{E}}\circ
P_{\mathbb{S}^{n}_{+}}(Q^{T}UQ)]Q^{T}$. Thus, by diagonalizing $A$, we may
assume that
$A=\mathrm{diag}(p_{1},\ldots,p_{n-m},0,\ldots,0)\in\mathbb{R}^{n\times n}$,
some $m\in\mathbb{N}$ with $m<n$ and $p_{k}>0\ (k\in[n-m])$. Let $B$ be
partitioned as $(\ref{eq:partition0})$. Then we will show the convergence rate
of alternating projections for $E$ and $\mathbb{S}^{n}_{+}$ is
$O(k^{-\frac{1}{2}})$. In the proof, we use the following technical lemma,
which is a slight modification of [9, Lemma $3.1$].

######  Lemma 5.2.

Suppose that the sequence $\\{x_{k}\\}$ satisfies

$x_{k+1}=x_{k}-ax_{k}^{d}+O(x_{k}^{d+1})\ (k=0,1,\ldots)$

for some $a>0$, an odd positive integer $d$ that is greater than $1$. Then
there exists $\delta>0$ such that if $0<|x_{0}|<\delta$, then $x_{k}$ has the
same sign as $x_{0}$ for $k=1,2,\ldots$ and $\\{x_{k}\\}$ converges to $0$
with $x_{k}=\Theta(k^{-\frac{1}{d-1}})$.

###### Proof.

For arbitrary $\varepsilon>0$, there exists $\delta$ with $0<\delta<a$ such
that $0<x_{k}<\delta$ implies
$0<x_{k}+(-a-\varepsilon)x_{k}^{d}<x_{k+1}<x_{k}+(-a+\varepsilon)x_{k}^{d}<\delta$.
By induction, we have $x_{k}>0$ for $k=1,2,\ldots$. Suppose
$\alpha:=\inf_{k}x_{k}>0$. Then $\alpha\leq
x_{k+1}<x_{k}+(-a+\varepsilon)\alpha^{d}$ and hence
$\alpha<\alpha+(a-\varepsilon)\alpha^{d}<x_{k}$. This is a contradiction. Thus
$\inf_{k}x_{k}=0$. Since $\\{x_{k}\\}$ is a decreasing sequence, we obtain
$x_{k}\to 0$. Then almost identical arguments in the proof of [9, Lemma $3.1$]
ensures that $x_{k}=\Theta(k^{-\frac{1}{2}})$. In case that $x_{1}<0$, we put
$x_{k}=-y_{k}$. Then we have $y_{k+1}=y_{k}-ay_{k}^{d}+O(y_{k}^{d+1})$ and
$y_{k}>0$. Applying the argument above to $y_{k}$, we obtain the result. ∎

######  Theorem 5.3.

Let $U_{k+1}=P_{E}\circ P_{\mathbb{S}^{n}_{+}}(U_{k})$. Suppose
$\mathbb{S}^{n}_{+}\cap E=\\{A\\}$. Then $\|U_{k}-A\|=O(k^{-\frac{1}{2}})$.
Moreover, if
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}=\mathop{\mathrm{missing}}{rank}B_{22}$.
Then $\\{U_{k}\\}$ converges to $A$ in a linear rate.

###### Proof.

Let $t_{k}=\varphi^{-1}(U_{k})$. Then $t_{k+1}=\varphi^{-1}\circ P_{E}\circ
P_{\mathbb{S}^{n}_{+}}\circ\varphi(t_{k})$. By Theorem 4.1, the leading term
of every eigenvalue of $A+tB$ has degree less than or equal to $2$. Then
Proposition 5.1 gives that
$t_{k+1}=t_{k}-\frac{1}{\|B\|^{2}}\frac{d}{dt}\sum_{i\in
n(t_{k})}\frac{1}{2}\lambda_{i}^{2}(t_{k})=t_{k}-at_{k}^{d}+O(t_{k}^{d+1})$
for some $a>0$, $d\in\mathbb{N}$ with $d=1$, or $3$. If $d=3$, then Lemma 5.2
implies that $|t_{k}|=\Theta(k^{-\frac{1}{2}})$ and hence
$\|U_{k}-A\|=\Theta(k^{-\frac{1}{2}})$. Suppose $d=1$ and estimate the value
of $a$. Then only the eigenvalues of $A+tB$ with leading degree $1$ contribute
to $a$. By the Newton diagram method explained in the first paragraph of
Section 4 and (ii) of Theorem 3.6, the leading coefficients of such
eigenvalues are the nonzero solutions to the equation $x^{m}-\sum_{1\times
1}|B_{22}|x^{m-1}+\sum_{2\times 2}|B_{22}|x^{m-2}+\cdots+(-1)^{m}\det
B_{22}=0$ . This is precisely equal to the characteristic polynomial of
$B_{22}$ and hence the leading coefficients are nonzero numbers among the
eigenvalues $\sigma_{1},\ldots,\sigma_{m}$ of $B_{22}$. If $\|B\|>\|B_{22}\|$,
then
$a\leq\frac{\sum_{i=1}^{m}\sigma_{i}^{2}}{\|B\|^{2}}=\frac{\|B_{22}\|^{2}}{\|B\|^{2}}<1$.
If $\|B\|=\|B_{22}\|$, then $B_{22}$ is indefinite since
$\mathbb{S}^{n}_{+}\cap E=\\{A\\}$. Thus
$a<\frac{\sum_{i=1}^{m}\sigma_{i}^{2}}{\|B\|^{2}}=1$. Thus $\\{t_{k}\\}$
converges linearly. If
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}=\mathop{\mathrm{missing}}{rank}B_{22}$,
Corollary 4.2 ensures $d\leq 1$. ∎

######  Example 5.4.

Consider

$A=\begin{pmatrix}1&0&0&0\\\ 0&0&0&0\\\ 0&0&0&0\\\ 0&0&0&0\end{pmatrix},\quad
B=\begin{pmatrix}b_{1}&b_{2}&b_{3}&b_{4}\\\ b_{2}&1&1&1\\\ b_{3}&1&u&0\\\
b_{4}&1&0&0\end{pmatrix}.$

Then
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}=\mathop{\mathrm{missing}}{rank}B_{22}$
if and only if $u\neq 0$, or $b_{3}=b_{4}$. In this case, Theorem 5.3 implies
that the convergence rate of $U_{k}$ is linear. In the other case, the
convergence rate is $O(k^{-\frac{1}{2}})$. We can directly check these
convergence rates by drawing the Newton diagram associated with $p_{A+tB}(x)$,
which is expanded by Proposition 3.2 as

$x^{4}-\left(1+(1+u+b_{1})t\right)x^{3}+\left((1+u)t+\left(\begin{vmatrix}b_{1}&b_{2}\\\
b_{2}&1\end{vmatrix}+\begin{vmatrix}b_{1}&b_{3}\\\
b_{3}&u\end{vmatrix}+\begin{vmatrix}b_{1}&b_{4}\\\
b_{4}&0\end{vmatrix}+\begin{vmatrix}1&1\\\
1&u\end{vmatrix}+\begin{vmatrix}1&1\\\
1&0\end{vmatrix}\right)t^{2}\right)x^{2}\\\ -\left((-2+u)t^{2}+\sum_{3\times
3}\begin{vmatrix}B\end{vmatrix}t^{3}\right)x+\begin{vmatrix}1&1&1\\\ 1&u&0\\\
1&0&0\end{vmatrix}t^{3}+\begin{vmatrix}B\end{vmatrix}t^{4}.$

######  Example 5.5.

The convergence rate given in Theorem 5.3 is only an upper bound. Let $A$ be
the same matrix in Example 5.4 and

$B=\begin{pmatrix}0&0&0&1\\\ 0&1&0&0\\\ 0&0&-2&0\\\ 1&0&0&0\end{pmatrix}.$

Then
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}>\mathop{\mathrm{missing}}{rank}B_{22}$.
However, the eigenvalues of $A+tB$ are $t,-2t,\frac{1\pm\sqrt{1+4t^{2}}}{2}$.
Thus Proposition 5.1 implies that the convergence rate is linear.

###  5.2. Singularity degree

We consider sufficient conditions for the upper bound given in Theorem 5.3 to
be tight. Here, we use the notion of the singularity degree of
$E\cap\mathbb{S}^{n}_{+}$; see, e.g. [2, 4, 11]. We give a brief explanation
for the singularity degree. Consider a general affine subspace

$E^{\prime}=\\{X\in\mathbb{S}^{n}:\langle C_{k},X\rangle=b_{k}\ (k\in[m])\\},$

where $C_{k}\in\mathbb{S}^{n}\ (k\in[m]),\
b=(b_{1},\ldots,b_{m})^{T}\in\mathbb{R}^{m}$. The face $F_{\min}$ of the
convex set $\mathbb{S}^{n}_{+}$ is called the minimal face of
$E^{\prime}\cap\mathbb{S}^{n}_{+}$ if $F_{\min}$ is the intersection of all
the faces of $\mathbb{S}^{n}_{+}$ containing
$E^{\prime}\cap\mathbb{S}^{n}_{+}$. Suppose that $E^{\prime}$ intersects with
$\mathbb{S}^{n}_{+}$ nontransversly; i.e., $E^{\prime}\cap
S^{n}_{+}\neq\emptyset$ and
$E^{\prime}\cap\mathop{\mathrm{missing}}{int}\mathbb{S}^{n}_{+}=\emptyset$. We
can find $F_{\min}$ by the following procedure called the facial reduction:

  1. (i)

Set $F_{0}=\mathbb{S}^{n}_{+},\ i=1$;

  2. (ii)

Find $y\in\mathbb{R}^{m},\ U^{i}\in\mathbb{S}^{n}_{+},\ V\in F_{i-1}^{\perp}$
such that

$b^{T}y=0,\quad\sum_{k=1}^{m}y_{k}C_{k}=U^{i}+V\notin F_{i-1}^{\perp};$

  3. (iii)

Set $F_{i+1}=F_{i}\cap\\{U^{i}\\}^{\perp}$;

  4. (iv)

If $F_{i+1}=F_{\min}$, then output $F_{i+1}$ as $F_{\min}$. Otherwise, set
$i:=i+1$ and repeat (ii), (iii), (iv).

It is well-known that only finitely many iterations are necessary to obtain
$F_{\min}$. Thus the iterative process can be expressed as

$\displaystyle\mathbb{S}_{+}^{n}$
$\displaystyle=F_{0}\overset{U^{1}}{\longrightarrow}F_{1}\overset{U^{2}}{\longrightarrow}F_{2}\overset{U^{3}}{\longrightarrow}\cdots\overset{U^{s}}{\longrightarrow}F_{s}=F_{\min}.$

The minimum length $s$ of such sequences is called the singularity degree of
$E^{\prime}\cap\mathbb{S}^{n}_{+}$.

First, we explain the relation between the singularity degree and $B_{22}$ by
the following lemma. Recall that
$A=\mathrm{diag}(p_{1},\ldots,p_{n-m},0,\ldots,0),\ p_{k}>0\ (k\in[n-m])$, $B$
is partitioned as $(\ref{eq:partition0})$ and
$E\cap\mathbb{S}^{n}_{+}=\\{A\\}$, where $E$ is the line defined by
$E=\\{A+tB:t\in\mathbb{R}\\}$.

######  Lemma 5.6.

  1. (i)

The singularity degree of $E\cap\mathbb{S}^{n}_{+}$ is greater than $1$, then
$B_{22}$ is a nonzero positive or negative semidefinite matrix with $\det
B_{22}=0$.

  2. (ii)

If $B_{22}$ is a nonzero positive or negative semidefinite matrix and
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}=\mathop{\mathrm{missing}}{rank}B_{22}$,
then $E\cap\mathbb{S}^{n}_{+}$ is not a singleton.

###### Proof.

(i) Obviously $B_{22}$ is nonzero. Suppose that $B_{22}$ is indefinite. Then
there exists an orthogonal matrix $Q$ such that $Q^{T}B_{22}Q=\Lambda$, where
$\Lambda=\mathrm{diag}(\lambda_{1},\ldots,\lambda_{r},0,\ldots,0)$ and two of
$\lambda_{k}$ have distinct signs. Then there exist positive numbers
$\sigma_{1},\ldots,\sigma_{m}$ such that
$\sum_{k=1}^{r}\sigma_{k}\lambda_{k}=0$. Define
$U=\left(\begin{array}[]{c|c}O&O\\\ \hline\cr O&Q\Sigma
Q^{T}\end{array}\right)$, where the partition is the same as that of $B$ and
$\Sigma=\mathrm{diag}(\sigma_{1},\ldots,\sigma_{m})$. Then we have
$U\in\mathbb{S}^{n}_{+}$ and $\langle U,B\rangle=0$. Let
$N=\dim\mathbb{S}^{n}_{+}$. Since $E$ is a line, there exist linearly
independent $C_{1},\ldots,C_{N-1}$ such that $E=\\{X\in\mathbb{S}^{n}:\langle
C_{1},X\rangle=1,\langle C_{k},X\rangle=0,k=2,\ldots,N-1\\}$. Then
$U\in\\{B\\}^{\perp}=\mathop{\mathrm{missing}}{Span}\\{C_{1},C_{2},\ldots,C_{N-1}\\}$
and hence $U=\sum_{k=1}^{N-1}y_{k}C_{k}$ for some $y_{k}\in\mathbb{R}$. In
addition, we have $y_{1}=\sum_{k=1}^{N-1}y_{k}\langle C_{k},A\rangle=\langle
U,A\rangle=0$ since $A\in E$. This means that the singularity degree is $1$.
Therefore, we have shown that if the singularity degree is $2$ then $B_{22}$
is a nonzero positive or negative semidefinite matrix. In addition, $\det
B_{22}=0$ since
$\mathop{\mathrm{missing}}{int}(E\cap\mathbb{S}^{n}_{+})=\emptyset$.

(ii) We assume that $B_{22}$ is a nonzero positive semidefinite matrix since
the other case is shown similarly. Let $A$ be partitioned as $B$. For $t$
sufficiently close to $0$, we see that $A_{11}+tB_{11}$ is positive definite.
By considering the Schur complement of $A_{11}+tB_{11}$ in $A+tB$, we have
that $A+tB$ is positive semidefinite if and only if
$S(t):=tB_{22}-t^{2}B_{21}(A_{11}+tB_{11})^{-1}B_{21}^{T}$ is positive
semidefinite. Since
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}=\mathop{\mathrm{missing}}{rank}B_{22}$,
the column space of $B_{21}$ is contained in that of $B_{22}$ and hence
contained in $\mathop{\mathrm{missing}}{Span}\\{v_{1},\ldots,v_{r}\\}$, where
$v_{k}\ (k\in[r])$ are eigenvectors of $B_{22}$ that are associated with
positive eigenvalues. Let
$v\in\mathop{\mathrm{missing}}{Span}\\{v_{1},\ldots,v_{r}\\}$ and $w\in\ker
B_{22}$. Since
$\mathop{\mathrm{missing}}{Span}\\{v_{1},\ldots,v_{r}\\}\perp\ker B_{22}$, we
have

$(v+w)^{T}S(t)(v+w)=t\left(v^{T}B_{22}v\right)-t^{2}\left(v^{T}B_{21}(A_{11}+tB_{11})^{-1}B_{21}^{T}v\right).$

Since $v^{T}B_{22}v\geq\lambda_{\min}\|v\|^{2}$ where $\lambda_{\min}$ is a
minimum positive eigenvalue of $B_{22}$, we obtain that $S(t)$ is positive
semidefinite for sufficiently small $t>0$. Therefore,
$A+tB\in\mathbb{S}^{n}_{+}$ and hence $E\cap S^{n}_{+}$ is not a singleton. ∎

######  Proposition 5.7.

Let $U_{k+1}=P_{E}\circ P_{\mathbb{S}^{n}_{+}}(U_{k})$. If
$\mathbb{S}^{n}_{+}\cap E=\\{A\\}$ and the singularity degree is greater than
$1$, then there exists the initial point $U_{0}$ such that
$\|U_{k}-A\|=\Theta(k^{-\frac{1}{2}})$.

###### Proof.

By Lemma 5.6, we may assume that $B_{22}$ is a nonzero positive semidefinite
matrix. In addition, we have
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}>\mathop{\mathrm{missing}}{rank}B_{22}$.
Let $r=\mathop{\mathrm{missing}}{rank}B_{22}$ and $d_{(i,j)}$ be the
coefficient of $t^{i}x^{j}$ in the characteristic polynomial $p_{A+tB}(x)$ of
$A+tB$. By (ii) of Theorem 3.6 and the positive semidefiniteness of $B_{22}$,
we obtain that
$\langle\mathrm{adj}_{|\gamma|}(A),C_{|\gamma|}^{\gamma_{1}}(B)\rangle>0$ for
$\gamma\in\Gamma:=\\{\left(\begin{smallmatrix}0\\\
m\end{smallmatrix}\right)+\eta\left(\begin{smallmatrix}1\\\
-1\end{smallmatrix}\right),\ \eta=0,\ldots,r\\}$. Thus
$d_{(0,m)},d_{(1,m-1)},\ldots,d_{(r,m-r)}$ are nonzero and have alternating
signs. Let $f(x)=\sum_{\gamma\in\Gamma}d_{\gamma}x^{\gamma_{2}}$. Then the
equation $f(x)=0$ has no negative solution. In fact, $f(-y)$ has no sign
change in the coefficients, and hence $f(-y)=0$ has no positive solution. For
$\gamma\in\Gamma$, we see that the coefficient of $x^{\gamma_{2}}$ in
$p_{A+tB}(x)$ is a polynomial in $t$ and its leading coefficient is
$d_{\gamma}$. Now, Theorem 3.8 ensures that $d_{(r+2,m-r-1)}$ is nonzero,
since
$\mathop{\mathrm{missing}}{rank}\begin{pmatrix}B_{21}&B_{22}\end{pmatrix}>r$.
Together with (iv) of Theorem 3.6, we see that $\Gamma$ coincides with the set
of all the integer points on the edge of slope $1$ of the Newton diagram
associated with $p_{A+tB}$. Thus, by the method of the Newton diagram
explained in the first paragraph of Section 4, the leading coefficients of the
eigenvalues of $A+tB$ whose leading terms have degree $1$ are the nonzero
solutions to the equation $f(x)=0$. Thus the leading term of an eigenvalue of
$A+tB$ with a negative leading coefficient has degree greater than $1$, and
hence Theorem 4.1 gives that the degree is $2$. On the other hand, since
$\mathbb{S}^{n}_{+}\cap E=\\{A\\}$, we see that $A+tB$ has at least one
negative eigenvalue for $t\neq 0$. For $U_{0}=A+t_{0}B$ for sufficiently small
$t_{0}>0$, let $U_{k+1}=P_{E}\circ P_{\mathbb{S}^{n}_{+}}(U_{k})$ and
$t_{k}=\varphi^{-1}(U_{k})$. Then Proposition 5.1 implies that
$t_{k+1}=t_{k}-\frac{1}{\|B\|^{2}}\frac{d}{dt}\sum_{i\in
n(t_{k})}\frac{1}{2}\lambda_{i}^{2}(t_{k})=t_{k}-at_{k}^{3}+O(t_{k}^{4})$ for
some $a>0$. Therefore, Lemma 5.2 implies that
$\|U_{k}-A\|=\Theta(k^{-\frac{1}{2}})$. ∎

##  6\. Acknowledgment

The first author was supported by JSPS KAKENHI Grant Number JP17K18726 and
JSPS Grant-in-Aid for Transformative Research Areas (A) (22H05107). The second
author was supported by JSPS KAKENHI Grant Number JP19K03631. The third author
was supported by JSPS KAKENHI Grant Number JP20K11696 and ERATO HASUO
Metamathematics for Systems Design Project (No.JPMJER1603), JST.

## References

  * [1] H.H. Bauschke, J.M. Borwein, On the convergence of von Neumann’s alternating projection algorithm for two sets, Set-Valued Anal. 1(2), 185–212 (1993).
  * [2] J.M. Borwein, H. Wolkowicz, Facial reduction for a cone-convex programming problem, J. Aust. Math. Soc. 30(3), 369–380 (1980/81).
  * [3] D. Drusvyatskiy, G. Li, H. Wolkowicz,  A note on alternating projections for ill-posed semidefinite feasibility problems, Math. Program. 162 (2017), pp. 537–548.
  * [4] D. Drusvyatskiy, H. Wolkowicz, The many faces of degeneracy in conic optimization, Foundations and Trends in Optimization 3(2), 77–170, (2017).
  * [5] R.A. Horn, C.R. Johnson, Matrix Analysis: Second Edition, Cambridge University Press, (2017).
  * [6] T. Kato, Perturbation Theory for Linear Operator, Springer-Verlag, Berlin (1980).
  * [7] J. Moro, J.V. Burke, M.L. Overton, On the Lidskii-Vishik-Lyusternik Perturbation Theory for Eigenvalues of Matrices with Arbitrary Jordan Structure, SIAM J. Matrix Anal. Appl. 18, 793–817 (1997).
  * [8] J. Moro, F.M. Dopico, First Order Eigenvalue Perturbation Theory and the Newton Diagram, Applied mathematics and scientific computing (Dubrovnik, 2001), 143–-175, Kluwer/Plenum, New York, 2003.
  * [9] H. Ochiai, Y. Sekiguchi, H. Waki, Exact convergence rates of alternating projections for nontransversal intersections, Jpn. J. Ind. Appl. Math. 41, 57–83 (2024).
  * [10] H. Ochiai, Y. Sekiguchi, H. Waki, Analytic Formulas for Alternating Projection Sequences for the Positive Semidefinite Cone and an Application to Convergence Analysis, arXiv:2401.15276 [math.OC].
  * [11] Y. Sekiguchi, H. Waki, Perturbation Analysis of Singular Semidefinite Programs and Its Applications to Control Problems, J. Optim. Theory Appl. 188, 52–72 (2021).