# When are almost block companion matrices which yield a given characteristic polynomial connected?

This is motivated by this question Are matrices which yield a given characteristic polynomial and have specified structure connected?

Let $$\mathcal E \in M_n(\mathbb R)$$ be a subset with following form: we first construct a block diagonal matrix in $$M_n(\mathbb R)$$ such that \begin{align*} C = \begin{pmatrix} C_{k_1} & 0 & 0 & \cdots & 0 \\ 0 & C_{k_2} & 0 & \cdots & 0 \\ 0 & 0 & \ddots & \vdots & 0 \\ 0 & 0 & 0 & \cdots & C_{k_r} \end{pmatrix}, \end{align*} with $$k_1 + k_2 + \dots + k_r = n$$ such that each block $$C_{k_j}$$ is in the companion form \begin{align*} \begin{pmatrix} 0 & 0 & \cdots & 0 & -c_0 \\ 1 & 0 & \cdots & 0 & -c_1 \\ 0 & 1 & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1& -c_{k_j-1} \end{pmatrix}. \end{align*} Now for each block we extend the last column to fill up the whole matrix. For example, suppose we have two blocks $$C_1$$ and $$C_2$$ with $$C_1 \in \mathbb R^{2 \times 2}$$ and $$C_2 \in \mathbb R^{3 \times 3}$$, elements in $$\mathcal E$$ would look like \begin{align*} \begin{pmatrix} 0 & -a_1 & 0 & 0 & -b_1 \\ 1 & -a_2 & 0 & 0 & -b_2 \\ 0 & -a_3 & 0 & 0 & -b_3 \\ 0 & -a_4 & 1 & 0 & -b_4 \\ 0 & -a_5 & 0 &1 & -b_5 \end{pmatrix}. \end{align*}

It is also clear for any monic $$n^{th}$$ degree real polynomial, we can at least find one realization in $$\mathcal E$$ since we can choose a matrix in block diagonal form. Let $$f: \mathcal E \to \mathbb R^n$$ be the map sending the coefficients of characteristic polynomial to $$\mathbb R^n$$.

Let $$q(t) = t^n + a_{n-1} t^{n-1} + \dots + a_0$$ be a fixed polynomial. I am wondering whether there are sufficient conditions on $$a = (a_{n-1}, \dots, a_0)$$ such that $$f^{-1}(a)$$ is a connected set?

This question Are matrices which yield a given characteristic polynomial and have specified structure connected? asked a specific case, i.e, $$n=4, k_1 = k_2 = 2$$. There is a very nice answer proving: as long as the polynomial has a real root, then it is connected. The technique by the answer does not seem to generalize. But I am very interested to know whether the same condition holds here: if $$q(t)$$ has a real root, then $$f^{-1}(a)$$ is connected where $$a = (a_{n-1}, \dots, a_0)$$ is the coefficient vector of $$q(t)$$?

EDIT: This question might be too tricky to answer (This is the third time I put a bounty). But I would be happy to reward the bounty if someone gives an answer on a very special polynomial with coefficients vector of $$a$$ such that $$f^{-1}(a)$$ is connected. For example, is $$f^{-1}((0, \dots, 0))$$ connected, i.e., the polynomial with all roots to be $$0$$ or some other special polynomials?

$\newcommand{\NN}{{\mathbb{N}}}\newcommand{\CC}{{\mathbb{C}}}\newcommand{\RR}{{\mathbb{R}}}\newcommand{\ra}{\rightarrow}\newcommand{\ds}{\displaystyle}$ So far, I can show that in the case $r=2$ that the set $f^{-1}(p)$ is connected if and only if the characteristic polynomial $p$ has at least one real zero.

