* Gil-Lopez  _et al._ [2021] J. Gil-Lopez, Y. S. Teo, S. De, B. Brecht, H. Jeong, C. Silberhorn, and L. L. Sánchez-Soto, Universal compressive tomography in the time-frequency domain, Optica 8, 1296 (2021).
  * Browne and Rudolph [2005] D. E. Browne and T. Rudolph, Resource-efficient linear optical quantum computation, Phys. Rev. Lett. 95, 010501 (2005).
  * Bartolucci  _et al._ [2021c] S. Bartolucci, P. M. Birchall, M. Gimeno-Segovia, E. Johnston, K. Kieling, M. Pant, T. Rudolph, J. Smith, C. Sparrow, and M. D. Vidrighin, Creation of entangled photonic states using linear optics (2021c), arXiv:2106.13825 [quant-ph] .
  * Lee and Jeong [2021] S.-H. Lee and H. Jeong, Universal resource-efficient topological measurement-based quantum computation via color-code-based cluster states (2021), arXiv:2106.07530 [quant-ph] .
  * Criger and Terhal [2016] B. Criger and B. Terhal, Noise thresholds for the [[4, 2, 2]]-concatenated toric code, Quantum Information and Computation 16, 1261 (2016).
  * Fowler and Goyal [2009b] A. G. Fowler and K. Goyal, Topological cluster state quantum computing, Quantum Info. Comput. 9, 721–738 (2009b).
  * Edmonds [1965a] J. Edmonds, Paths, trees, and flowers, Can. J. Math. 17, 449 (1965a).
  * Edmonds [1965b] J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bur. Stand. B 69, 55 (1965b).
  * Fowler [2015] A. G. Fowler, Minimum weight perfect matching of fault-tolerant topological quantum error correction in average o(1) parallel time, Quantum Info. Comput. 15, 145–158 (2015).
  * Kolmogorov [2009] V. Kolmogorov, Blossom v: a new implementation of a minimum cost perfect matching algorithm, Math. Program. Comput. 1, 43 (2009).


# A class of normal dilation matrices affirming the Marcus-de Oliveira
conjecture

Kijti Rodtes  missing<EMAIL_ADDRESS>
###### Abstract.

In this article, we prove a class of normal dilation matrices affirming the
Marcus-de Oliveira conjecture.

Keywords: Normal dilation, Normal matrices, Marcus de Oliveira Conjecture
MSC(2010): 15A15; 15A60; 15A86

Throughout, $n$ will denote a positive integer. The determinant conjecture of
Marcus and de Oliveira states that the determinant of the sum of two $n$ by
$n$ normal matrices $A$ and $B$ belongs to the convex hull of the $n!$
$\sigma$-points, $z_{\sigma}:=\prod_{i=1}^{n}(a_{i}+b_{\sigma(i)})$, indexed
by $\sigma\in S_{n}$, where $a_{i}$’s and $b_{j}$’s are eigenvalues of $A$ and
$B$, respectively (see [9],[3],[11]). We briefly write as $(A,B)\in MOC$ if
the pair of normal matrices $A,B$ affirms the Marcus and de Oliveira
conjecture, i.e.,

$\det(A+B)\in co(\\{z_{\sigma}|\sigma\in S_{n}\\}).$

In [8], Fiedler showed that, for two hermitian matrices $A,B$

$\Delta(A,B):=\\{\det(A+UBU^{*})|U\in U_{n}(\mathbb{C})\\}$

is a line segment with $\sigma$-points as endpoints, where $U_{n}(\mathbb{C})$
denotes the set of all unitary matrices of dimension $n\times n$. This result,
in fact, motivates the conjecture. As a consequence of Fiedler’s result,
$(A,B)\in MOC$ for any pair of skew-hermitian matrices $A,B$.

