You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


---
abstract: 'In matrix analysis, the *Wielandt-Mirsky conjecture* states that $$\dist(\sigma(A), \sigma(B)) \leq  \|A-B\|,$$ for any normal matrices $ A, B \in \mathbb C^{n\times n}$ and any operator norm $\|\cdot \|$ on $C^{n\times n}$. Here $\dist(\sigma(A), \sigma(B))$ denotes the optimal matching distance between the spectra of the matrices $A$ and $ B$. It was proved by A.J. Holbrook (1992) that this conjecture is *false* in general. However it is true for the Frobenius distance and the Frobenius norm (the *Hoffman-Wielandt inequality*). The main aim of this paper is to study the Hoffman-Wielandt inequality and some weaker versions of the Wielandt-Mirsky conjecture for matrix polynomials.'
address: |
    Department of Mathematics, Quy Nhon University\
    170 An Duong Vuong, Quy Nhon, Binh Dinh, Vietnam
author:
- 'CÔNG-TRÌNH LÊ'
title: 'On Wielandt-Mirsky’s conjecture for matrix polynomials'
---

Introduction
============

Let $\mathbb C^{n\times n}$ denote the set of all $n\times n$ matrices whose entries in $\mathbb C$. Let $A, B \in \mathbb C^{n \times n}$ be complex matrices whose spectra are $\sigma(A)=\{\alpha_1,\cdots,\alpha_n\}$ and $\sigma(B)=\{\beta_1\cdots,\beta_n\}$, respectively. The *optimal matching distance* between $\sigma(A)$ and $\sigma(B)$ is defined by $$\dist(\sigma(A),\sigma(B)):=\min_\theta \max_{j=1,\cdots,n} |\alpha_j - \beta_{\theta(j)}|,$$ where the minimum is taken over all permutations $\theta$ on the set $\{1,\cdots,n\}$.

One of the interesting conjectures in matrix analysis is the *Wielandt-Mirsky conjecture* [@Bh2007] which states that for any normal matrices $ A, B \in \mathbb C^{n\times n}$, $$\label{conjecture}
\dist(\sigma(A), \sigma(B)) \leq  \|A-B\|,$$ where $\|\cdot \|$ denotes the operator bound norm.

This conjecture has been proved to be true in the following special cases (cf. [@Ho]):

-   $A$ and $B$ are Hermitian (Weyl, 1912);

-   $A$, $B$ and $A-B$ are normal (Bhatia, 1982);

-   $A$ is Hermitian and $B$ is skew-Hermitian (Sunder, 1982);

-   $A$ and $B$ are constant multiples of unitaries (Bhatia and Holbrook, 1985).

It has been proven by Holbrook (1992, [@Ho]) that this conjecture is *false* in general. However, if we replace the optimal matching distance $\dist(\sigma(A), \sigma(B)) $ by the *Frobenius distance* between the spectra of the matrices $A$ and $B$, $$\dist_F(\sigma(A), \sigma(B)):=\min_\theta \big[\sum_{j=1}^n |\alpha_j - \beta_{\theta(j)}|^2\big]^{\frac{1}{2}},$$ then we have the following *Hoffman-Wielandt inequality* [@HoWie] $$\label{Hoffman-Wielandt}
\dist_F(\sigma(A), \sigma(B))\leq |A-B|_F$$ for any normal matrices $A$ and $B$. Here $|A-B|_F$ denotes the *Frobenius norm* of the matrix $A-B$.

It is clear that $$\dist(\sigma(A),\sigma(B)) \leq \dist_F(\sigma(A),\sigma(B)) \leq \sqrt{n}\cdot \dist(\sigma(A),\sigma(B)).$$ Therefore it follows from the Hoffman-Wielandt inequality that *the Wielandt-Mirsky conjecture is true for the Frobenius norm*.

A weaker version of the Wielandt-Mirsky conjecture was proved by R. Bhatia, C. Davis and A. Mcintosh (1983, [@BDM1983]) that there exists a universal constant $c$ such that for any normal matrices $A, B \in \mathbb C^{n \times n}$ we have $$\label{universal-constant}
\dist(\sigma(A), \sigma(B))\leq c \|A-B\|.$$

If we don’t require the universality of the constant $c$ in the above inequality, for any normal matrix $A\in \mathbb C^{n\times n}$ and for any $B\in \mathbb C^{n\times n}$, we have (cf. [@Bh2007 p. 4]) $$\label{Anormal-Barbitrary}
\dist(\sigma(A),\sigma(B))\leq (2n-1)\|A-B\|.$$

