# Distance Evaluation to the Set of Defective Matrices

Alexei Yu. Uteshev111The corresponding author, Elizaveta A. Kalinina, Marina
V. Goncharova
St. Petersburg State University
Faculty of Applied Mathematics
St. Petersburg, Russia
1<EMAIL_ADDRESS>

###### Abstract

We treat the problem of the Frobenius distance evaluation from a given matrix
$A\in\mathbb{R}^{n\times n}$ with distinct eigenvalues to the manifold of
matrices with multiple eigenvalues. On restricting considerations to the rank
$1$ real perturbation matrices, we prove that the distance in question equals
$\sqrt{z_{\ast}}$ where $z_{\ast}$ is a positive (generically, the least
positive) zero of the algebraic equation

$\mathcal{F}(z)=0,\ \mbox{where}\
\mathcal{F}(z):=\mathcal{D}_{\lambda}\left(\det\left[(\lambda I-A)(\lambda
I-A^{\top})-zI_{n}\right]\right)/z^{n}$

and $\mathcal{D}_{\lambda}$ stands for the discriminant of the polynomial
treated with respect to $\lambda$. In the framework of this approach we also
provide the procedure for finding the nearest to $A$ matrix with multiple
eigenvalue. Generalization of the problem to the case of complex perturbations
is also discussed. Several examples are presented clarifying the computational
aspects of the approach.

Keywords: Wilkinson’s problem, defective matrix, multiple eigenvalues,
distance equation

MSC 2010: 68W30, 15A18 , 12D10, 58C40

##  1 Introduction

The origin of the problem of finding the distance from a matrix
$A\in\mathbb{C}^{n\times n}$ to the set $\mathbb{D}$ of matrices with multiple
eigenvalues can be traced back to Wilkinson [23] who posed it in relation to
the sensitivity analysis of matrix eigenvalues. The desired distance further
will be treated with respect to either the $2$-norm or to the Frobenius norm
in $\mathbb{C}^{n\times n}$ and will be denoted $d(A,\mathbb{D})$. It is
usually referred to as the Wilkinson distance of $A$ [3, 18]. Alternatively,
$d(A,\mathbb{D})$ can be defined as the $\inf\|A-B\|$ where $B$ belongs to the
subset of defective matrices, i.e. those possessing at least one eigenvalue
whose geometric multiplicity is less than its algebraic multiplicity.

Starting from Wilkinson’s works [24, 25, 26], the problem of evaluation of
$d(A,\mathbb{D})$ has been studied intensively in [3, 7, 8, 16, 17, 19]. The
most recent result is presented in the work [2]. We briefly trace the
developed approaches. Most of them are in the framework of singular value
analysis of appropriate parameter dependent matrices.

The following theorem gives the min-max representation of $d(A,\mathbb{D})$
obtained by Malyshev [17].

###### Theorem 1.1

Let $A\in\mathbb{C}^{n\times n}$. Let the singular values of the matrix

$\left[\begin{array}[]{cc}A-\lambda I_{n}&\gamma I_{n}\\\ \mathbb{O}_{n\times
n}&A-\lambda I_{n}\end{array}\right]$ (1.1)

be ordered like
$\sigma_{1}(\lambda,\gamma)\geq\sigma_{2}(\lambda,\gamma)\geq\ldots\geq\sigma_{2n}(\lambda,\gamma)\geq
0$. Then the $2$-norm distance $d(A,\mathbb{D})$ can be evaluated as

$d(A,\mathbb{D})=\min_{\lambda\in\mathbb{C}}\max_{\gamma\geq
0}\sigma_{2n-1}(\lambda,\gamma)\,.$

The straight computation of this distance is quite difficult, so to find this
distance, in many works the notion of pseudospectra [20] is used.

Definition. For both the 2-norm and the Frobenius norm, the
$\varepsilon$-pseudospectra of a matrix $A$ is

$\Lambda_{\varepsilon}(A)=\\{\sigma_{\min}<\varepsilon\\}$

where $\varepsilon>0$ and $\sigma_{\min}$ stands for the smallest singular
value of the matrix $A-zI$.

Equivalently,

$\Lambda_{\varepsilon}(A)=\\{z\in\mathbb{C}|\det(A+E-zI)=0,\mbox{ \rm for some
}E\in\mathbb{C}^{n\times n}\mbox{ \rm with }\|E\|<\varepsilon\\}\,.$

If $\Lambda_{\varepsilon}$ has $n$ components, then $A+E$ has $n$ distinct
eigenvalues for all perturbations $E\in\mathbb{C}^{n\times n}$ and hence $A+E$
is not defective.

In subsequent papers, the pseudospectra approach is used to find the distance
to the nearest defective matrix.

In [16], a geometric solution to the problem of finding $d(A,\mathbb{D})$ in
Frobenius norm is given. The nearest defective matrix is related to the
critical points of the minimal singular value $\sigma_{\min}(x,y)$ of the
matrix $A-(x+\mathbf{i}y)I$ that could be obtained by examination of
pseudospectra of $A$. For an approximation of a multiple eigenvalue of the
nearest defective matrix, the averaging heuristic by Puiseux series is
proposed. Also an iterative method for finding this eigenvalue together with
the minimal perturbation is presented.

In [3], it is proposed to find the smallest perturbation $E$ such that the
components of the pseudospectra of $A+E$ coalesce. The problem is reformulated
as follows. One needs to find
$z\in\mathbb{C},\varepsilon\in\mathbb{R},\varepsilon>0$ and
$U,V\in\mathbb{C}^{n}$, such that222Hereinafter $\mbox{}^{\top}$ stands for
the transpose while $\mbox{}^{\mathsf{H}}$ stands for the Hermitian transpose.

$(A-zI)V-\varepsilon U=\mathbb{O}_{n\times 1},\varepsilon
V-(A-zI)^{\mathsf{H}}U=\mathbb{O}_{n\times 1},\,U^{\mathsf{H}}V=0\,.$ (1.2)

The algorithm to solve the system of equations presented in this work is
rather expensive because it requires the repeated calculation of
pseudospectra. Also any condition of coalescence of two pseudospectral curves
is necessary.

In [4], a new computational approach to approximating the nearest defective
matrix by a variant of Newton’s method is suggested.

The Implicit Determinant Method based on standard Newton’s method is used to
solve the system (1.2) in [2].

There are several works considering generalizations of Wilkinson’s problem for
the cases of prescribed eigenvalues or their multiplicities [5, 11, 15, 14,
18], and matrix pencils [1].

The approaches developed in the above cited papers could be characterized as
related to the Numerical Linear Algebra. The present paper aims at solving the
stated problem for the case of Frobenius norm within the framework of symbolic
computation approach. Namely, we reduce the problem to that of the univariate
polynomial equation solving. As a matter of fact, the manifold $\mathbb{D}$ of
matrices with multiple eigenvalues in the $\mathbb{R}^{n^{2}}$ space of their
entries is an algebraic one, i.e. it is represented by a multivariate
polynomial equation. If we slightly modify Wilkinson’s problem to that of
finding $d^{2}(A,\mathbb{D})$, then the constrained optimization problem
becomes an algebraic one in the sense that both the objective function and the
constraint be polynomials. Application of the Lagrange multipliers method
reduces the problem to that of system of algebraic equations solving. The
latter can be resolved, at least in theory, via the analytical procedure of
elimination of variables consisting in the multivariate resultant computation
or the Gröbner basis construction. Application of these procedures to the
system of equations of the treated problem, complemented with
$z-d^{2}(A,\mathbb{D})=0$, results in a univariate equation $\mathcal{F}(z)=0$
whose zero set contains all the critical values of the squared distance
function. This equation will be further referred to as the distance equation
and its computation is the priority of the present paper.

This approach has been developed in [13]. Unfortunately, soon after that
publication, a significant gap in reasoning was discovered. It was assumed
that the value $d(A,\mathbb{D})$ could be provided by only the rank $1$
perturbation matrix $E_{\ast}$ and that the nearest to $A$ matrix
$B_{\ast}=A+E_{\ast}$ in $\mathbb{D}$ might possess only a double real
eigenvalue. In Section 6, an example of the order $4$ matrix $A$ is given
where the nearest in $\mathbb{D}$ matrix possesses a pair of double complex-
conjugate eigenvalues. As yet we failed to manage this scenario for the
general statement of the problem; neither do we able to claim that it is a
zero probability event.

We confine ourselves here to considering the case where the critical values of
$d^{2}(A,\mathbb{D})$ are provided only by the rank $1$ perturbation matrices.
For this case, the practical implementations of the elimination of variables
procedure mentioned above can be reduced to just only two bivariate equations.
One of these equations follows quite naturally from the developed in [13]
approach. This is

$\Phi(\lambda,z)=0\ \mbox{where}\ \Phi(\lambda,z):=\det\left[(\lambda
I-A)(\lambda I-A^{\top})-zI_{n}\right]\,.$

The more difficulties causes the deduction of the second equation. It happens
to be

$\partial\Phi(\lambda,z)/\partial\lambda=0\,.$

To obtain the distance equation, it is then sufficient to eliminate the
variable $\lambda$ from the obtained system. This can be managed with the aid
of discriminant computation, i.e. the function of the coefficients of a
polynomial responsible for the existence of a multiple zero for this
polynomial. We recall some basic features of this function in Section 2.

In Section 3, we prove the main result of the paper, namely that the value
$d^{2}(A,\mathbb{D})$ is in the set of non-negative zeros of the distance
equation. If $A\not\in\mathbb{D}$ then generically $d^{2}(A,\mathbb{D})$
equals the least positive zero $z_{\ast}$ of this equation. We also detail
here the structure of the matrix $B_{\ast}$ nearest to $A$ in $\mathbb{D}$. It
appears that the multiple eigenvalue of $B_{\ast}$ coincide with the multiple
zero of the polynomial $\Phi(\lambda,z_{\ast})$.

In Section 5, computational aspects of the proposed approach are discussed via
solving the problem for the two families of matrices treated in the
literature.