In [1], N. Bebiano, A. Kovacec, and J.da Providencia provided that if $A$ is
positive definite and $B$ a non-real scalar multiple of a hermitian matrix,
then $(A,B)\in MOC$. They also obtained that if eigenvalues of $A$ are
pairwise distinct complex numbers lying on a line $l$ and all eigenvalues of
$B$ lie on a parallel to $l$, then $(A,B)\in MOC$. S.W. Drury showed that
$(A,B)\in MOC$ for the case that $A$ is hermitian and $B$ is non-real scalar
multiple of a hermitian matrix (essentially hermitian matrix) in [5] and the
case that $A=sU$ and $B=tV$ for $s,t\in\mathbb{C}$ and $U,V\in
U_{n}(\mathbb{C})$ in [6].

It is also known that, for normal matrices $A,B\in M_{n}(\mathbb{C})$ (the set
of all $n\times n$ matrices over $\mathbb{C}$), $(A,B)\in MOC$: if
$\det(A+B)=0$ ([7]); if the point $z_{\sigma}$ lie all on a straight line
([10]); if $n=2,3$ ([3, 2]); if $A$ or $B$ has only two distinct eigenvalues,
one of them simple, ([3]). However, it seems that there is no new affirmative
class of normal matrices to this conjecture after the year 2007.

Let $X$ be a square $n\times n$ complex matrix and $s$ be a complex number. It
is a direct calculation to see that

$N(X,s):=\left(\begin{array}[]{cc}X&(X-sI)^{*}\\\ (X-sI)^{*}&X\\\
\end{array}\right)$

is a normal matrix of size $2n\times 2n$ and thus it is a normal dilation of
$X$. We will see (in the proof of the main result) that the eigenvalues of
$N(X,s)$ lie on both real and imaginary axis and thus this matrix need not be
essentially hermitian or a scalar multiple of a unitary matrix. In this short
note, we show that:

######  Theorem 0.1.

Let $X,Y\in M_{n}(\mathbb{C})$ and $s,t\in\mathbb{C}$. Then
$(N(X,s),N(Y,t))\in MOC$.

Note that if $A\in M_{n}(\mathbb{C})$ is normal then $UAU^{*}$ is also normal
for any $U\in U_{n}(\mathbb{C})$. Then $VN(X,s)V^{*}$ is also a normal
dilation of $X$ for any $V\in U_{2n}(\mathbb{C})$. Moreover, since the
conjecture is invariant under simultaneous unitary similarity, we also deduce
from Theorem 0.1 that $(VN(X,s)V^{*},VN(Y,t)V^{*})\in MOC$ for any $V\in
U_{2n}(\mathbb{C})$.

To prove the main result, we will use the following lemmas.

######  Lemma 0.2.

Let $A,B\in M_{n}(\mathbb{C})$ and $C,D\in M_{m}(\mathbb{C})$ be normal. If
$(A,B)\in MOC$ and $(C,D)\in MOC$, then $(A\oplus C,B\oplus D)\in MOC$.

###### Proof.

Suppose that $\\{a_{i}\,|\,1\leq i\leq n\\}$, $\\{b_{i}\,|\,1\leq i\leq n\\}$,
$\\{c_{i}\,|\,1\leq i\leq m\\}$ and $\\{d_{i}\,|\,1\leq i\leq m\\}$ are
ordered set of the eigenvalues of $A,B,C$ and $D$, respectively. Denote
$e_{i}:=a_{i}$, $f_{i}:=b_{i}$ for $i=1,\dots,n$ and $e_{n+j}=c_{j}$,
$f_{n+j}=d_{j}$ for $j=1,\dots,m$. Then, $\\{e_{i}\,|\,1\leq i\leq n+m\\}$ and
$\\{f_{i}\,|\,1\leq i\leq n+m\\}$ are ordered set of the eigenvalues of
$A\oplus C$ and $B\oplus D$, respectively. For each $\sigma\in S_{n},\pi\in
S_{m}$ and $\theta\in S_{n+m}$, denote $z_{\sigma},v_{\pi}$ and $w_{\theta}$
the product $\prod_{i=1}^{n}(a_{i}+b_{\sigma(i)})$,
$\prod_{i=1}^{m}(c_{i}+d_{\pi(i)})$ and
$\prod_{i=1}^{n+m}(e_{i}+f_{\theta(i)})$, respectively. Suppose that $(A,B)\in
MOC$ and $(C,D)\in MOC$, then