Consider the subset $S$ of $M_{n+m}(\mathbb R)$, $n,m>0$, the elements of which have the form \begin{align*} A = \begin{pmatrix} C_1&D_2\\ D_1&C_2 \end{pmatrix} \end{align*} where $C_j$ are companion matrices and $D_j$ are all zero except of their last columns. Precisely \begin{align*}\begin{matrix} C_1=\begin{pmatrix} 0 & 0 & \cdots & 0 & -a_1 \\ 1 & 0 & \cdots & 0 & -a_2 \\ 0 & 1 & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1& -a_{n} \end{pmatrix},& D_2=\begin{pmatrix} 0 & \cdots & 0 & -b_{1}\\ 0 & \cdots & 0 & -b_{2} \\ \vdots& & \vdots & \vdots \\ 0 & \cdots & 0& -b_{n} \end{pmatrix}\\ D_1=\begin{pmatrix} 0 & \cdots & 0 & -a_{n+1}\\ 0 & \cdots & 0 & -a_{n+2} \\ \vdots& & \vdots & \vdots \\ 0 & \cdots & 0& -a_{n+m} \end{pmatrix},& C_2=\begin{pmatrix} 0 & 0 & \cdots & 0 & -b_{n+1} \\ 1 & 0 & \cdots & 0 & -b_{n+2} \\ 0 & 1 & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1& -b_{n+m} \end{pmatrix}.\end{matrix} \end{align*} where $a_j,b_j$, $j=1,...,n+m$ can assume any real number. Let $f$ be the map sending elements of $S$ to their characteristic polynomial $p$.

We want to show that $f^{-1}(p)$ is connected if and only if $p$ has at least one real zero. More precisely if $p$ has at least one real zero, we show that every element of $f^{-1}(p)$ is connected to a block diagonal matrix by some path within $f^{-1}(p)$ and that the block diagonal matrices in $f^{-1}(p)$ are connected by paths. In $p$ has no real roots, then we give an example of two matrices in $f^{-1}(p)$ which cannot be connected by a path within this set. This is the strategy of this answer.

As in 1 the characteristic polynomial $p(t)$ of $A$ in $f^{-1}(p)$ written as above is calculated as \begin{align}\label{eq1}\tag{1} p(t)=c_1(t)c_2(t)-d_1(t)d_2(t), \end{align} where $c_1$, $c_2$ are the characteristic polynomials of $C_1,C_2$, respectively, and $d_1(t)=a_{n+m}t^{m-1}+...+a_{n+1}$, $d_2(t)=b_{n}t^{n-1}+...+b_{1}$. Note that $c_1\in t^n+P_n,\,c_2\in t^m+P_m$, $d_1\in P_m$ and $d_2\in P_n$, where $P_k$ denotes the set of polynomials of degree less than $k$.

As in 1, we will mainly use the vector $a$ as parameters and determine the vector $b$ by solving the system of linear equations obtained from the condition that the characterictic polynomial of $A$ is $p(t)$. This is equivalent to saying that $c_1,d_1$ are given and we determine $c_2,d_2$ from (\ref{eq1}). The coefficient matrix of this linear system is the transpose of Sylvester's matrix for $c_1,d_1$ the determinant of which is the resultant of $c_1$ and $d_1$, but we do not really need this. All we need is the following

Claim: The linear mapping $L_{c_1,d_1}:P_m\times P_n\mapsto P_{m+n}$, $L_{c_1,d_1}(h_1,h_2)=c_1h_1+d_1h_2$ is bijective if and only if $c_1$ and $d_1$ are coprime, that is they don't have a (nontrivial) common factor. We will only write $L$ in the sequel for simplicity.

Proof: If they have a common factor of degree larger than 0 then the mapping does not have $1$ in its image. If they do not have a common factor, we only have to show that $L$ is one-to-one. So suppose that $(h_1,h_2)\in P_m\times P_n$ with $c_1h_1+d_1h_2=0$. This equation implies that the degree of $h_1$ is actually less than that of $d_1$ and that every prime factor of $d_1$ is a factor of $h_1$ with the same multiplicity ($\RR[t]$ is a Euclidian domain), because $d_1$ and $c_1$ have no common prime factor. Hence $d_1$ divides $h_1$ and $h_1=0$. The claim is proved.

It is convenient to write (\ref{eq1}) in terms of $L$: $L(c_2-t^m,d_2)=p-t^m\,c_1$. If the parameters $a$ vary continuously along some path in $\RR^{n+m}$ on which $c_1,d_1$ are coprime, then so do $L$, $L^{-1}$, $c_2,d_2$ and hence the vector $b$ such that $A$ has characteristic polynomial $p$.