In Section 7, we address to the generalization of Wilkinson’s problem to the
case of complex perturbations. Here the results are presented in a very
concise manner with the potential intention of returning to them in future
articles.

Notation is kept to correlate with [13]. For a matrix $A\in\mathbb{R}^{n\times
n}$, $f_{A}(\lambda)$ denotes its characteristic polynomial, $d(A,\mathbb{D})$
denotes the distance from $A$ to the set $\mathbb{D}$ of matrices possessing a
multiple eigenvalue. $E_{\ast}$ and $B_{\ast}=A+E_{\ast}$ stand for,
respectively, the (minimal) perturbation matrix and the nearest to $A$ matrix
in $\mathbb{D}$ (i.e. $d(A,\mathbb{D})=\|A-B_{\ast}\|$); we then term by
$\lambda_{\ast}$ the multiple eigenvalue of $B_{\ast}$. $I$ (or $I_{n}$)
denotes the identity matrix (of the corresponding order). $\mathcal{D}$ (or
$\mathcal{D}_{\lambda}$) denotes the discriminant of a polynomial (with
subscript indicating the variable).

Remark. All the computations were performed in CAS Maple 15.0 with those
approximate done within the accuracy $10^{-40}$. In the paper they are
presented rounded to $10^{-6}$.

##  2 Algebraic Preliminaries

It is well-known that in the $(N+1)$-dimensional space of the polynomial

$F(x)=a_{0}x^{N}+a_{1}x^{N-1}+\dots+a_{N}\in\mathbb{C}[x],\,a_{0}\neq 0,N\geq
2$ (2.1)

coefficients, the manifold of polynomials with multiple zeros is given by the
equation

$D(a_{0},a_{1},\dots,a_{N})=0\quad\mbox{where}\ D:=\mathcal{D}_{x}(F(x))$
(2.2)

denotes the discriminant of the polynomial. Discriminant is formally defined
as a symmetric function of the zeros $\\{\lambda_{1},\dots,\lambda_{N}\\}$ of
the polynomial $F(x)$

$D_{x}(F(x))=a_{0}^{2N-2}\prod_{1\leq j<k\leq
N}(\lambda_{k}-\lambda_{j})^{2}\,.$ (2.3)

This representation gives rise to further transformation of the discriminant
into the homogeneous polynomial $D(a_{0},a_{1},\dots,a_{N})$ of the order
$2N-2$ with respect to the coefficients of $F(x)$. Such a transformation can
be implemented through a preliminary representation of discriminant in an
appropriate determinantal form. We will follow the approach based on the
Hankel matrix formalism [21].

For this aim, find first the Newton sums $s_{0},s_{1},\dots,s_{2N-2}$ of the
polynomial $F(x)$ with the aid of recursive formulas