$\det(A+B)=\sum_{\sigma\in S_{n}}t_{\sigma}z_{\sigma}\hbox{ and
}\det(C+D)=\sum_{\pi\in S_{m}}s_{\pi}v_{\pi},$

where $t_{\sigma},s_{\pi}\in[0,1]$ such that $\sum_{\sigma\in
S_{n}}t_{\sigma}=1$ and $\sum_{\sigma\in S_{m}}s_{\pi}=1$. Note that

$\displaystyle\det(A\oplus C+B\oplus D)$ $\displaystyle=$
$\displaystyle\det((A+B)\oplus(C+D))$ $\displaystyle=$
$\displaystyle\det(A+B)\cdot\det(C+D)$ $\displaystyle=$
$\displaystyle(\sum_{\sigma\in S_{n}}t_{\sigma}z_{\sigma})(\sum_{\pi\in
S_{m}}s_{\pi}v_{\pi})$ $\displaystyle=$ $\displaystyle\sum_{\sigma\in
S_{n},\pi\in S_{m}}(t_{\sigma}s_{\pi})(z_{\sigma}v_{\pi}).$

For each $\sigma\in S_{n}$ and $\pi\in S_{m}$, define a permutation
$\theta(\sigma,\pi)\in S_{n+m}$ by

$\theta(\sigma,\pi):=\left(\begin{array}[]{cccccc}1&\cdots&n&n+1&\cdots&n+m\\\
\sigma(1)&\cdots&\sigma(n)&n+\pi(1)&\cdots&n+\pi(m)\\\ \end{array}\right)$

Then $w_{\theta(\sigma,\pi)}=z_{\sigma}v_{\pi}$. Since, for each $\sigma\in
S_{n}$ and $\pi\in S_{m}$, $t_{\sigma}s_{\pi}\in[0,1]$ and

$\sum_{\sigma\in S_{n},\pi\in S_{m}}(t_{\sigma}s_{\pi})=(\sum_{\sigma\in
S_{n}}t_{\sigma})(\sum_{\sigma\in S_{m}}s_{\pi})=(1)(1)=1,$

we conclude that

$\det(A\oplus C+B\oplus D)\in co\\{w_{\theta(\sigma,\pi)}\,|\,\sigma\in
S_{n},\pi\in S_{m}\\}\subseteq co\\{w_{\theta}\,|\,\theta\in S_{n+m}\\}.$

Hence $(A\oplus C,B\oplus D)\in MOC$. ∎

To be a self contained material, we record a result of S.W. Drury.

######  Theorem 0.3.

[4] Let $A$ and $B$ be hermitian matrices with the given eigenvalues
$(a_{1},\dots,a_{n})$ and $(b_{1},\dots,b_{n})$ respectively. Let
$(t_{1},\dots,t_{n})$ be the eigenvalues of $A+B$. Then

$\prod_{j=1}^{n}(\lambda+t_{j})\in
co\\{\prod_{j=1}^{n}(\lambda+a_{j}+b_{\sigma(j)})|\sigma\in S_{n}\\},$

where $co$ denotes the convex hull in the space of polynomials and $\lambda$
is an indeterminate.

As a corollary of the above theorem, we have that:

######  Lemma 0.4.

Let $X,Y\in M_{n}(\mathbb{C})$ and $\alpha,\beta\in\mathbb{C}$. Then
$(X-X^{*}+\alpha I_{n},Y-Y^{*}+\beta I_{n})\in MOC$ and $(X+X^{*}+\alpha
I_{n},Y+Y^{*}+\beta I_{n})\in MOC$.

###### Proof.