We need the following notion for coprime couples $(c,d)$ of polynomials for which $c$ is monic. We say that $(c,d)$ is reduced if $c$ and $d$ have at most simple real zeros and either $d$ has no real zero or the zeros of $d$ separate those of $c$. In this case, we also say that $(c,d)$ is of type $k$ if $d$ has exactly $k\geq0$ real zeros. Every coprime couple $(c,d)$ with monic $c$ can be continuously modified into a reduced couple in the following way. Whenever there is a pair of simple adjacent real zeros of $c$ or $d$, we can make them coalesce into a double zero and then make them into a pair of conjugate complex non-real zeros. Multiple zeros are treated similarly. If $d$ has a real zero larger (or smaller) than all zeros of $c$ then we can move it to infinity - this reduces the degree of $d$. The type $k$ of $(c,d)$ obtained in this way is independent of the way we reach a reduced couple continuously. This seems reasonable because real zeros of $c$ or $d$ between zeros of $d$ or $c$, respectively, can only appear in pairs when modifying continuously. The independence of $k$ could be proved formally by expressing it using the winding number around $0$ of the path in $\RR^2$ defined by $t\mapsto (c(t),d(t))$, $-T\leq t\leq T$, $T$ large, completed by a large arc in the positive direction unless $d$ is constant.

We now prove that every element $A$ of $f^{-1}(p)$ is connected to some block diagonal matrix within $f^{-1}(p)$ if $p$ has at least one real zero.

Case 0: If $d_1$ is a nonzero constant, then $L$ is invertible, whatever $c_1$ is and hence $c_1$ can be chosen arbitrarily; by (\ref{eq1}), $c_2, d_2$ are uniquely determined. Therefore we can reduce $c_1$ to the first factor in some real factorisation $p(t)= c_1(t)c_2(t)$, $c_1\in t^n+P_n$, $c_2\in t^m+P_m$ of $p$. Such a factorisation exists even if $n$ and $m$ are odd because $p$ has at least one real zero. By its uniqueness, we must then have $c_2$ from the factorisation and $d_2=0$. We reach block diagonal form after reducing $d_1$ to 0. In this case, we can reach any real factorisation of $p(t)$. Trivially the present case can be reached from any real factorisation of $p(t)$ ad therefore they can all be connected by paths within $f^{-1}(p)$. The present case is almost identical to the first case in 1. Observe that this case also applies if $p$ has no real zero and $m,n$ are even.

Case 1: If $c_1$, $d_1$ related to $A$ are coprime and $d_1$ has at least one complex zero then its complex zeros are not zeros of $c_1$. Then we can modify $c_1$, $d_1$ continuously such that they still are coprime by studying the locations of their zeros in the complex plane. We have to keep pairs of conjugate complex zeros if there are nonreal zeros and we have to make sure that a zero of $c_1$ never meets a zero of $d_1$. Recall that $c_2$, $d_2$ are uniquely determined by (\ref{eq1}) and also vary continuously.

First, we can continuously modify the couple $(c_1,d_1)$ into a reduced one. In the case of odd $n$, we can move all real zeros of $c_1$ and $d_1$, such that the zero in the middle of the real zeros of $c_1$ coincides with the real zero of $p$. Let us call it $z$. By (\ref{eq1}), it must also be a zero of $d_2$, because it is not a zero of $d_1$. Therefore, we can divide (\ref{eq1}) by $t-z$ and obtain a similar equation \begin{align}\label{eq2}\tag{2} \tilde p(t)=\tilde c_1(t)c_2(t)- d_1(t)\tilde d_2(t), \end{align} where $\tilde p(t)=p(t)/(t-z)\in t^{n+m-1}+P_{n+m-1}$, $\tilde c_1(t)= c_1(t)/(t-z)\in t^{n-1}+P_{n-1}$ and $\tilde d_2(t)=d_2(t)/(t-z)\in P_{n-1}$. The new problem is analogous to (\ref{eq1}) and can be seen as coming from the question asked for diagonal blocks of size $n-1$ and $m$. If we can modify $\tilde c_1,c_2,d_1,\tilde d_2$ without changing $\tilde p$ such that we arrive at $d_1\tilde d_2=0$ which corresponds to a block diagonal matrix then we can do the same with the original problem.

Again, $c_2$ and $\tilde d_2$ are determined from (\ref{eq2}) if $\tilde c_1$ and $d_1$ are coprime and we can modify the zeros of the latter polynomials as before for $c_1$ and $d_1$. Now, the two middle real zeros of $d_1$ are no longer separated by a zero of $\tilde c_1$ and after modifying them into a pair of conjuagte complex zeros, the two middle zeros of $c_1$ are adjacent etc.: We can continously modify $(\tilde c_1,d_1)$ such that both have no more real zeros.

In a final step, all the complex zeros of $d_1$ are moved to infinity -- of course in such a way that we never meet a zero of $\tilde c_1$; its constant term is fixed. Thus $d_1$ is reduced to a nonzero constant and we have reached case 0. Since $n-1$ is even, there is a real factorisation of $\tilde p$ into polynomials of these degrees and, by case 0, we can reach block diagonal form.