If $A$ is Hermitian and $B$ is arbitrary, we have the following inequality due to W. Kahan ([@K1967 p.166]: $$\label{Eq-Kahan}
\dist(\sigma({A}), \sigma({B})) \leq (\gamma_{n}+2)\|{A}-{B}\|,$$ where $\gamma_n$ is a constant depending on the size $n$ of the matrices.

For a *matrix polynomial* we mean the matrix-valued function of a complex variable of the form $$\label{mp}
P(z)= A_m z^m + \cdots + A_1 z + A_0,$$ where $A_i\in \mathbb C^{n\times n}$ for all $i=0,\cdots,m$. If $A_m\not =0$, $P(z)$ is called a *matrix polynomial of degree $m$*. When $A_m=I$, the identity matrix in $\mathbb C^{n \times n}$, the matrix polynomial $P(z)$ is called a *monic*.

A number $\lambda \in \mathbb C$ is called an *eigenvalue* of the matrix polynomial $P(z)$, if there exists a nonzero vector $x\in \mathbb C^n$ such that $P(\lambda)x=0$. Then the vector $x$ is called, as usual, an *eigenvector* associated to the eigenvalue $\lambda$. Note that each eigenvalue of $P(z)$ is a root of the *characteristic polynomial* $\det(P(z))$.

For an $(m+1)$-tuple $\bold{A}=(A_0,\cdots,A_m)$ of matrices $A_i\in \mathbb C^{n\times n}$, the matrix polynomial $$P_\bold{A}(z):= A_m z^m + \cdots + A_1 z + A_0$$ is called the *matrix polynomial associated to $\bold{A}$*.

The *spectrum* of the matrix polynomial $P_{\bold{A}}(z)$ is defined by $$\sigma(\bold{A}):=\sigma\big(P_{\bold{A}}(z)\big)=\{\lambda \in \mathbb C | \det(P_\bold{A}(\lambda))=0\},$$ which is the set of all its eigenvalues. We should observe that for a matrix $A\in \mathbb C^{n \times n}$, its usual spectrum $\sigma(A)$ is actually the spectrum of the monic matrix polynomial $I z - A$. Interested readers may refer to the book of I. Gohberg, P. Lancaster and L. Rodman [@GLR1982] for the theory of matrix polynomials and applications.

The main goal of this paper is to give some versions of the Wielandt-Mirsky conjecture for matrix polynomials.

The paper is organized as follows. In Section \[section2\] we establish some Wielandt’s inequalities for matrix polynomials. In Section \[section3\] we give some weaker versions of the Wielandt-Mirsky conjecture for monic matrix polynomials and for matrix polynomials whose leading coefficients are non-singular.

[**Notation and conventions.**]{} Throughout this paper, by a positive integer $p$ we mean $p\geq 1$ or $p=\infty$.\
For a matrix $A=(a_{ij}) \in \mathbb C^{n\times n}$, a positive integer $p$, and a vector $p$-norm $|\cdot|_p$ on $\mathbb C^n$, the *matrix $p$-norm* of $A$ is defined by $$|A|_p:=\begin{cases}
\Big(\displaystyle\sum_{i,j=1}^n |a_{ij}|^p\Big)^{\frac{1}{p}} & (1\leq p < \infty)\\
\displaystyle\max_{i,j=1,\cdots,n} |a_{ij}| & (p=\infty).
\end{cases}$$ In particular, $|A|_2=|A|_F$, the Frobenius norm.

The *operator $p$-norm* of $A$ is defined by $$\|A\|_p:=\max\{ |Ax|_p: |x|_p =1\}.$$ Note that $$\|A\|_1:=\max_{j=1,\cdots,n} \sum_{i=1}^n a_{ij},$$ $$\|A\|_\infty:=\max_{i=1,\cdots,n} \sum_{j=1}^n a_{ij}.$$ There are many relations between operator and matrix $p$-norms. Interested readers may refer to the paper of A. Tonge [@T2000] and the references therein for more details.

Some Wielandt’s inequalities for matrix polynomials {#section2}
===================================================

In the first part of this section we give some versions of the Hoffman-Wielandt inequality (\[Hoffman-Wielandt\]) for monic matrix polynomials.

For a monic matrix polynomial $P_{\bold{A}}(z)= I\cdot  z^m + A_{m-1}z^{m-1}+ \cdots + A_1 z + A_0 $ with $A_i\in \mathbb C^{n\times n}$, the $(mn\times mn)$-matrix $$C_{\bold{A}}:=\left[\begin{array}{ccccc}
0 & I & 0 & \cdots & 0\\
0 & 0 & I & \cdots & 0\\
\vdots & \vdots & \vdots &   & \vdots \\
0 & 0 & 0 & \cdots & I\\
-A_0 & -A_1 & -A_2 & \cdots & -A_{m-1}
\end{array}\right]$$ is called the *companion matrix* of the matrix polynomial $P_{\bold{A}}(z)$ or of the tuple $(A_0,\cdots,A_{m-1},I)$.

Note that the spectrum $\sigma(\bold{A})$ of $P_{\bold{A}}(z)$ coincides to the spectrum $\sigma(C_\bold{A})$ of $ C_{\bold{A}}$ (cf. [@GLR1982]).

For two $(m+1)$-tuples $\bold{A}=(A_0,\cdots,A_{m-1},I)$ and $\bold{\bar{A}}=(\bar{A}_0,\cdots,\bar{A}_{m-1},I)$, the relation between the operator norms of their difference and those of their companion matrices is given in the following key lemma. \[norm-companion\] Let $\bold{A}=(A_0,\cdots,A_{m-1},I)$ and $\bold{\bar{A}}=(\bar{A}_0,\cdots,\bar{A}_{m-1},I)$ be $(m+1)$-tuples. Then for any integer $p>0$, we have

-   $ |C_\bold{A} - C_{\bold{\bar{A}}}|_p = |\bold{A}-\bold{\bar{A}}|_p=
      \begin{cases}
      \big(\sum_{i=0}^{m-1} |A_i-\bar{A}_i|_p^p\big)^{\frac{1}{p}} & (1\leq p < \infty)\\
      \displaystyle\max_{i=0,\cdots,m} |A_i|_\infty  & (p=\infty).
      \end{cases}$

-   $ \|C_\bold{A} - C_{\bold{\bar{A}}}\|_p = \|\bold{A}-\bold{\bar{A}}\|_p\leq \displaystyle\sum_{i=0}^{m-1} \|A_i-\bar{A}_i\|_p$.

-   $ \|C_\bold{A} - C_{\bold{\bar{A}}}\|_1 =   \displaystyle\max_{i=0,\cdots,m-1} \|A_i-\bar{A}_i\|_1.$

We have the following expression of the difference of companion matrices $$C_\bold{A} - C_{\bold{\bar{A}}} = \left[\begin{array}{ccccc}
0 & 0 & 0 & \cdots & 0\\
0 & 0 & 0 & \cdots & 0\\
\vdots & \vdots & \vdots &   & \vdots \\
0 & 0 & 0 & \cdots & 0\\
\bar{A}_0-A_0 & \bar{A}_1-A_1 & \bar{A}_2-A_2 & \cdots & \bar{A}_{m-1}-A_{m-1}
\end{array}\right].$$ This implies that the matrix (resp. operator) norm of $C_\bold{A} - C_{\bold{\bar{A}}}$ is the same of that of the $m$-tuple $(\bar{A}_0-A_0, \ldots, \bar{A}_{m-1}-A_{m-1})$, i.e. we have the first equalities in (1) and (2).\
The second equality in (2) follows from the subadditivity of the operator $p$-norm. On the other hand, for an $(m+1)$-tuple $\bold{A}=(A_0,\cdots,A_m)$ of matrices in $\mathbb C^{n\times n}$, by a direct computation, we have $$\label{matrixnorm-1}
  |\bold{A}|_p:= \begin{cases}
  \big(\sum_{i=0}^m |A_i|_p^p\big)^{\frac{1}{p}} & (1\leq p < \infty)\\
  \displaystyle\max_{i=0,\cdots,m} |A_i|_\infty  & (p=\infty),
  \end{cases}$$ thus we get the second equality of (1). Moreover, we have $$\label{oper1norm}
 \|\bold{A}\|_1 = \max_{i=0,\cdots,m} \|A_i\|_1.$$ Thus, we get (3). As a consequence of Lemma \[norm-companion\], we obtain the following Hoffman-Wielandt inequality for matrix polynomials.

\[thr-Hoffman-Wielandt-matrix\] Let $P_{\bold{A}}(z)= I\cdot  z^m + A_{m-1}z^{m-1}+ \cdots + A_1 z + A_0$ and $P_{\bold{\bar{A}}}(z)= I\cdot  z^m + \bar{A}_{m-1}z^{m-1}+ \cdots + \bar{A}_1 z + \bar{A}_0$ be monic matrix polynomials whose corresponding companion matrices $C_\bold{A}$ and $C_\bold{\bar{A}}$ are normal. Then we have $$\dist_F(\sigma(\bold{A}), \sigma(\bold{\bar{A}})) \leq |\bold{A}-\bold{\bar{A}}|_F.$$ Applying the Hoffman-Wielandt inequality (\[Hoffman-Wielandt\]) for two normal matrices $C_\bold{A}$ and $C_{\bold{\bar{A}}}$ we get $$\dist_F(\sigma(C_\bold{A}), \sigma(C_{\bold{\bar{A}}})) \leq |C_\bold{A}-C_{\bold{\bar{A}}}|_F.$$ Then the theorem follows from Lemma \[norm-companion\] (applying for $p=2$) with the observation that $\sigma(\bold{A})=\sigma(C_\bold{A})$ and $\sigma(\bold{\bar{A}})=\sigma(C_\bold{\bar{A}})$. We should observe that $$\label{companion-normal}
C_\bold{A} \mbox{ is normal if and only if } A_0 \mbox{ is unitary and } A_1=\ldots=A_{m-1}=0.$$

Therefore, Theorem \[thr-Hoffman-Wielandt-matrix\] yields the following consequence. \[coro-Hoffman-Wielandt\] Let $P_{\bold{A}}(z)= I\cdot  z^m + A_0$ and $P_{\bold{\bar{A}}}(z)= I\cdot  z^m +  \bar{A}_0$ be momic matrix polynomials with $A_0$ and $\bar{A}_0$ unitary. Then we have $$\dist_F(\sigma(\bold{A}), \sigma(\bold{\bar{A}})) \leq |A_0-\bar{A}_0|_F.$$

One more interesting inequality was established by Wielandt for scalar matrices which is stated as follows.

Let $A\in \mathbb C^{n \times n}$ be a Hermitian matrix such that for some numbers $a,b>0$ the inequalities $bI \leq A \leq aI$ hold. Then for any orthogonal unit vectors $x,y \in \mathbb C^n$, the inequality $$\label{Wielandt}
 |x^*Ay|^2 \leq \big(\dfrac{a-b}{a+b}\big)^2(x^*Ax)\cdot (y^*Ay)$$ holds.

In the following we establish a version of this inequality for matrix polynomials.

Let $P_A(\lambda)=\displaystyle\sum_{i=0}^d A_i \lambda^i$ be a matrix polynomial whose coefficient matrices satisfy $$bI\leq A_i\leq aI$$ for some numbers $a,b >0$ and for all $i=0,\ldots,d$. Then for any orthogonal unit vectors $x,y \in \mathbb C^n$, $$|x^*P_A(\lambda)y|^2 \leq \big(\dfrac{a-b}{a+b}\big)^2 (x^*P_A(|\lambda|)x) \cdot  (y^*P_A(|\lambda|)y).$$

It follows from (\[Wielandt\]) that for each $i=0,\ldots,d$, $$|x^*A_iy|\leq \big(\dfrac{a-b}{a+b}\big)(x^*A_ix)^{\frac{1}{2}}\cdot (y^*A_iy)^{\frac{1}{2}}.$$ Then $$\begin{aligned}
|x^*P_A(\lambda)y|^2 &= \big(\big|\sum_{i=0}^d (x^*A_iy)\lambda^i \big|\big)^2 \leq  \big( \sum_{i=0}^d |x^*A_iy|\cdot |\lambda|^i \big)^2\\
& \leq \big(\dfrac{a-b}{a+b}\big)^2 \big( \sum_{i=0}^d (x^*A_ix)^{\frac{1}{2}} |\lambda|^{\frac{i}{2}}\cdot (y^*A_iy)^{\frac{1}{2}}\cdot |\lambda|^{\frac{i}{2}} \big)^2\\
& \leq \big(\dfrac{a-b}{a+b}\big)^2 \big(\sum_{i=0}^d (x^*A_ix)  |\lambda|^{i}\big)  \big(\sum_{i=0}^d (y^*A_iy)  |\lambda|^{i}\big)\\
&= \big(\dfrac{a-b}{a+b}\big)^2 \big(x^*(\sum_{i=0}^d A_i  |\lambda|^{i})x\big)\big(y^*(\sum_{i=0}^d A_i  |\lambda|^{i})y\big)\\
&= \big(\dfrac{a-b}{a+b}\big)^2\big(x^*P_A(|\lambda|)x\big)\cdot \big(y^*P_A(|\lambda|)y\big),
 \end{aligned}$$ where the last inequality follows from the classical Cauchy-Schwarz inequality. The proof is complete.

 Some weaker versions of the Wielandt-Mirsky conjecture for matrix polynomials  {#section3}
===============================================================================

In this section we give some estimations for the optimal matching distance between the spectra of matrix polynomials.

\[thr-distance-1\] There exists a constant $c>0$ such that for every positive integer $p$ and monic matrix polynomials $P_{\bold{A}}(z)= I\cdot  z^m + A_{m-1}z^{m-1}+ \cdots + A_1 z + A_0$ and $P_{\bold{\bar{A}}}(z)= I\cdot  z^m + \bar{A}_{m-1}z^{m-1}+ \cdots + \bar{A}_1 z + \bar{A}_0$ whose corresponding companion matrices $C_\bold{A}$ and $C_\bold{\bar{A}}$ are normal we have $$\dist(\sigma(\bold{A}), \sigma(\bold{\bar{A}})) \leq c\|\bold{A}-\bold{\bar{A}}\|_p \leq c\displaystyle\sum_{i=0}^{m-1} \|A_i-\bar{A}_i\|_p.$$ It follows from the result of R. Bhatia, C. Davis and A. Mcintosh (see the inequality (\[universal-constant\]) that there exists a constant $c>0$ such that for every monic matrix polynomials $P_{\bold{A}}(z)$ and $P_{\bold{\bar{A}}}(z)$ whose corresponding companion matrices $C_\bold{A}$ and $C_\bold{\bar{A}}$ are normal, we have $$\dist(\sigma(C_\bold{A}), \sigma(C_{\bold{\bar{A}}})) \leq c\|C_\bold{A}-C_{\bold{\bar{A}}}\|_p.$$ Then the theorem follows from Lemma \[norm-companion\] (2) with the observation that $\sigma(\bold{A})=\sigma(C_\bold{A})$ and $\sigma(\bold{\bar{A}})=\sigma(C_\bold{\bar{A}})$. Using again the observation (\[companion-normal\]) we obtain the following consequence. \[coro-distance-1-1\] There exists a constant $c>0$ such that for every positive integer $p$ and monic matrix polynomials $P_{\bold{A}}(z)= I\cdot  z^m + A_0$ and $P_{\bold{\bar{A}}}(z)= I\cdot  z^m +  \bar{A}_0$ with $A_0$ and $\bar{A}_0$ unitary, we have $$\dist(\sigma(\bold{A}), \sigma(\bold{\bar{A}})) \leq c\|A_0-\bar{A}_0\|_p.$$ Similarly, applying the inequality (\[Anormal-Barbitrary\]) and Lemma \[norm-companion\] (2) with the observation (\[companion-normal\]) we obtain the following results. \[coro-distance-1-2\] Let $P_{\bold{A}}(z)= I\cdot  z^m + A_0$ and $P_{\bold{\bar{A}}}(z)= I\cdot  z^m +  \bar{A}_0$ be matrix polynomials with $A_0$ and $\bar{A}_0$ unitary. Then for every positive integer $p$ we have $$\dist(\sigma(\bold{A}), \sigma(\bold{\bar{A}})) \leq (2mn-1)\|A_0-\bar{A}_0\|_p.$$

A similar version of (\[Eq-Kahan\]) for monic matrix polynomials is given as follows, whose proof is similar to that of Proposition \[thr-Hoffman-Wielandt-matrix\].

\[thr-distance-2\] Let $P_{\bold{A}}(z)= I\cdot  z^m + A_{m-1}z^{m-1}+ \cdots + A_1 z + A_0$ and $P_{\bold{\bar{A}}}(z)= I\cdot  z^m + \bar{A}_{m-1}z^{m-1}+ \cdots + \bar{A}_1 z + \bar{A}_0$ be monic matrix polynomials. Assume that $C_\bold{A}$ is Hermitian. Then for every positive integer $p$ we have $$\dist(\sigma(\bold{A}), \sigma(\bold{\bar{A}})) \leq (\gamma_{m,n}+2)\|\bold{A}-\bold{\bar{A}}\|_p \leq (\gamma_{m,n}+2)\displaystyle\sum_{i=0}^{m-1} \|A_i-\bar{A}_i\|_p,$$ where $\gamma_{m,n}$ is a constant depending on $m$ and $n$.

The constant $\gamma_{m,n}$ have the following properties (cf. [@Bh2007 p. 3]):

-   $\dfrac{2}{\pi} \ln (mn) - 0(1) \leq \gamma_{m,n} \leq \log_2 (mn) + 0.038.$

-   A. Pokrzywa (1981, [@P1981]) proved that $$\gamma_{m,n}=\dfrac{2}{mn} \sum_{j=1}^{[mn/2]} \cot \dfrac{2j-1}{2mn}\pi.$$

One of the condition for the companion matrix $C_\bold{A}$ to be Hermitian is given as follows. \[coro-distance-2-1\] Let $P_{\bold{A}}(z)= I\cdot  z^m + A_0$ and $P_{\bold{\bar{A}}}(z)= I\cdot  z^m +  \bar{A}_0$ be matrix polynomials with $A_0$ unitary. Assume that $P_{\bold{A}}(z)$ has only real eigenvalues. Then for every positive integer $p$ we have $$\dist(\sigma(\bold{A}), \sigma(\bold{\bar{A}})) \leq (\gamma_{m,n}+2)\|A_0-\bar{A}_0\|_p.$$ It is well-known that a normal matrix $A\in \mathbb C^{n\times n}$ is Hermitian if and only if it has only real eigenvalues. Therefore, the normal matrix $C_\bold{A}$ is Hermitian if and only if it, whence the matrix polynomial $P_\bold{A}(z)$, has only real eigenvalues. Note also that in this case, $C_\bold{A}$ is normal if and only if $A_0$ is unitary. Then the result follows from Proposition \[thr-distance-2\]. There are some characterization for matrix polynomials to have only real eigenvalues. These kinds of matrix polynomials are sometime called *weakly hyperbolic*. The readers can refer to the work of M. Al-Ammari and F. Tisseur (2012, [@AT2012 Theorem 3.4]) and the references therein for more details characterization.

In the following we will establish an estimation for the optimal matching distance between spectra of two arbitrary monic matrix polynomials. For the proof, we need the following estimation given by Bhatia and Friedland (1981), Elsner (1982, 1985).

\[bhatia-arbitrary\] Let $A$ and $B$ be any $k \times k$-matrices. Then the optimal matching distance between their eigenvalues are bounded as $$\dist(\sigma(A), \sigma(B)) \leq  c(k) \cdot  k^{\frac{1}{k}} \cdot  (2M)^{1-\frac{1}{k}}\cdot \|A-B\|^{\frac{1}{k}},$$ where $M=\max\{\|A\|, \|B\|\}$, $\|\cdot \|$ any operator norm, and $c(k)=k $ or $k-1$ according to whether $k$ is odd or even.

Let $N$ be any positive number and $p$ any positive integer. Let $P_{\bold{A}}(z)= I\cdot  z^m + A_{m-1}z^{m-1}+ \cdots + A_1 z + A_0$ and $P_{\bold{\bar{A}}}(z)= I\cdot  z^m + \bar{A}_{m-1}z^{m-1}+ \cdots + \bar{A}_1 z + \bar{A}_0$ be monic matrix polynomials such that $|\bold{A}|_p \leq N$ and $|\bold{\bar{A}}|_p\leq N$. Then there exists a constant $c$ such that $$\dist(\sigma(\bold{A}), \sigma(\bold{\bar{A}})) \leq c \|\bold{A}-\bold{\bar{A}}\|_p^{\frac{1}{mn}}.$$

Applying Lemma \[bhatia-arbitrary\] for the companion matrices $C_\bold{A}$ and $C_\bold{\bar{A}}$ with the operator norm $\|\cdot \|_p$ we obtain $$\dist(\sigma(C_\bold{A}), \sigma(C_\bold{\bar{A}})) \leq  c(mn) \cdot  (mn)^{\frac{1}{mn}} \cdot  (2M)^{1-\frac{1}{mn}}\cdot \|C_\bold{A}-C_\bold{\bar{A}}\|_p^{\frac{1}{mn}},$$ where $M=\max\{\|C_\bold{A}\|_p, \|C_\bold{\bar{A}}\|_p\}$. Then it follows from Lemma \[norm-companion\] (2) and the equalities $\sigma(\bold{A})=\sigma(C_\bold{A})$ and $\sigma(\bold{\bar{A}})=\sigma(C_\bold{\bar{A}})$ that $$\dist(\sigma(\bold{A}), \sigma(\bold{\bar{A}})) \leq  c(mn) \cdot  (mn)^{\frac{1}{mn}} \cdot  (2M)^{1-\frac{1}{mn}}\cdot \|\bold{A}-\bold{\bar{A}}\|_p^{\frac{1}{mn}}.$$ Now we need to estimate $\|C_\bold{A}\|_p$ and $ \|C_\bold{\bar{A}}\|_p$. By a comparison of the operator $p$-norm $\|C_\bold{A}\|_p$ and the matrix $p$-norm $|C_\bold{A}|_p$ given by M. Gohberg [@G1987] (see also in [@T2000], we have $$\label{compare-pnorm}
\|C_\bold{A}\|_p \leq (mn)^{\max\{1/p'-1/p,0\}} |C_\bold{A}|_p.$$ It is easy to see that for $1\leq p < \infty$, $$\label{equ-compare-norm1}
|C_\bold{A}|_p^p = \sum_{i=0}^{m-1}|A_i|_p^p + (m-1)n = |\bold{A}|_p^p + (m-1)n \leq N^p + (m-1)n,$$ and for $p=\infty$, $$\label{equ-compare-norm2}
|C_\bold{A}|_\infty  =  \max\{|\bold{A}|_\infty, 1\}\leq \max\{N,1\}.$$ It follows from the inequalities (\[compare-pnorm\]), (\[equ-compare-norm1\]) and (\[equ-compare-norm2\]) that $$\|C_\bold{A}\|_p \leq M':=\begin{cases}
(mn)^{\max\{1/p'-1/p,0\}} \big(N^p + (m-1)n\big)^{\frac{1}{p}} & (1\leq p < \infty)\\
mn\max\{N,1\} & (p=\infty).
\end{cases}$$ Similarly, $$\|C_\bold{\bar{A}}\|_p \leq M'.$$ Then the number $$c:= c(mn) \cdot  (mn)^{\frac{1}{mn}} \cdot  (2M')^{1-\frac{1}{mn}}$$ satisfies the requirement.

For matrix polynomials which are not necessarily monic, we have the following estimation, only for operator $1$-norm.

\[thr1\] Let $\bold{\bar{A}}=(\bar{A}_0,\cdots, \bar{A}_m)$ be a fixed $(m+1)$-tuple such that $\bar{A}_m$ non-singular. Then there exists a constant $c>0$ such that for every pair of matrix polynomials $P_{\bold{A}}(z)= A_m\cdot  z^m + A_{m-1}z^{m-1}+ \cdots + A_1 z + A_0$ and $P_{\bold{{A}'}}(z)= A'_m\cdot  z^m +  {A}'_{m-1}z^{m-1}+ \cdots + {A}'_1 z +  {A}'_0$ with $\|\bold{A}-\bold{\bar{A}}\|_1 < \dfrac{1}{\|\bar{A}^{-1}_m\|_1}$ and $\|\bold{A'}-\bold{\bar{A}}\|_1 < \dfrac{1}{\|\bar{A}^{-1}_m\|_1}$ we have $$\dist(\sigma(\bold{A}), \sigma(\bold{{A}'})) < c  \|\bold{A}-\bold{A'}\|_1^{\frac{1}{mn}}.$$

It follows from the sub-multiplicative property of operator $1$-norm and the formula (\[oper1norm\]) that $$\|\bar{A}^{-1}_m(A_m-\bar{A}_m)\|_1 \leq \|\bar{A}^{-1}_m \|_1\cdot \|A_m-\bar{A}_m\|_1\leq  \|\bar{A}^{-1}_m \|_1 \cdot \|\bold{A}-\bold{\bar{A}}\|_1 < 1.$$ Then $A_m$ is also non-singular (cf. [@GL2013 Theorem 2.3.4]), thus each element of $\sigma(\bold{ A})$ is finite. Similarly, each element of $\sigma(\bold{ A'})$ is also finite.

Since $\sigma(\bold{A'})$ is the set of roots of the polynomial $\det(P_\bold{A'}(z))\in \mathbb C[z]$ whose degree is $mn$, it is easy to see that $$\dist(x, \sigma(\bold{A'}))^{mn}\leq  |\det(P_{\bold{A'}}(x))|, \mbox{ for all } x\in \mathbb C.$$ In particular, for any $\lambda \in \sigma(\bold{{A}})$, we have $$\label{equ6}
 \dist(\lambda, \sigma(\bold{A'}))^{mn} \leq |\det(P_{\bold{A'}}(\lambda))|.$$

Since $\det(P_{ \bold{A}}(\lambda))=0,$ we have $$\begin{aligned}
 \label{equ7}
|\det(P_{\bold{A'}}(\lambda))| & =  |\det(P_{\bold{A'}}(\lambda)) - \det(P_{\bold{A}}(\lambda))|.\end{aligned}$$

The following inequality is useful for the later estimation (cf. [@Bh2007 2007, p.107]): For any matrices $A,B \in \mathbb C^{n\times n}$ and for any integer $p>0$, we have $$\label{det-ineq}
|\det(A) - \det(B)| \leq n \max\{\|A\|_p, \|B\|_p\}^{n-1}\cdot \|A-B\|_p.$$ Applying the inequality (\[det-ineq\]), we get $$\label{equ8}
|\det(P_{\bold{A'}}(\lambda)) - \det(P_{ \bold{A}}(\lambda))| \leq n \max\{  \|P_{ \bold{A'}}(\lambda)\|_1, \|P_{\bold{A}}(\lambda)\|_1\}^{n-1}\cdot \|P_{\bold{A}}(\lambda) - P_{ \bold{A'}}(\lambda)\|_1.$$ Using again the sub-multiplicativity of operator $1$-norm and the formula (\[oper1norm\]), we have $$\|P_{\bold{A}}(\lambda) - P_{ \bold{A'}}(\lambda)\|_1 = \|\sum_{i=0}^m (A_i -A'_i)\lambda^i \|_1 \leq \sum_{i=0}^m |\lambda|^i \cdot \|\bold{A}-\bold{A'}\|_1.$$ It follows from a matrix version of Cauchy theorem (cf. [@DLN2017 Theorem 3.4]) that for $\lambda \in \sigma(\bold{{A}})$, we have $$|\lambda| < 1 + \|{A}_m^{-1}\|_1 \cdot \max\{\|{A}_i\|_1, i=0,\cdots,m-1\} \leq 1+\|{A}_m^{-1}\|_1\cdot \|\bold{{A}}\|_1.$$ On the other hand, by the sub-additivity of operator norm, we have $$\|\bold{A}\|_1\leq \|\bold{A}-\bold{\bar{A}}\|_1 + \|\bold{\bar{A}}\|_1 <  \dfrac{1}{\|\bar{A}^{-1}_m\|_1} + \|\bold{\bar{A}}\|_1.$$ Hence for each $\lambda \in \sigma(\bold{A})$ we have $$|\lambda| < 2 +  \|\bar{A}_m^{-1}\|_1\cdot \|\bold{\bar{A}}\|_1.$$ Then $$\sum_{i=0}^m |\lambda|^i < L:=\dfrac{(2 +  \|\bar{A}_m^{-1}\|_1\cdot \|\bold{\bar{A}}\|_1)^{m+1}-1}{1+ \|\bar{A}_m^{-1}\|_1\cdot \|\bold{\bar{A}}\|_1}.$$ This yields $$\label{equ9}
\|P_{\bold{A}}(\lambda) - P_{ \bold{A'}}(\lambda)\|_1 < L\cdot \|\bold{A}-\bold{A'}\|_1.$$ By a similar estimation, we get $$\begin{aligned}
\|P_{ \bold{A}}(\lambda)\|_1 & < L \cdot \|\bold{A}\|_1\leq L\cdot \big(\dfrac{1}{\|\bar{A}^{-1}_m\|_1} + \|\bold{\bar{A}}\|_1\big),\label{equ10}\\
\|P_{\bold{A'}}(\lambda)\|_1 & <  L\cdot \|\bold{A'}\|_1\leq L\cdot \big(\dfrac{1}{\|\bar{A}^{-1}_m\|_1} + \|\bold{\bar{A}}\|_1\big).\label{equ11}\end{aligned}$$ It follows from the inequalities (\[equ6\]), (\[equ7\]), (\[equ8\]), (\[equ9\]), (\[equ10\]) and (\[equ11\]) that $$\dist(\lambda, \sigma(\bold{A'}))  < c \|\bold{A}-\bold{A'}\|_1^{\frac{1}{mn}},$$ where $$c:=\Big(n\cdot L^{n-1}\cdot \big(\dfrac{1}{\|\bar{A}^{-1}_m\|_1} + \|\bold{\bar{A}}\|_1\big)^{n-1}\Big)^{\frac{1}{mn}}.$$ Similarly, for every $\lambda' \in \sigma(\bold{A'}),$ we have also $$\dist(\lambda, \sigma(\bold{A}))  < c \|\bold{A}-\bold{A'}\|_1^{\frac{1}{mn}}.$$ It follows that $$\dist(\sigma(\bold{A}),\sigma(\bold{A'}))  < c \|\bold{A}-\bold{A'}\|_1^{\frac{1}{mn}}.$$

Acknowledgements {#acknowledgements .unnumbered}
================

The author would like to thank Dr. Minh Toan HO for his suggestion to establish a Wielandt’s inequality for matrix polynomials in Section 2. He would also like to express his sincere gratitude to the anonymous referees for their useful comments and suggestions to improve the results in the original version of this paper. The final version of this paper was finished during the visit of the author at the Vietnam Institute for Advanced Study in Mathematics (VIASM). He thanks VIASM for financial support and hospitality.

[99]{} Al-Ammari M, Tisseur F. [ Hermitian matrix polymomials with real eigenvalues of definite type. Part I. Classification]{}. Linear Algebra Appl. 2012; **436**(10): 3954–3973. Bhatia R. [ Perturbation bounds for matrix eigenvalues]{}. Longman, Harlow; 1987; 2nd ed., SIAM, Philadelphia; 2007. Bhatia R, Davis C, Mcintosh A. [ Perturbation of spectral subspaces and solution of linear operator equations]{}. Linear algebra and its applications 1983; **52**: 45-67. Du T.H.B, Le C.-T., Nguyen T.D. [ On the location of eigenvalues of matrix polynomials]{}. Preprint, 2017.

Gohberg I, Lancaster P, Rodman L. [Matrix Polynomials]{}. Academic Press, New York; 1982. Goldberg M. [Equivalence constants for lp norms of matrices]{}. Linear and Multilinear Algebra 1987; **21**: 173–179. Golub G.H, Van Loan C.F. Matrix Computations, 4th Edition. Johns Hopkins University Press, Baltimore; 2013. Hiai F, Petz D. Introduction to matrix analysis and applications. Springer; 2014. Hoffman A.J, Wielandt H.W. The variation of the spectrum of a normal matrix. Duke Math. J. 1953; **20**: 37-39. Holbrook A.J. [Spectral variation of normal matrices]{}. Linear Algebra Appl. 1992; **174**: 131-144. Kahan W. [ Inclusion theorems for clusters of eigenvalues of Hermitian matrices]{}. Technical Report, Computer Science Department, University of Toronto; 1967. . [ Spectra of operators with fixed imaginary parts]{}. Proc. Amer. Math. Soc. 1981; **81**, No. 3: 359-364. . [ Equivalence constants for matrix norms: a problem of Goldberg]{}. Linear Alg. Appl. 2000; **306**: 1-13.