Since $X+X^{*}$ and $Y+Y^{*}$ are hermitian, by Theorem 0.3, we deduce
directly that $(X+X^{*}+\alpha I_{n},Y+Y^{*}+\beta I_{n})\in MOC$. Since
$X-X^{*}$ and $Y-Y^{*}$ are skew-hermitian, $i(X-X^{*})$ and $i(Y-Y^{*})$ are
hermitian. Again, by Theorem 0.3, $(X-X^{*}+\alpha I_{n},Y-Y^{*}+\beta
I_{n})\in MOC$.

∎

###### Proof.

(Theorem 0.1) Let $U$ be the block matrix in $M_{2n}(\mathbb{C})$ defined by

$U:=\frac{1}{\sqrt{2}}\left(\begin{array}[]{cc}I_{n}&I_{n}\\\ -I_{n}&I_{n}\\\
\end{array}\right).$

It is a direct computation to see that $U$ is a unitary matrix and

$U^{*}\left(\begin{array}[]{cc}M&N\\\ N&M\\\
\end{array}\right)U=(M-N)\oplus(M+N),$

for any $M,N\in M_{n}(\mathbb{C})$. Let $A:=X-X^{*}+(\overline{s})I_{n}$,
$B:=Y-Y^{*}+\overline{t}I_{n}$, $C:=X+X^{*}-(\overline{s})I_{n}$, and
$D:=Y+Y^{*}-\overline{t}I_{n}$. By Lemma 0.4, the pair of normal matrices
$(A,B)$ and $(C,D)$ satisfy the conjecture. Hence, by Lemma 0.2, $(A\oplus
C,B\oplus D)\in MOC$. Therefore,

$(N(X,s),N(Y,t))=(U(A\oplus C)U^{*},U(B\oplus D)U^{*})\in MOC,$

which completes the proof. ∎

## Acknowledgments

The author would like to thank Prof Tin Yau Tam for bringing this topic to the
author. He would like to thank the referee(s) for valuable comments to improve
the paper. He also would like to thank Naresuan University for the financial
support on the project number R2563C006.

## References

  * [1] N. Bebiano, A. Kovacec, and J.da Providencia. The validity of the Marcus-de Oliveira conjecture for essentially Hermitian matrices. _Second Conference of the International Linear Algebra Society (ILAS) (Lisbon, 1992). Linear Algebra Appl._ , 197/198:411-427, 1994.
  * [2] N. Bebiano, J. K. Merikoski, and J. da Providencia, On a conjecture of G. N. de Oliveira on determinants, _Linear and Multilinear Algebra_ , 20:167-170, 1987.
  * [3] G. N. de Oliveira, Normal matrices (research problem),_linear and Multilinear Algebra_ , 12:153-154, 1982.
  * [4] S. W. Drury. On Symmetric Functions of the Eigenvalues of the Sum of Two Hermitian Matrices. _Linear Algebra Appl._ , 176:211-222, 1992.
  * [5] S. W. Drury. Essentially Hermitian matrices revisited. _Electron. J. Linear Algebra_ , 15:285-296, 2006.
  * [6] S. W. Drury. OMC for scalar multiples of unitaries. _Linear Algebra Appl._ , 422(1):318-325, 2007.
  * [7] S. W. Drury and B. Cload, On the determinantal conjecture of Marcus and de Oliveira, _Linear Algebra Appl._ , 177:105-109, 1992.
  * [8] M. Fiedler, Bounds for the determinant of the sum of hermitian matrices, _Proc.Amer.Math.Soc_ , 30:27-31, 1971.
  * [9] M. Marcus, Derivations, Plucker relations, and the numerical range. _Indiana Univ. Math. J._ , 22:1137-1149, 1972/73.
  * [10] J. K. Merikoski and A. Virtanen, Some notes on de Oliveira’s determinantal conjecture, _Linear Algebra Appl._ , 121:345-352, 1989.
  * [11] X. Zhan, Open problems in matrix theory, _ICCM_ , II. 1-4, 2007.

Kijti Rodtes

Department of Mathematics, Faculty of Science,
Naresuan University, Phitsanulok 65000, Thailand