In the case of even $n$, either $d_1$ is a constant and we are in case 0 or the degree of $d_1$ after modification into a reduced couple $(c_1,d_1)$ must be odd. In this case, we remove the middle zero of $d_1$ in the same way as above and arrive at \begin{align}\nonumber \tilde p(t)=c_1(t)\tilde c_2(t)- \tilde d_1(t) d_2(t), \end{align} with a couple $(c_1,\tilde d_1)$ of type 0. The remainder of the proof is analogous.

Case 2: If $c_1$, $d_1$ related to $A$ are not coprime then we work with $c_2, d_2$ instead; if necessary after a preliminary modification. If $c_2,d_2$ are coprime, no modification is necessary. Case 1 applies after permuting $c_1,d_1$ and $c_2,d_2$. Otherwise let $q$ be the gcd of $c_1,d_1$. Then $\bar c_1=c_1/q$ and $\bar d_1=d_1/q$ are coprime. Now we modifiy $c_2,d_2$ as $c_2^s=c_2-s\,\bar d_1$, $d_2^s=d_2-s\,\bar c_1$, $s>0$. We still have $p(t)=c_1(t)c_2^s(t)-d_1(t)d_2^s(t)$ because $(c_1,d_1)$ is a multiple of $(\bar c_1,\bar d_1)$ and we still have $c_2^s\in t^m+P_m$, $d_2^s\in P_n$. We claim that $c_2^s,d_2^s$ are coprime for sufficiently large $s$ and thus again Case 1 applies after a permutation of $c_1,d_1$ and $c_2^s,d_2^s$.

Indeed, any possible nontrivial common factor of them for a certain $s$ is also a factor of $p$. Therefore there exists a (possibly complex) zero $z$ of $p$ such that $c_2^s(z)=d_2^s(z)=0$. As $\bar c_1,\bar d_1$ are coprime, the vector $(\bar c_1(z),\bar d_1(z))$ is nonzero for any zero $z$ of $p$. This must also be the case for $c_2^s=c_2-s\,\bar d_1$ and $d_2^s=d_2-s\,\bar c_1$ if $s>0$ is sufficiently large because $p$ has finitely many zeros.

This completes the proof that $f^{-1}(p)$ is connected if $p$ has at least one real zero.

Suppose now that $p$ has no real zero and hence $n+m$ is even. First, we divide $p$ by $t^n$ with a remainder: $p=t^n\,c_2+d_2$ with $d_2\in P_n$. Then we can choose $c_1(t)=t^n$ and $d_1=1$ in (\ref{eq1}). The corresponding matrix actually is a companion matrix of $p$ and therefore in $f^{-1}(p)$.

If $m=1$ then the matrix correponding to $c_1'(t)=t^n$, $d_1'=-1$, $d_2'=-d_2$, $c_2'=c_2$ is also in $f^{-1}(p),$ but cannot be reached on a path within $f^{-1}(p),$ because $d_1$ must vanish on this path which is impossible because $p$ has no real zero.

Otherwise, we can suppose that $n,m\geq 2$. We choose $c_1', d_1'$ such that they have no common complex zeros and complete with $c_2',d_2'$ calculated from (\ref{eq1}). In the case of even $n,m$ we can choose $c_1'$ having exactly two simple real zeros and $d_1'$ having exactly one real zero between those of $c_1'$. In the case of odd $n,m$ we can choose $c_1'$ having exactly three simple real zeros and $d_1'$ having exactly two real zeros separating those of $c_1'$.

The matrix corresponding to $c_1', d_1', c_2',d_2'$ also belongs to $f^{-1}(p)$ by construction but cannot be connected within it to the companion matrix of $p$ because this would continuosly modify a couple $(c_1,d_1)$ of type $0$ into a couple $(c_1',d_1')$ of type $1$ or $2$ which is impossible (see above for a discussion). This completes the proof.

It can be shown that, in the above context, the number of connected components of $f^{-1}(p)$ is $\min(n,m)+1$ if $p$ has no real zero, but this was not asked.

• @user9527 I rewrote the case $r=2$ to give a necessary and sufficient condition for the connectedness of $f^{-1}(c)$. For the cases $r>2$, I have a first idea generalising the claim concerning $L$, but nothing else yet. Aug 27, 2018 at 17:51