$s_{0}=N,\ s_{1}=-a_{1}/a_{0},\ $
$s_{k}=\left\\{\begin{array}[]{lr}-(a_{1}s_{k-1}+a_{2}s_{k-2}+\dots+a_{k-1}s_{1}+a_{k}k)/a_{0},&\mbox{
if}\ k\leq N,\\\
-(a_{1}s_{k-1}+a_{2}s_{k-2}+\dots+a_{N}s_{k-N})/a_{0},&\mbox{if}\
k>N,\end{array}\right.$ (2.4)

and compose the Hankel matrix

$S=\left[s_{j+k}\right]_{j,k=0}^{N-1}=\left[\begin{array}[]{llllll}s_{0}&s_{1}&s_{2}&\dots&s_{N-2}&s_{N-1}\\\
s_{1}&s_{2}&s_{3}&\dots&s_{N-1}&s_{N}\\\
s_{2}&s_{3}&s_{4}&\dots&s_{N}&s_{N+1}\\\ \dots&&&&&\dots\\\
s_{N-1}&s_{N}&s_{N+1}&\dots&s_{2N-3}&s_{2N-2}\end{array}\right]_{N\times N}\
.$

Denote by $S_{1},\dots,S_{N}=\det S$ its leading principal minors.

###### Theorem 2.1

One has

${\mathcal{D}}(F)=a_{0}^{2N-2}S_{N}\,.$ (2.5)

The condition

$S_{N}=0,\dots,S_{N-k+1}=0,S_{N-k}\neq 0$

is the necessary and sufficient for the polynomial $F(x)$ to possess $k$
common zeros with $F^{\prime}(x)$. In particular, if $S_{N}=0,S_{N-1}\neq 0$,
then $F(x)$ possesses a unique multiple zero and the multiplicity of this zero
equals $2$. This zero can be computed via the formula

$\lambda=s_{1}-\frac{1}{S_{N-1}}\left|\begin{array}[]{lllll}s_{0}&s_{1}&\dots&s_{N-3}&s_{N-1}\\\
s_{1}&s_{2}&\dots&s_{N-2}&s_{N}\\\ \vdots&&&&\vdots\\\
s_{N-2}&s_{N-1}&\dots&s_{2N-1}&s_{2N-3}\end{array}\right|\,.$ (2.6)

The determinant in the right-hand side is constructed by deleting the last row
and the last but one column in $\det S$.

Consequently, the set $\mathbb{D}$ of matrices with multiple eigenvalues is
given by the equation

$\mathcal{D}_{\lambda}\left(\det(\lambda I-B)\right)=0\,.$

For the case of polynomials with real coefficients, the sequence of leading
principal minors of the matrix $S$ permits one to establish the exact number
of real zeros for $F(x)$ [10].

######  Theorem 2.2 (Jacobi)

Let

$S_{N}=0,\dots,S_{N-k+1}=0,S_{N-k}\neq 0,\dots,S_{1}\neq 0$

Then the number of distinct pairs of complex-conjugate zeros for
$F(x)\in\mathbb{R}[x]$ equals

$\mathcal{V}(1,S_{1},\dots,S_{N-k})$

where $\mathcal{V}$ denotes the number of variations of sign in the given
sequence.

In the space $\mathbb{R}^{N+1}$ of polynomials (2.1) with real coefficients,
the discriminant manifold (2.2) separates the domains of vectors providing the
coefficients of polynomials with the same number of real zeros.

The last comment of the present section relates to application of discriminant
to one problem from Elimination Theory. Consider a bivariate polynomial
$F(x,y)\in\mathbb{R}[x,y],\deg F\geq 2$. The discriminant furnishes the tool
for eliminating the variable $x$ from the system of equations

$F(x,y)=0,{\partial F(x,y)}/{\partial x}=0\,.$ (2.7)

Namely, if $(x_{0},y_{0})$ is a solution to the system (2.7), then $y_{0}$ is
necessarily a zero of the algebraic univariate equation

$\mathcal{Y}(y)=0\ \mbox{ where }\ \mathcal{Y}(y):=\mathcal{D}_{x}(F(x,y))\,.$

The reverse statement is subject to an extra assumption. If
$y_{1}\in\mathbb{C}$ is a zero for $\mathcal{Y}(y)$, then there exists a
multiple zero for the polynomial $F(x,y_{1})$. Under the assumption that
$y_{1}$ is a simple zero for $\mathcal{Y}(y)$, $x_{1}$ is a unique multiple
zero and its multiplicity equals $2$. Then it can be expressed as a rational
function of $y_{1}$ using the result of Theorem 2.1. These considerations are
valid for all the solutions of the system (2.7) provided that
$\mathcal{D}_{y}(\mathcal{Y}(y))\neq 0$.

##  3 Distance Equation

In terms of the discriminant manifold referred to in the previous section, the
problem of evaluation of $d^{2}(A,\mathbb{D})$ is equivalent to that of
constrained optimization

$\min\|B-A\|^{2}\quad\mbox{subject to}\
\mathcal{D}_{\lambda}(f_{B}(\lambda))=0,\ B\in\mathbb{R}^{n\times n}\,.$

Here the constraint is an algebraic equation with respect to the entries of
the matrix $B$. Traditional application of the Lagrange multipliers method
reduces the problem to that of solving a system of $n^{2}+1$ nonlinear
algebraic equations. Under the additional assumption the matrix
$B_{\ast}\in\mathbb{R}^{n\times n}$ providing a solution to this system
possesses only one multiple eigenvalue and its multiplicity equals $2$, it is
possible to reduce the number of variables in the constrained optimization
approach. The following result is presented in [13]:

###### Theorem 3.1

The value $d^{2}(A,\mathbb{D})$ belongs to the set of critical values of the
objective function

$G(U):=U^{\top}AA^{\top}U-\left(U^{\top}AU\right)^{2}$ (3.1)

for the constrained optimization problem under constraints

$U^{\top}U=1,\ U\in\mathbb{R}^{n}\,.$ (3.2)

If $U_{\ast}$ be the point providing $d^{2}(A,\mathbb{D})$, then the
perturbation can be computed as

$E_{\ast}=U_{\ast}U_{\ast}^{\top}(\kappa I-A)\quad\mbox{ where}\
\kappa:=U_{\ast}^{\top}AU_{\ast}\,.$

The new optimization problem still have significant number of variables. We
aim to eliminate all of them but introduce an extra one responsible for the
critical values of the objective function.

Stationary points of the function (3.1) under the constraints (3.2) can be
found via Lagrange method applied to the function $G(U)-\mu(U^{\top}U-1)$.
This results into the system

$AA^{\top}U-(U^{\top}AU)(A+A^{\top})U-\mu U=\mathbb{O}_{n\times 1}\,.$ (3.3)

Denote

$\lambda:=U^{\top}AU\,.$ (3.4)

Then the equation (3.3) has a nontrivial solution with respect to $U$ if and
only if

$\det(AA^{\top}-\lambda(A+A^{\top})-\mu I)=0\,.$ (3.5)

Under this condition, multiplication of (3.3) by $U^{\top}$ yields

$U^{\top}AA^{\top}U=2\lambda^{2}+\mu\,.$

Wherefrom it follows that the critical values of the objective function (3.1)
are given by

$z=\lambda^{2}+\mu\,.$

Substitution this into (3.5) results in the equation connecting $z$ and
$\lambda$:

$\Phi(\lambda,z)=0$ (3.6)

where

$\Phi(\lambda,z):=\det\left[AA^{\top}-\lambda(A+A^{\top})+(\lambda^{2}-z)I\right]$
(3.7) $=\det\left[(\lambda I-A)(\lambda I-A)^{\top}-zI\right]$ (3.8)

Zeros $z_{1},\dots,z_{n}$ of the polynomial $\Phi(\lambda,z)$ with respect to
the variable $z$ are evidently real since they are the squares of the singular
values for the matrix $\lambda I-A$.

Our further task is to deduce an extra equation connecting $\lambda$ and $z$.

###### Theorem 3.2

The value $d^{2}(A,\mathbb{D})$ belongs to the set of non-negative zeros of
the polynomial

$\mathcal{F}(z)\equiv\mathcal{D}_{\lambda}(\Phi(\lambda,z))/z^{n}\,.$ (3.9)

Proof. Under the condition (3.6), there exists a nontrivial solution for (3.3)
with respect to the column $U$

$(\lambda I-A)(\lambda I-A)^{\top}U=z\,U\,.$ (3.10)

This equality means that $U$ is the right singular vector for the matrix
$\lambda I-A$ corresponding to the singular value $\sqrt{z}$. The
corresponding left singular vector for that matrix can be found from the
equality

$\sqrt{z}V:=(\lambda I-A)^{\top}U\,.$ (3.11)

Dual relationship is valid for $U$:

$\sqrt{z}U=(\lambda I-A)V\,.$ (3.12)

From the conditions (3.2) and (3.4) it follows that

$U^{\top}(\lambda I-A)U=0\,.$ (3.13)

Multiply (3.12) from the left by $U^{\top}$. From (3.2), it follows that

$\sqrt{z}=U^{\top}(\lambda I-A)V\,.$ (3.14)

Multiply (3.11) from the left by $V^{\top}$ and utilize (3.14):

$\sqrt{z}V^{\top}V=V^{\top}(\lambda I-A)^{\top}U=\sqrt{z}\,.$

Wherefrom the two alternatives follow

$V^{\top}V=1\quad\mbox{or}\quad\sqrt{z}=0\,.$

Similarly, multiplication of (3.11) from the left by $U^{\top}$ and further
application of (3.13) yields

$\sqrt{z}U^{\top}V=0\,.$

This also leads to two alternatives:

$U^{\top}V=0\quad\mbox{or}\quad\sqrt{z}=0\,.$

Ignore the case $\sqrt{z}=0$.

$V^{\top}V=1,\ U^{\top}V=0\,.$ (3.15)

Consider the equation (3.14) as a definition of the $\sqrt{z}$ as the function
of $\lambda$. Differentiate this relation with respect to $\lambda$:

$\frac{d\,\sqrt{z}}{d\,\lambda}=U^{\top}V+\frac{d\,U^{\top}}{d\,\lambda}(\lambda
I-A)V+U^{\top}(\lambda I-A)\frac{d\,V}{d\,\lambda}\,.$

With the aid of (3.11) and (3.12) transform this into

$U^{\top}V+\sqrt{z}\left[\frac{d\,U^{\top}}{d\,\lambda}U+V^{\top}\frac{d\,V}{d\,\lambda}\right]\,.$

Due to (3.2) and (3.15), we arrive at

$\frac{d\,\sqrt{z}}{d\,\lambda}=0\,.$ (3.16)

Equation (3.6) defines implicit function $z(\lambda)$. Differentiation of the
identity $\Phi(\lambda,z(\lambda))\equiv 0$ with respect to $\lambda$ yields
the identity

$\Phi^{\prime}_{\lambda}(\lambda,z)+\Phi^{\prime}_{z}(\lambda,z)\frac{d\,z}{d\,\lambda}\equiv
0\,.$

Under the condition (3.16), the variables $\lambda$ and $z$ are linked by an
extra relationship

$\Phi^{\prime}_{\lambda}(\lambda,z)=0\,.$ (3.17)

Together with (3.6), the deduced condition composes the system of algebraic
equations

$\Phi(\lambda,z)=0,\ \Phi^{\prime}_{\lambda}(\lambda,z)=0\,.$ (3.18)

According with the results of Section 2, elimination of $\lambda$ from this
system can be implemented with the aid of the discriminant computation, i.e.
the variable $z$ should satisfy the equation

$\mathcal{D}_{\lambda}(\Phi(\lambda,z))=0\,.$

To prove the validity of (3.9), it is necessary to additionally confirm that
the left-hand side of the last equation is divisible by $z^{n}$. This is
indeed the case, since the polynomial $\Phi(\lambda,0)$ possesses $n$ multiple
zeros coinciding with the eigenvalues of the matrix $A$.  $\Box$

With $\mathcal{F}(z)$ given by (3.9), the distance equation $\mathcal{F}(z)=0$
is now well-defined and in Section 4 we discuss some of related features and
computational aspects.

To conclude the present section, we have to detail the properties of the
$\lambda$-component for the solution of the system (3.18). Let the polynomial
$\mathcal{F}(z)$ defined by (3.9) possess a positive real zero $z_{0}$ and
this zero be simple. Then the polynomial $\Phi(\lambda,z_{0})$ has a unique
multiple zero and multiplicity of this zero equals $2$. We denote by
$\lambda_{0}$. It is evidently real and can be expressed as a rational
function of $z_{0}$ via, for instance, formula (2.6).

The less evident conclusion is as follows: this multiple zero coincides with
the multiple eigenvalue of the matrix in $\mathbb{D}$ providing the critical
value $z_{0}$ for the function $d^{2}(A,\mathbb{D})$.

###### Theorem 3.3

For any real solution $(\lambda_{0},z_{0})$ of the system (3.18) where
$z_{0}\neq 0$, there exists the rank $1$ perturbation $E_{0}$ such that
$\|E_{0}\|=\sqrt{z_{0}}$ and the matrix $B_{0}=A+E_{0}$ possesses the multiple
eigenvalue $\lambda_{0}$.

Proof. The number $\sqrt{z_{0}}$ is a singular value for the matrix
$\lambda_{0}I-A$. We intend to prove that the matrix from the theorem
statement is defined by the formula

$E_{0}:=\sqrt{z_{0}}U_{0}V_{0}^{\top}\,,$ (3.19)

where $U_{0}$ and $V_{0}$ are respectively the left and the right singular
vectors of the unit norm for the matrix $\lambda_{0}I-A$ corresponding to
$\sqrt{z_{0}}$.

Indeed, the matrix $B_{0}=A+E_{0}$ has $\lambda_{0}$ as the eigenvalue
corresponding to the eigenvector $V_{0}$:

$B_{0}V_{0}=(A+E_{0})V_{0}\stackrel{{\scriptstyle(\ref{eqEj})}}{{=}}AV_{0}+\sqrt{z_{0}}U_{0}\stackrel{{\scriptstyle(\ref{eqU})}}{{=}}AV_{0}+(\lambda_{0}I-A)V_{0}=\lambda_{0}V_{0}\,.$

If $\mathbf{rank}(B_{0}-\lambda_{0}I)<n-1$ then the theorem is proved. Assume
that $\mathbf{rank}(B_{0}-\lambda_{0}I)=n-1$. Let us prove the existence of a
column $W$ such that

$(B_{0}-\lambda_{0}I)W=V_{0}\,.$

The necessary and sufficient condition for resolving this equation consists in
the fulfillment of the equality

$(B_{0}-\lambda_{0}I)(B-\lambda_{0}I)^{+}V_{0}=V_{0}$ (3.20)

where $\mbox{ }^{+}$ stands for the Moore-Penrose inverse of the matrix. It
can be easily verified that

$(B_{0}-\lambda_{0}I)(B_{0}-\lambda_{0}I)^{+}=I-U_{0}U_{0}^{\top}$

(by assumption, $\mathbf{rank}(B_{0}-\lambda_{0}I)=n-1$), and the condition
(3.20) is fulfilled:

$(B_{0}-\lambda_{0}I)(B_{0}-\lambda_{0}I)^{+}V_{0}=(I-U_{0}U_{0}^{\top})V_{0}\stackrel{{\scriptstyle(\ref{eqVTUT})}}{{=}}V_{0}\,.$

The columns $V_{0}$ and $W$ are linearly independent. Indeed, if

$\alpha V_{0}+\beta W=\mathbb{O}_{n\times 1}\quad\mbox{for}\
\\{\alpha,\beta\\}\subset\mathbb{R}$

then on multiplying this equality from the left by $B_{0}-\lambda_{0}I$ it
follows that $\beta V_{0}=\mathbb{O}_{n\times 1}$, and thus $\beta=0$. But
then $\alpha=0$ since $V_{0}$ is a nonzero column.

Hence,

$(B_{0}-\lambda_{0}I)^{2}V_{0}=\mathbb{O},\
(B_{0}-\lambda_{0}I)^{2}W=\mathbb{O}$

for the linear independent $V_{0}$ and $W$. Consequently,
$\mathbf{rank}(B_{0}-\lambda_{0}I)^{2}\leq n-2$ and this gives evidence that
$\lambda_{0}$ should be a multiple eigenvalue for $B_{0}$.  $\Box$

###### Corollary 3.1

If $A\not\in\mathbb{D}$, then

$d(A,\mathbb{D})=\sqrt{z_{\ast}}\,,$

where $z_{\ast}$ is the minimal positive zero of the polynomial (3.9) provided
that this zero is not a multiple one. Minimal perturbation is evaluated by the
formula

$E_{\ast}=U_{\ast}U_{\ast}^{\top}(\lambda_{\ast}I-A)\,.$ (3.21)

Here $\lambda_{\ast}$ is the multiple zero for the polynomial
$\Phi(\lambda,z_{\ast})$ and $U_{\ast}\in\mathbb{R}^{n},\|U_{\ast}\|=1$ is the
left singular vector of the matrix $\lambda_{\ast}I-A$ corresponding to the
singular value $\sqrt{z_{\ast}}$.

The significance of condition for simplicity of the minimal positive zero
$z_{\ast}$ can be explained as follows. Since we are looking for only real
perturbations, formula (3.21) yields such a matrix if $\lambda_{\ast}$ is
real. For the matrices of the order $n\geq 4$, it might happen that the system
(3.18) possesses a solution $(z_{\ast},\lambda_{\ast})$ with an imaginary
$\lambda_{\ast}$ (we give an example of such a matrix in Section 6). Then the
system necessarily possesses the solution
$(z_{\ast},\overline{\lambda_{\ast}})$. This implies (v. the last comment from
Section 2) that $z_{\ast}$ should be a multiple zero for (3.9). Therefore, the
condition for simplicity of $z_{\ast}$is sufficient to prevent such an
occasion. Formal verification of this condition can be replaced by a more
general one relating the discriminant of $\mathcal{F}(z)$:

$\mathcal{D}_{z}(\mathcal{F}(z))\neq 0\,.$

##  4 Properties of the Distance Equation

###### Example 4.1

The distance equation for the matrix $A=[a_{jk}]_{j,k=1}^{2}$ is found in the
form

$\mathcal{F}(z):=16\left[(a_{11}-a_{22})^{2}+(a_{12}+a_{21})^{2}\right]\cdot\left\\{\left[4z-\mathcal{D}(f_{A}(\lambda))\right]^{2}-16(a_{12}-a_{21})^{2}z\right\\}=0\,.$

Polynomial in braces has only real zeros with respect to $z$ since its
discriminant equals

$256(a_{12}-a_{21})^{2}\left[(a_{11}-a_{22})^{2}+(a_{12}+a_{21})^{2}\right]\geq
0\,.$

$\Box$

Some terms in the canonical representation of the polynomial (3.6) can be
explicitly expressed via the entries of the matrix $A$:

$\Phi(\lambda,z)\equiv\lambda^{2n}-2\mathbf{tr}(A)\lambda^{2n-1}+(-nz+\mathbf{tr}(AA^{\top})+p_{2})\lambda^{2n-2}+\dots+\det(AA^{\top}-zI)\,.$
(4.1)

Here $p_{2}$ is the coefficient of $\lambda^{n-2}$ in the characteristic
polynomial $f_{A+A^{\top}}(\lambda):=\det(\lambda I-A-A^{\top})$. It happens
that this polynomial is also responsible for the order of the distance
equation.

###### Theorem 4.1

One has

$\mathcal{F}(z)\equiv
4^{n}\left[\mathcal{D}_{\lambda}(f_{A+A^{\top}}(\lambda))\right]^{2}z^{n(n-1)}+\mbox{lower
order terms in }\ z\,.$ (4.2)

Proof. Let $\\{\mu_{1},\dots,\mu_{n}\\}$ be the spectrum of the matrix
$A+A^{\top}$ while $P\in\mathbb{R}^{n\times n}$ be an orthogonal matrix
reducing it to the diagonal form:

$P^{\top}(A+A^{\top})P=\mathbf{diag}(\mu_{1},\dots,\mu_{n})\,.$

Apply the same transformation to the determinant (3.7):

$\Phi(\lambda,z)\equiv\det\left[P^{\top}AA^{\top}P+\mathbf{diag}(\lambda^{2}-\mu_{1}\lambda-z,\dots,\lambda^{2}-\mu_{n}\lambda-z)\,.\right]$

The leading term of the polynomial $\mathcal{D}_{\lambda}(\Phi(\lambda,z))$
with respect to $z$ coincide with that of

$\mathcal{D}_{\lambda}\left(\prod_{j=1}^{n}(\lambda^{2}-\mu_{j}\lambda-z)\right)\,.$

The set of zeros of the polynomial under the discriminant sign is as follows

$\left\\{\frac{1}{2}\left(\mu_{j}\pm\sqrt{\mu_{j}^{2}+4z}\right)\right\\}_{j=1}^{n}\,.$

Using the definition (2.3) of the discriminant, one gets

$\mathcal{D}_{\lambda}\left(\prod_{j=1}^{n}(\lambda^{2}-\mu_{j}\lambda-z)\right)=\prod_{j=1}^{n}(4\,z+\mu_{j}^{2})\prod_{1\leq
j<k\leq n}\left[z^{2}(\mu_{k}-\mu_{j})^{4}\right]\,.$

Coefficient of the monomial $z^{n^{2}}$ in the right-hand side can be
recognized, via (2.3), as the square of the discriminant of the characteristic
polynomial of $A+A^{\top}$.  $\Box$

As for the determining the structure of the free term of $\mathcal{F}(z)$, our
successes are restricted to the following

Hypothesis. If computed symbolically with respect to the entries of $A$,
$\mathcal{F}(0)$ has a factor
$\left[\mathcal{D}_{\lambda}(f_{A}(\lambda))\right]^{2}$.

According to Theorem 2.1, the polynomial $\mathcal{F}(z)$ can be constructed
in the form of determinant of a suitable Hankel matrix. For this aim, compute
first the Newton sums $\\{s_{j}(z)\\}_{j=0}^{4n-2}$ for the polynomial
$\Phi(\lambda,z)$ treated with respect to $\lambda$. Direct utilization of the
formulas (2.4) requires the canonical representation (4.1) for the polynomial
$\Phi(\lambda,z)$ while initially we have just only its representation in the
determinantal form (3.8). Fortunately, the Newton sums can be computed in an
alternative way. Indeed,

$\Phi(\lambda,z)\equiv\det(\lambda I_{2n}-W)\quad\mbox{where}\
W:=\left[\begin{array}[]{cc}A^{\top}&\sqrt{z}I_{n}\\\
\sqrt{z}I_{n}&A\end{array}\right]$

and it is known that the Newton sums of the characteristic polynomial of a
matrix can be computed as the traces of matrix powers:

$s_{j}(z)\equiv\mathbf{tr}(W^{j})\quad\mbox{for}\ j\in\\{0,1,\dots\\}$

Thus, one has

$s_{2}(z)=2(\mathbf{tr}(A^{2})+nz),\
s_{3}(z)=2(\mathbf{tr}(A^{3})+3\,z\,\mathbf{tr}(A)),\ \dots$

Compose the Hankel matrix

$S(z):=\left[s_{j+k}(z)\right]_{j,k=0}^{2n-1}$

and compute the sequence of its leading principal minors
$S_{1}(z),\dots,S_{2n}(z)$. Due to (2.5) and (3.9),

$S_{2n}(z)\equiv\mathcal{D}_{\lambda}(\Phi(\lambda,z))\equiv\mathcal{F}(z)z^{n}\,.$
(4.3)

Evidently, the polynomial $\Phi(\lambda,0)$ possesses only $n$ double zeros,
and they all are distinct provided that $A\not\in\mathbb{D}$. Consequently,
due to Theorem 2.1, one has $S_{n+1}(0)=0,\dots,S_{2n}(0)=0$.

###### Theorem 4.2

Polynomial $\mathcal{F}(z)$ does not have negative zeros. The number of its
positive zeros lying within the interval $[0,z_{0}],z_{0}>0$ is not less than

$|\mathcal{V}(1,S_{1}(z_{0}),\dots,S_{2n}(z_{0}))-\mathcal{V}(1,S_{1}(0),\dots,S_{n}(0))|\,.$
(4.4)

Proof. The first claim of the theorem follows from the positive definiteness
of the matrix $(\lambda I-A)(\lambda I-A)^{\top}-zI$ for $z<0$.

By Theorem 2.2, the number $\mathcal{V}(1,S_{1}(z_{0}),\dots,S_{2n}(z_{0}))$
equals the number of complex-conjugate pairs of zeros for the polynomial
$\Phi(\lambda,z_{0})$. When the parameter $z$ varies from $0$ to $z_{0}$, the
discriminant $\mathcal{D}_{\lambda}(\Phi(\lambda,z))$ vanishes at any value of
$z$ where a pair of real zeros of $\Phi(\lambda,z)$ transforms to a pair
complex-conjugate ones or vice versa. The discriminant vanishes at these
values.  $\Box$

Theorem 4.1 claims that the degree of the distance equation generically equals
$n(n-1)$. One can immediately watch that for the skew-symmetric matrix $A$
this estimation is not valid. Moreover, for this type of matrices, polynomial
$\mathcal{F}(z)$ vanishes identically. Some other types of matrices that
permit explicit representation for the polynomial $\Phi(\lambda,z)$, and, as a
consequence, for the value $d(A,\mathbb{D})$, in terms of the spectrum of $A$
can be found in [13]. We summarize those results in the following

###### Theorem 4.3

Let all the eigenvalues $\lambda_{1},\dots,\lambda_{n}$ of $A$ be distinct.
One has:

$\Phi(\lambda,z)\equiv\prod_{j=1}^{n}[(\lambda-c)^{2}-(\lambda_{j}-c)^{2}-z]\quad\mbox{for}\
A=\mbox{skew-symmetric}\ +cI_{n}\ ,$ (4.5)

where $c\in\mathbb{R}$ is an arbitrary scalar;

$\Phi(\lambda,z)\equiv\prod_{j=1}^{n}(\lambda^{2}-z+1-2\lambda\Re(\lambda_{j}))\quad\mbox{for
orthogonal}\ A\ \ ;$ (4.6)
$\Phi(\lambda,z)\equiv\prod_{j=1}^{n}\left[(\lambda-\lambda_{j})^{2}-z\right]\quad\mbox{for
symmetric}\ A\ .$ (4.7)

For the case (4.5), $\Phi(\lambda,z)$ has a multiple zero if $n\geq 2$. For
the case (4.6), $\Phi(\lambda,z)$ has a multiple zero if $n\geq 3$. For the
both cases, the distance $d(A,\mathbb{D})$ is attained at the continuum of
matrices in $\mathbb{D}$ [13].

###### Example 4.2

Find $d(A,\mathbb{D})$ for the skew-symmetric matrix

$A=\left[\begin{array}[]{rrrr}0&-4&2&-1\\\ 4&0&7&3\\\ -2&-7&0&11\\\
1&-3&-11&0\end{array}\right]\,.$

Solution. Here

$\Phi(\lambda,z)\equiv\left({\lambda}^{4}-2\,{\lambda}^{2}z+200\,{\lambda}^{2}+{z}^{2}-200\,z+3249\right)^{2}\,,$

and $\mathcal{D}_{\lambda}(\Phi(\lambda,z))\equiv 0$. However, if we take

$\mathcal{D}_{\lambda}(\sqrt{\Phi(\lambda,z)})=\mathcal{D}_{\lambda}({\lambda}^{4}-2\,{\lambda}^{2}z+200\,{\lambda}^{2}+{z}^{2}-200\,z+3249)$

the result is the true distance equation

$11667456256\,z^{2}-2333491251200\,z+37907565375744=0\,.$

Its least positive zero equals

$100-\sqrt{6751}=\frac{1}{4}(\sqrt{314}-\sqrt{86})^{2}$

where $\pm 1/2\mathbf{i}(\sqrt{314}-\sqrt{86})$ are the eigenvalues of $A$.
$\Box$

Remark. Similar trick works also for the case of orthogonal matrices.

##  5 Examples and Computational Aspects

Once the canonical form of the distance equation is computed, Wilkinson’s
problem is nearly solved. Indeed, for a univariate algebraic equation, the
exact number of real zeros, as well as their location, could be trustworthy
determined via purely algebraic procedures.

Remark. Theorem 4.1 claims that generically the degree of the distance
equation equals $n(n-1)$. The both examples below fall into this genericity.
For instance, one has $\deg\mathcal{F}(z)=870$ for $n=30$.

###### Example 5.1

Find $d(F_{n},\mathbb{D})$ for Frank’s matrix [9]

$F_{n}=\left[\begin{array}[]{cccccc}n&n-1&n-2&\dots&2&1\\\
n-1&n-1&n-2&\dots&2&1\\\ 0&n-2&n-2&\dots&2&1\\\ 0&0&n-3&\dots&2&1\\\
\vdots&\vdots&&\ddots&\vdots&\vdots\\\ 0&0&0&\dots&1&1\end{array}\right]\,.$
(5.1)

Solution. For $n=3$, one has

$\Phi(\lambda,z)={\lambda}^{6}-12\,{\lambda}^{5}+\left(-3\,z+48\right){\lambda}^{4}+\left(24\,z-74\right){\lambda}^{3}$
$+\left(3\,{z}^{2}-73\,z+48\right){\lambda}^{2}+\left(-12\,{z}^{2}+70\,z-12\right)\lambda-{z}^{3}+25\,{z}^{2}-33\,z+1$

and

$\mathcal{F}(z)=23839360000\,{z}^{6}-476315200000\,{z}^{5}+3522206312000\,{z}^{4}-11668368222400\,{z}^{3}$
$+16297635326400\,{z}^{2}-6895772352000\,z+230443315200\,.$

Distance equation has only real zeros, namely

$z_{1}\approx 0.036482,\ z_{2}\approx 0.648383,\ z_{3}\approx 2.316991,\
z_{4}\approx 4.954165,\ z_{5}\approx 5.274176,\ z_{6}=27/4=6.75\,.$

Thus, $d(F_{3},\mathbb{D})=\sqrt{z_{1}}\approx 0.191004$. To find the
corresponding perturbation via (3.21), first evaluate the multiple zero for
$\Phi(\lambda,z_{1})$ via (2.6):

$\lambda_{\ast}\approx 0.602966\,.$

Then evaluate the unit left singular vector of the matrix $\lambda_{\ast}I-A$
corresponding to $\sqrt{z_{1}}$:

$U_{\ast}\approx\left[0.639244,\,-0.751157,\,-0.164708\right]^{\top}$

Finally,

$E_{\ast}\approx\left[\begin{array}[]{rrr}-0.019161&-0.041159&0.113343\\\
0.022516&0.048365&-0.133186\\\
0.004937&0.010605&-0.029204\end{array}\right]\,.$

The nearest to $F_{3}$ matrix in $\mathbb{D}$

$B_{\ast}=F_{3}+E_{\ast}\approx\left[\begin{array}[]{rrr}2.980838&1.958840&1.113343\\\
2.022516&2.048365&0.866813\\\ 0.004937&1.010605&0.970795\end{array}\right]$

possesses the spectrum
$\\{\lambda_{\ast},\lambda_{\ast},6-2\lambda_{\ast}\approx 4.794067\\}$.

For $n>3$, the set of nonreal zeros for the distance equation becomes
nonempty, and its cardinality, relative to that of real, increases fastly with
$n$.

$n$ | $d(F_{n},\mathbb{D})\approx$ | coefficient size | number of real zeros | timing (s)
---|---|---|---|---
$5$ | $4.499950\ \times 10^{-3}$ | $\sim 10^{50}$ | $12$ | $-$
$10$ | $3.925527\times 10^{-8}$ | $\sim 10^{300}$ | $30$ | $-$
$12$ | $1.849890\times 10^{-10}$ | $\sim 10^{480}$ | $34$ | $0.13$
$20$ | $3.757912\times 10^{-21}$ | $\sim 10^{1690}$ | $62$ | $5$
$30$ | $1.638008\times 10^{-36}$ | $\sim 10^{4450}$ | $102$ | $30$

.

The results for $F_{10}$ and $F_{12}$ confirm estimations $d_{10}\approx
3.93\cdot 10^{-8}$ and $d_{12}\approx 1.85\cdot 10^{-10}$ given in [3].
$\Box$

###### Example 5.2

Find $d(K_{n},\mathbb{D})$ for Kahan’s matrix [3, 12]

$K_{n}=\left[\begin{array}[]{cccccc}1&-c&-c&\dots&-c&-c\\\
0&s&-sc&\dots&-sc&-sc\\\ 0&0&s^{2}&\dots&-s^{2}c&-s^{2}c\\\
&&\ddots&\dots&&\\\ 0&0&0&\ddots&s^{n-2}&-s^{n-2}c\\\
0&0&0&\dots&0&s^{n-1}\end{array}\right]\quad\mbox{for}\ s^{2}+c^{2}=1\,.$

Solution. We present computational results for two specialization of parameter
values. The first one is $s=3/5,c=4/5$:

$n$ | $d(K_{n},\mathbb{D})\approx$ | coefficient size | number of real zeros | timing (s)
---|---|---|---|---
$5$ | $1.370032\times 10^{-3}$ | $\sim 10^{310}$ | $8$ | $-$
$10$ | $5.470834\times 10^{-6}$ | $\sim 10^{2970}$ | $48$ | $-$
$15$ | $2.246949\times 10^{-8}$ | $\sim 10^{10590}$ | $138$ | $6.7$
$20$ | $9.245309\times 10^{-11}$ | $\sim 10^{25730}$ | $288$ | $145.4$
$25$ | $3.984992\times 10^{-10}$ | $\sim 10^{52910}$ | $258$ | $218.23$
$30$ | $1.240748\times 10^{-11}$ | $\sim 10^{92460}$ | $464$ | $937.66$

The second test series correspond to a specialization $s^{n-1}=1/10$ treated
in [3]. For this case, an extra difficulty results from approximation of the
entries of the matrix $K_{n}$ as rational numbers. This results in increasing
the length of the coefficients of the distance equation. Compared with the
previous case, the timing increases drastically, i.e. more than $10^{2}$ times
for the same specializations of $n$.

$n$ | $d(K_{n},\mathbb{D})\approx$ | number of real zeros
---|---|---
$6$ | $4.704940\times 10^{-4}$ | $10$
$10$ | $1.538157\times 10^{-5}$ | $18$
$15$ | $4.484974\times 10^{-7}$ | $28$
$20$ | $1.904858\times 10^{-8}$ | $38$

The results for $K_{6},K_{15}$ and $K_{20}$ confirm estimations given in [2].
$\Box$

It should be emphasized however that computation of the whole sets of real
zeros for the distance equation is redundant for evaluation of
$d(A,\mathbb{D})$. We need to find just only the least positive zero of
$\mathcal{F}(z)$. For this aim, the determinantal representation (4.3) for
this polynomial might be sufficient for the real zero localization. According
to Theorem 4.2, the lower estimate for the number of real zeros of
$\mathcal{F}(z)$ lying within the interval $[0,z_{0}],z_{0}>0$ is given by the
number (4.4). If this number is not zero then at least one real zero for
$\mathcal{F}(z)$ lies in $[0,z_{0}]$, and the next step in its localization
might be the treatment of the matrix $S(z_{0}/2)$.

Experiments with the Frank’s matrix (5.1) demonstrate the unambiguity of the
zero isolation process. For the matrix $F_{10}$, one has
$\mathcal{V}(1,S_{1}(0),\dots,S_{10}(0))=0$, i.e. all the eigenvalues of $A$
are real. Then (4.4) coincides with

$\mathcal{V}_{z_{0}}:=\mathcal{V}(1,S_{1}(z_{0}),\dots,S_{10}(z_{0}),\dots,S_{20}(z_{0}))\,.$

Some specializations for $z_{0}$

$z_{0}$ | $10^{-3}$ | $10^{-9}$ | $2\times 10^{-15}$ | $10^{-15}$
---|---|---|---|---
$\mathcal{V}_{z_{0}}$ | 5 | 3 | 1 | 0

demonstrate that the number of real zeros of $\mathcal{F}(z)$ lying in any
interval $[0,z_{0}]$ happens to be equal to $\mathcal{V}_{z_{0}}$. For
instance, there are precisely $5$ zeros within the interval $[0,10^{-3}]$,
namely

$1.540976\times 10^{-15},\ 7.739368\times 10^{-15},7.463686\times 10^{-13},\
1.403045\times 10^{-9},1.412301\times 10^{-5}\,.$

However, for the case of the matrix

$\left[\begin{array}[]{rrr}1&1&-2\\\ 2&1&0\\\ -3&1&1\end{array}\right]$

variations $\mathcal{V}_{0.4}=0,\mathcal{V}_{0.5}=1,\mathcal{V}_{2.25}=0$
permit one to locate single zeros within the intervals $[0.4,0.5]$ and
$[0.5,2.25]$ but are unable to detect this number for $[0.4,2.25]$.

##  6 Counterexamples

We exemplify here two cases

  * (a)

The minimal positive zero of the distance equation not always provides the
value $d^{2}(A,\mathbb{D})$ even if we restrict ourselves to the rank $1$
perturbation matrices;

  * (b)

The distance $d(A,\mathbb{D})$ is not always provided by the rank $1$
perturbations.

###### Example 6.1

For the matrix

$A(\epsilon)=\left[\begin{array}[]{cccc}0&1&1&0\\\ -1&0&0&1\\\
\epsilon&0&0&1\\\ 0&0&-1&0\end{array}\right]\,,$

find $d(A(\epsilon),\mathbb{D})$ for $\epsilon>0$.

Solution. Distance equation is provided by the polynomial

$\mathcal{F}(z)\equiv
65536\epsilon^{8}\left[(\epsilon+2)^{4}z^{2}-2\epsilon(\epsilon+8)(\epsilon+2)^{2}z+\epsilon^{2}(\epsilon-8)^{2}\right]^{2}\cdot\left[(\epsilon+1)z-3\epsilon-1\right]^{4}$
$\times(z^{2}-3\,z+1)\left[{z}^{2}-\left({\epsilon}^{2}+3\right)z+({\epsilon}+1)^{2}\right]\,.$

Its zeros are

$z_{1}=\frac{\epsilon(\sqrt{\epsilon}-\sqrt{8})^{2}}{(\epsilon+2)^{2}},\
z_{2}=\frac{\epsilon(\sqrt{\epsilon}+\sqrt{8})^{2}}{(\epsilon+2)^{2}},z_{3}=\frac{3\epsilon+1}{\epsilon+1},$
$z_{4}=\frac{3-\sqrt{5}}{2}\approx 0.381966,\
z_{5}=\frac{3+\sqrt{5}}{2}\approx 2.618033\,,$
$z_{6}=\frac{1}{2}\left({\epsilon}^{2}+3-|\epsilon-1|\sqrt{{\epsilon}^{2}+2\,{\epsilon}^{2}+5}\right),\
z_{7}=\frac{1}{2}\left({\epsilon}^{2}+3+|\epsilon-1|\sqrt{{\epsilon}^{2}+2\,{\epsilon}^{2}+5}\right)$

are all real. Zero $z_{4}$ is simple, it coincides with the square of a
singular value of the matrix $A$, and the polynomial $\Phi(\lambda,z_{4})$ has
the real double zero $\lambda_{4}=0$. The corresponding value of the distance
function from $A$ to $\mathbb{D}$ does not depend on $\epsilon$, it
equals333Amazing coincidence with the reciprocal to the golden ratio!

$\sqrt{z_{4}}=\frac{\sqrt{5}-1}{2}\approx 0.618033\,.$

The corresponding perturbation and matrix in $\mathbb{D}$ are as follows:

$E_{4}=\frac{1}{10}\left[\begin{array}[]{cccc}0&\sqrt{5}-5&(3\sqrt{5}-5&0\\\
0&0&0&0\\\ 0&0&0&0\\\
0&-2\sqrt{5}&5-\sqrt{5}&0\end{array}\right],B_{4}=\frac{1}{10}\left[\begin{array}[]{cccc}0&5+\sqrt{5}&5+3\sqrt{5}&0\\\
-10&0&0&10\\\ 10\epsilon&0&0&10\\\
0&-2\sqrt{5}&-5-\sqrt{5}&0\end{array}\right]\,.$

Double eigenvalue of $B_{4}$ is just $0$.

Next, we do not need to treat the zeros $z_{6},z_{7}$ and $z_{3}$, since they
are greater than $z_{4}$. Also $z_{2}>z_{1}$, therefore, the two zeros that
can compete for the distance value are $z_{1}$ and $z_{4}$. It can be verified
that

$z_{1}\leq z_{4}\ \mbox{iff}\ \epsilon\leq\epsilon_{2}\ \mbox{where}\
\epsilon_{2}=2\sqrt{2}(\sqrt{5}+3)\sqrt{\sqrt{5}+2}+7\sqrt{5}+15\approx
61.133652\,.$

It looks like $d(A,\mathbb{D})=\sqrt{z_{1}}$ for $\epsilon\leq\epsilon_{2}$.
However, this is not true for some subinterval in $[0,\epsilon_{2}]$. Indeed,
$z_{1}$ is a double zero for $\mathcal{F}(z)$, and polynomial
$\Phi(\lambda,z_{1})$ possesses two double zeros:

$\lambda_{1,2}=\pm\frac{\sqrt{K(\epsilon)}}{\epsilon+2}\quad\mbox{where}\
K(\epsilon):=\sqrt{2}(\epsilon-\sqrt{2}\sqrt{\epsilon}+2)\left(\sqrt{\epsilon}+\frac{1}{\sqrt{2}}\right)\left(\sqrt{\epsilon}+\frac{\sqrt{5}+1}{\sqrt{2}}\right)\left(\sqrt{\epsilon}-\frac{\sqrt{5}-1}{\sqrt{2}}\right)\,.$

These zeros are real only for

$\epsilon\geq\epsilon_{1}\ \mbox{where}\ \epsilon_{1}:=3-\sqrt{5}\approx
0.763932\,.$

For the values $\epsilon<\epsilon_{2}$, the minimal positive zero of the
distance equation is not responsible for the distance from $A$ to
$\mathbb{D}$.

It seems that $d(A,\mathbb{D})=\sqrt{z_{4}}$ for $\epsilon<\epsilon_{2}$.
However, this statement is also invalid for some subinterval of the parameter
values. The matrix

$\widetilde{E}(\epsilon):=\frac{\epsilon(8-\epsilon)}{(\epsilon^{2}+16)^{2}}\left[\begin{array}[]{cccc}0&-4\,\epsilon&{\epsilon}^{2}&0\\\
-4\,\epsilon&0&0&{\epsilon}^{2}\\\ -16&0&0&4\,\epsilon\\\
0&-16&4\,\epsilon&0\end{array}\right]$

represents a rank $2$ perturbation that provides for the matrix
$A(\epsilon)+\widetilde{E}(\epsilon)$ a pair of double eigenvalues

$\lambda_{1,2}=\pm\frac{1}{\epsilon^{2}+16}\sqrt{\left({\epsilon}^{2}+4\,\epsilon-16\right)\left(3\,{\epsilon}^{2}+4\,\epsilon+16\right)}\,.$

These eigenvalues are non-real for $\epsilon<2(\sqrt{5}-1)\approx 2.472136$.
For these parameter values, one has

$\|\widetilde{E}(\epsilon)\|=\frac{\sqrt{2}\epsilon(8-\epsilon)}{\epsilon^{2}+16}$

and this value is lesser than $\sqrt{z_{1}}$ for $\epsilon<\epsilon_{c}$ where
$\epsilon_{c}$ denotes the least positive zero of the polynomial

${\epsilon}^{8}-80\,{\epsilon}^{7}-368\,{\epsilon}^{6}-1024\,{\epsilon}^{5}+64\,{\epsilon}^{4}-9216\,{\epsilon}^{3}-16384\,{\epsilon}^{2}-32768\,\epsilon+65536\,;$

i.e. $\epsilon_{c}\approx 1.055249$.

Figure 1.

Summarizing:

$d(A(\epsilon),\mathbb{D})=\left\\{\begin{array}[]{cl}\sqrt{2}\epsilon(8-\epsilon)/(\epsilon^{2}+16)&\mbox{if}\
\epsilon\in[0,\epsilon_{c}]\\\
\sqrt{\epsilon}|\sqrt{\epsilon}-\sqrt{8}|/(\epsilon+2)&\mbox{if}\
\epsilon\in[\epsilon_{c},\epsilon_{2}]\\\ (\sqrt{5}-1)/2&\mbox{if}\
\epsilon>\epsilon_{2}\end{array}\right.$

The plot is displayed in Fig. 1 (the first formula — red, the second one —
blue, the third one — green).  $\Box$

Remark. As it is mentioned in Introduction, the case where $d(A,\mathbb{D})$
is achieved at the rank $2$ matrix (i.e. the nearest in $\mathbb{D}$ matrix
possesses two double imaginary eigenvalues) is beyond our consideration. We
are not able even to conjecture whether this is a zero probability event or
not.

##  7 Complex Perturbations

The method proposed above can be extended to the case of complex
perturbations. For a real matrix $A$, we are now looking for the distance to
the nearest complex matrix $B$ with multiple eigenvalue:

$d_{C}(A,\mathbb{D}):=\min\|B-A\|\quad\mbox{subject to}\
\mathcal{D}_{\lambda}(f_{B}(\lambda))=0,\ B\in\mathbb{C}^{n\times n}\,.$

Warning. The present section should be considered as a draft of a separate
publication to be prepared sometime afterwards. We skip here the details of
algebraic backgrounds, proofs of theoretical results and do not bother
ourselves with mentioning that the validity of some of the declared results is
subject to several extra assumptions preventing the appearance of troubles
similar to those dealt with in the previous section.

Consider the polynomial

$\Theta(a,b,z)=\det\left[\left((a+b\mathbf{i})I-A\right)\left((a-b\mathbf{i})I-A^{\top}\right)-zI\right]\,$
(7.1)

and generate the system of algebraic equations

$\Theta=0,\ \partial\Theta/\partial a=0,\ \partial\Theta/\partial b=0\,.$
(7.2)

We are looking for the real solutions to this system. Since

$\Theta(a,0,z)\stackrel{{\scriptstyle(\ref{eqPhi})}}{{\equiv}}\Phi(a,z)\,,$

this solution set includes that for the system (3.18).

###### Theorem 7.1

If the system (7.2) possesses a solution $(a_{0},b_{0},z_{0})$ with $b_{0}\neq
0$ then it has the solution $(a_{0},-b_{0},z_{0})$.

Proof.  Polynomial $\Theta(a,b,z)$ is even in $b$:

$\Theta(a,-b,z)=\det\left[((a+\mathbf{i}b)I-A^{\top})((a-\mathbf{i}b)I-A)-zI\right]$
$=\det\left[\left\\{((a+\mathbf{i}b)I-A^{\top})((a-\mathbf{i}b)I-A)\right\\}^{\top}-zI\right]$
$=\det\left[((a-\mathbf{i}b)I-A^{\top})((a+\mathbf{i}b)I-A)-zI\right]=\Theta(a,b,z)\,.$

Consequently $\Theta^{\prime}_{a}$ is even in $b$ while $\Theta^{\prime}_{b}$
is odd $b$. The latter becomes even on dividing by $b$.  $\Box$

Our aim is to eliminate the variables $a$ and $b$ from the system (7.2), i.e.
to find the bivariate discriminant  $\mathcal{D}_{a,b}(\Theta)$ for the
polynomial $\Theta(a,b,z)$ treated with respect to these variables.

The discriminant $\mathcal{D}_{x,y}(F)$ of a polynomial
$F(x,y,z)\in\mathbb{C}[x,y,z]$ is formally defined as the result of
elimination of variables $x$ and $y$ from the system of equations

$F=0,\ \partial F/\partial x=0,\ \partial F/\partial y=0\,.$ (7.3)

This is a polynomial in $z$ and its vanishment at $z=z_{0}\in\mathbb{C}$ is
the necessary and sufficient condition for the existence of solution
$(x_{0},y_{0},z_{0})\in\mathbb{C}^{3}$ to the system (7.3), or equivalently,
for the existence of the multiple zero $(x_{0},y_{0})$ for the polynomial
$F(x,y,z_{0})$. Constructive computation of discriminant can be implemented in
several ways, and we will exemplify below the procedure based of the Bézout
construction of the resultant [6].

###### Theorem 7.2

The discriminant $\mathcal{D}_{a,b}(\Theta(a,b,z))$ is factorized as follows:

$\mathcal{D}_{a,b}(\Theta(a,b,z))\equiv
z^{n(n+1)/2}\mathcal{F}(z)\widetilde{\mathcal{F}}(z)\,.$ (7.4)

Here $\mathcal{F}(z)$ is defined by (3.9), while

$\widetilde{\mathcal{F}}(z)\in\mathbb{R}[z],\
\deg\widetilde{\mathcal{F}}(z)=n(n-1)(n-2)/2\,,$

(For $n=2$ polynomial $\widetilde{\mathcal{F}}(z)$ is just a constant).

According to Section 3, the distance equation $\mathcal{F}(z)=0$ is
responsible for the rank $1$ real perturbation that provides the distance
$d(A,\mathbb{D})$. It turns out that the equation

$\widetilde{\mathcal{F}}(z)=0$

is responsible for the rank $1$ imaginary perturbation. Its real zero
$\widetilde{z}_{0}$ corresponds to a pair of multiple zeros of the polynomial
$\Theta(a,b,\widetilde{z}_{0})$, and these zeros are either in the form
$(a_{0},\pm\beta_{0})$ or in the form $(a_{0},\pm\mathbf{i}\beta_{0})$ with
real $\beta_{0}$. We are definitely interested only in the real solutions for
the system (7.2).

###### Theorem 7.3

Let the system (7.2) possess a real solution $(a_{0},b_{0},\widetilde{z}_{0})$
with $\widetilde{z}_{0}>0,b_{0}\neq 0$. Denote
$U_{0}\in\mathbb{C}^{n},\|U_{0}\|=1$ the left singular vector for the matrix
$(a_{0}+\mathbf{i}b_{0})I-A$ corresponding to the singular value
$\sqrt{\widetilde{z}_{0}}$. Then the rank $1$ perturbation

$E_{0}=U_{0}U_{0}^{\mathsf{H}}((a_{0}+\mathbf{i}b_{0})I-A)$ (7.5)

is such that $\|E_{0}\|=\sqrt{\widetilde{z}_{0}}$ and the matrix
$B_{0}=A+E_{0}\in\mathbb{C}^{n\times n}$ possesses the double eigenvalue
$a_{0}+\mathbf{i}b_{0}$.

Remark. Evidently, the matrix $\overline{E_{0}}$ provides for the matrix
$\overline{B_{0}}=A+\overline{E_{0}}$ the double eigenvalue
$a_{0}-\mathbf{i}b_{0}$.

In view of Theorem 7.3, the distance $d_{C}(A,\mathbb{D})$ results from the
competition between the least positive zero of $\mathcal{F}(z)$ and that
minimal positive zero of $\widetilde{\mathcal{F}}(z)$ that corresponds to the
real solution for the system (7.2).

Computation of the polynomial $\widetilde{\mathcal{F}}(z)$ can be simplified
if we take into account Theorem 7.1. Substitute

$\mathfrak{b}:=b^{2}$

in the polynomials of the system (7.2) and denote

$\Xi(a,\mathfrak{b},z):=\Theta(a,b,z),\
\Xi_{a}(a,\mathfrak{b},z):=\Theta^{\prime}_{a}(a,b,z),\
\Xi_{\mathfrak{b}}(a,\mathfrak{b},z):=\Theta^{\prime}_{b}(a,b,z)/b\,.$

###### Theorem 7.4

The result of elimination of variables $a$ and $\mathfrak{b}$ from the system

$\Xi=0,\ \Xi_{a}=0,\Xi_{\mathfrak{b}}=0$ (7.6)

is the equation

$z^{n(n-1)/2}\widetilde{\mathcal{F}}(z)=0\,.$

If $\widetilde{z}_{0}$ is a positive zero of $\widetilde{\mathcal{F}}(z)$, the
corresponding real solution to the system (7.6) might have the
$\mathfrak{b}$-component either positive or negative. We are interested only
in the positive variant.

###### Example 7.1

Find $d_{C}(A,\mathbb{D})$ for

$A=\left[\begin{array}[]{rrr}0&1&0\\\ 0&0&1\\\
-91&-55&-13\end{array}\right]\,.$

Solution. First compute the polynomial $\mathcal{F}(z)$ via (3.9):

$\mathcal{F}(z):=33076090700402342058246544\,z^{6}-377039198861306289080145178864\,z^{5}$
$+937864902703881321034450183916\,z^{4}-771868276098720970149792503999\,z^{3}$
$+211070978787821517684022650624\,z^{2}$
$-510584100140452518540394496\,z+319295875259784560640000\,.$

Its real zeros are as follows

$z_{1}\approx 0.739336,\ 0.765571,\ 0.980468,\ 11396.658548\,.$

Next compose the polynomial $\Xi(a,\mathfrak{b},z)$:

$\Xi(a,\mathfrak{b},z)=-z^{3}+(3a^{2}+3\mathfrak{b}+26a+11477)z^{2}$
$-(3\,a^{4}+6\,a^{2}\mathfrak{b}+3\,\mathfrak{b}^{2}+52a^{3}+52a\mathfrak{b}+11756a^{2}+11536\mathfrak{b}+11466\,a+19757)z$
$+\left({a}^{2}+\mathfrak{b}+14\,a+49\right)\left(({a}^{2}+\mathfrak{b}+6\,a+13)^{2}-16\,\mathfrak{b}\right)\,.$

Now we trace briefly the procedure of elimination of $a$ and $\mathfrak{b}$
from the system (7.6). Consider the monomial sequence

$\mathbb{M}:=\\{\mathfrak{m}_{j}(a,\mathfrak{b})\\}=\\{1,a,\mathfrak{b},\mathfrak{b}^{2}\\}\,.$

It is possible to reduce the polynomial $\mathfrak{m}_{j}\Xi$ modulo $\Xi_{a}$
and $\Xi_{\mathfrak{b}}$, i.e. to find the polynomials
$\\{\beta_{jk}(z)\\}_{j,k=1}^{4}\subset\mathbb{R}[z]$ and
$\\{p_{11}(a,\mathfrak{b},z),p_{j2}(a,\mathfrak{b},z)\\}_{j=1}^{4}\subset\mathbb{R}[a,\mathfrak{b},z]$
satisfying the identity

$m_{j}\Xi\equiv\beta_{j1}(z)+\beta_{j2}(z)a+\beta_{j3}(z)\mathfrak{b}+\beta_{j4}(z)\mathfrak{b}^{2}+p_{j1}\Xi_{a}+p_{j2}\Xi_{\mathfrak{b}}\
\mbox{for}\ j\in\\{1,2,3,4\\}\,.$

For instance,

$\beta_{11}(z)=-17718805921\,z^{2}+610367232\,z+22937600,\
\beta_{12}(z)=-39353600\,z+5324800,\ $
$\beta_{13}(z)=146694400\,z-512000,\beta_{14}(z)=-307200,\dots,$
$\beta_{44}(z)=-{\scriptstyle 76550493273549926400}\,z^{3}+{\scriptstyle
162810741053705011200}\,z^{2}-{\scriptstyle
1867736871075840000}\,z-{\scriptstyle 50331648000000}\,.$

Compose the Bézout matrix

$\mathfrak{B}(z):=\left[\beta_{jk}(z)\right]_{j,k=1}^{4}\,.$

Then

$\det\mathfrak{B}(z)\equiv z^{3}\widetilde{\mathcal{F}}(z)$

where

$\widetilde{\mathcal{F}}(z)=412324266119803814719539025\,{z}^{3}+33923334498676415590177600\,{z}^{2}$
$+691077589890510378371072\,z-899669298077697638400\,.$

For any zero $\widetilde{z}_{0}$ of this polynomial, the corresponding $a$ and
$\mathfrak{b}$ components of the solution to the system (7.6) can be obtained
in the following way. Denote by $\\{\mathfrak{B}_{4j}\\}_{J=1}^{4}$ the
cofactors of $\det\mathfrak{B}$ corresponding to the entries of the last row
of the matrix $\mathfrak{B}$. Then the $a$-component of solution is connected
with the $z$-component as

$a=\frac{\mathfrak{B}_{42}}{\mathfrak{B}_{41}}=\frac{43719663040898080379\,{z}^{2}+2929017747573439808\,z+29336262189312000}{2(624300876564482975\,z^{2}-226254560538037856\,z-3469512291865600)}$

while the $\mathfrak{b}$-component as

$\mathfrak{b}=\frac{\mathfrak{B}_{43}}{\mathfrak{B}_{41}}=\frac{{\scriptstyle
3083432482762007609519}\,{z}^{3}+{\scriptstyle
1101690698089389073600}\,{z}^{2}+{\scriptstyle
67186386329988787456}\,z-{\scriptstyle
129087561954918400}}{16(624300876564482975\,z^{2}-226254560538037856\,z-3469512291865600)}$

Polynomial $\widetilde{\mathcal{F}}(z)$ possesses a single real zero,
namely444All the decimals in the following approximation are error-free.

$\widetilde{z}_{1}\approx 0.0012268490707391199222512104943\,,$

and substitution of this value into the last formulas yields

$a=a_{1}\approx-4.403922040624116177182912013601,\
\mathfrak{b}=\mathfrak{b}_{1}\approx 0.750705046015830894563798035515\,.$

Since $\mathfrak{b}_{1}>0$, one may claim that

$d_{C}(A,\mathbb{D})=\sqrt{\widetilde{z}_{1}}\approx
0.035026405335676681771543151648\,.$

The two perturbations in $\mathbb{C}^{3\times 3}$ providing this distance
correspond to the solutions

$(a_{1},b_{1},\widetilde{z}_{1})\ \mbox{and}\
(a_{1},-b_{1},\widetilde{z}_{1})\ \mbox{where}\ \
b_{1}=\sqrt{\mathfrak{b}_{1}}\approx 0.866432366671415902596255690462\,.$

of the system (7.2). Let us compute via (7.5) the one corresponding to
$(a_{1},-b_{1},\widetilde{z}_{1})$. The unit left singular vector of
$(a_{1}-\mathbf{i}b_{1})I-A$ corresponding to the singular value
$\sqrt{\widetilde{z}_{1}}$ is as follows

$U_{1}\approx\left[0.930609,\ 0.360923+0.039918\,\mathbf{i},\
0.045052+0.008866\,\mathbf{i}\right]^{\top}$

and the minimal perturbation

$E_{1}\approx\left[\begin{array}[]{ccc}0.001289-0.000442\mathbf{i}&-0.007120+0.000832\mathbf{i}&0.031666+0.002551\mathbf{i}\\\
0.000519-0.000116\mathbf{i}&-0.002797+0.000017\mathbf{i}&0.012172+0.002348\mathbf{i}\\\
0.000067-0.000009\mathbf{i}&-0.000353-0.000028\mathbf{i}&0.001509+0.000425\mathbf{i}\end{array}\right]\,.$

The spectrum of the matrix $A+E_{1}$ is

$\\{a_{1}-\mathbf{i}b_{1},a_{1}-\mathbf{i}b_{1},-13-2(a_{1}-\mathbf{i}b_{1})\approx-4.192156-1.732865\mathbf{i}\\}\,.$

$\Box$

To test the performability of the algorithm sketched in the present section,
we chose the next matrix from the Matlab gallery(′grcar′,6).

###### Example 7.2

Find $d_{C}(A,\mathbb{D})$ for

$A=\left[\begin{array}[]{rrrrrr}1&1&1&1&0&0\\\ -1&1&1&1&1&0\\\ 0&-1&1&1&1&1\\\
0&0&-1&1&1&1\\\ 0&0&0&-1&1&1\\\ 0&0&0&0&-1&1\end{array}\right]\,.$

Solution. Here the minimal zero of $\mathcal{F}(z)$ equals $z_{1}\approx
0.116565$ and that of $\widetilde{\mathcal{F}}(z)$ equals

$\widetilde{z}_{1}\approx 0.04630491415327188209539627157\,.$

The latter corresponds to the real solution for the system (7.2):

$(a_{1},\pm b_{1},\widetilde{z}_{1})\ \mbox{where}\ a_{1}\approx 0.753316,\
b_{1}\approx-1.591155\,.$

Thus, one obtains

$d_{C}(A,\mathbb{D})=\sqrt{\widetilde{z}_{1}}\approx
0.2151857666140395125353\,.$

This confirms estimation $d_{C}(A,\mathbb{D})\approx 0.21519$ from [2, 3].

For the solution $(a_{1},b_{1},\widetilde{z}_{1})$, the spectrum of the
nearest to $A$ matrix in $\mathbb{D}$ is as follows

$\\{0.361392-1.944783\mathbf{i},1.139422-1.239762\mathbf{i},1.502453-0.616966\mathbf{i},1.490100+0.619201\mathbf{i},a_{1}+\mathbf{i}b_{1},a_{1}+\mathbf{i}b_{1}\\}\,.$

##  8 Conclusion

We have investigated Wilkinson’s problem for the distance evaluation from a
given matrix to the set of matrices possessing multiple eigenvalues. The
proposed approach consists in the construction of distance equation with the
zero set containing the critical values of the squared distance function. This
construction is realized in the ideology of symbolic computations, i.e. the
procedure consists of a finite number of elementary algebraic operations on
the entries of the matrix.

The representation of the distance equation with the aid of the discriminant
function should not be taken as a complete surprise. Indeed, the Wilkinson’s
problem is the one of evaluation the distance to the discriminant manifold in
the space of matrix entries. Hence, in view of this circumstance, the
appearance of the discriminant in a solution to the problem is somehow
natural. The more astonishing is the emergence of the discriminant in nearly
any problem of distance evaluation from a point to an algebraic manifold in a
multidimensional space [21, 22].

Direction for further research is clearly related the stuff of Section 6, i.e.
the problem of existence the rank $2$ minimal perturbation providing
$d(A,\mathbb{D})$.

## References

  * [1] Ahmad, Sk.S., Alam, R.: On Wilkinson’s problem for matrix pencils. ELA, 30, pp. 632–648 (2015)
  * [2] Akinola, R. O., Freitag, M. A., Spence A.: The calculation of the distance to a nearby defective matrix. Numerical Linear Algebra with Applications. 21:3, pp. 403–414 (2014)
  * [3] Alam, R., Bora, S.: On sensitivity of eigenvalues and eigendecompositions of matrices. Linear Algebra Appl. 396, pp. 273–301 (2005)
  * [4] Alam, R., Bora, S., Byers, R., Overton, M. L.: Characterization and construction of the nearest defective matrix via coalescence of pseudospectral components. Linear Algebra Appl. 435, pp. 494–513 (2011)
  * [5] Armentia, G., Gracia, J.-M., Velasco, F.-E.: Nearest matrix with a prescribed eigenvalue of bounded multiplicities. Linear Algebra Appl., 592, 188–209 (2020)
  * [6] Bikker P., Uteshev A.Yu.: On the Bézout construction of the resultant. J.Symbolic Comput., 1999, 28, No 1. 45–88 (1999)
  * [7] Demmel, J.W.: Computing stable eigendecompositions of matrices. Linear Algebra Appl., 79, pp. 163–193 (1986)
  * [8] Demmel, J.W.: On condition numbers and the distance to the nearest ill-posed problem, Numer.Math. 51, pp. 251–289 (1987)
  * [9] Frank, W.L.: Computing eigenvalues of complex matrices by determinant evaluation and by methods of Danilewski and Wielandt. J. Soc. Indust. Appl. Math. 6(4), pp. 378–392 (1958).
  * [10] Gantmacher, F.R.: The Theory of Matrices. Chelsea, New York (1959)
  * [11] Gracia, J.-M.: Nearest matrix with two prescribed eigenvalues. Linear Algebra Appl. 401, pp. 277–294 (2005)
  * [12] Kahan, W.: Numerical linear algebra. Canad. Math. Bull. 9, pp. 757–801 (1966)
  * [13] Kalinina, E., Uteshev, A.: Distance evaluation to the set of matrices with multiple eigenvalues. LNCS, 13366. Springer, Cham, pp.206–224 (2022)
  * [14] Kokabifar, E., Loghmani, G.B., Karbassi, S.M.: Nearest matrix with prescribed eigenvalues and its applications. J. Comput. Appl. Math. 298, pp. 53–63 (2016)
  * [15] Lippert, R.A.: Fixing multiple eigenvalues by a minimal perturbation. Linear Algebra Appl. 432, pp. 1785–1817 (2010)
  * [16] Lippert, R.A., Edelman, A.: The computation and sensitivity of double eigenvalues, in: Z. Chen, Y. Li, C.A. Micchelli, Y. Xu (Eds.), Advances in Computational Mathematics: Proc. Gaungzhou International Symposium, Dekker, New York, pp. 353–393 (1999)
  * [17] Malyshev, A.: A formula for the 2-norm distance from a matrix to the set of matrices with multiple eigenvalues. Numer. Math. 83, pp. 443–454 (1999)
  * [18] Mengi, E.: Locating a nearest matrix with an eigenvalue of prespecified algebraic multiplicity. Numer. Math. 118, pp. 109–135 (2011)
  * [19] Ruhe, A.: Properties of a matrix with a very ill-conditioned eigenproblem. Numer. Math. 15, pp. 57–60 (1970)
  * [20] Trefethen, L. N., Embree, M.: Spectra and Pseudospectra, Princeton University Press, Princeton, NJ (2005)
  * [21] Uteshev, A.Yu., Cherkasov, T.M.: The search for the maximum of a polynomial.J. Symbolic Comput. 25 (5). pp. 587–618 (1998)
  * [22] Uteshev, A.Yu., Yashina M.V.: Metric problems for quadrics in multidimensional space. J.Symbolic Comput., 68, Part I, pp. 287–315 (2015)
  * [23] Wilkinson, J.H.: The Algebraic Eigenvalue Problem, Oxford University Press, New York (1965)
  * [24] Wilkinson, J.H.: Note on matrices with a very ill-conditioned eigenproblem. Numer. Math. 19, 176–178 (1972)
  * [25] Wilkinson, J.H.: On neighbouring matrices with quadratic elementary divisors, Numer. Math. 44, 1–21 (1984)
  * [26] Wilkinson, J.H.: Sensitivity of eigenvalues, Util. Math. 25, 5–76 (1984)