14
$\begingroup$

Suppose $M \in \mathcal M(n \times n; \mathbb R)$ and $N \in \mathcal M(n \times m; \mathbb R)$ are fixed with $N \neq 0$. Let \begin{align*} E = \{X \in \mathcal{M}(m \times n; \mathbb R) : \rho(M-NX) < 1\}, \end{align*} where $\rho(\cdot)$ denotes the spectral radius of a matrix. I want to know whether the closure $\bar{E}$ of $E$ is equal to
$$F = \{X \in \mathcal{M}(m \times n; \mathbb R) : \rho(M-NX) \le 1\}.$$ We will assume $E$ is not empty.

If we define following composition of continuous maps \begin{align*} f: X \mapsto M-NX \mapsto (\lambda_1(M-NX), \dots, \lambda_n(M-NX)) \mapsto (|\lambda_1(M-NX)|, \dots, |\lambda_n(M-NX)|) \\ \mapsto \max( |\lambda_1(M-NX)|, \dots, |\lambda_n(M-NX)|). \end{align*} Then $f$ is continuous into $[0, \infty)$. We note $E = \{X: f^{-1}([0,1)\}$ and $F = \{X: f^{-1}([0,1])\}$. So $E$ is open and $F$ is closed. Clearly $\bar{E} \subset F$. But I could not show the other direction (or possibly $\bar{E}$ is a proper subset of $F$). I tried to construct a sequence $\{X_n\}$ converging to $X \in F \setminus E$ by multiplying a factor $1-\varepsilon$ to $X$ but apparently to conclude $\bar{E} = F$ we need some kind of sublinearatily of spectral radius which is not true in general.

$\endgroup$
  • 1
    $\begingroup$ If $N=0$ and $\rho(M)=1$, then the LHS is empty but the RHS is the whole matrix space. $\endgroup$ – user1551 May 26 '18 at 10:17
  • $\begingroup$ Actually I made the assumption $E$ is not empty. But sorry, the assumption was in the middle which made it not clear enough. $\endgroup$ – user1101010 May 26 '18 at 14:08
  • $\begingroup$ The problem can be restated as follows: "if $1$ is a local minimum of $f$, must it also be a global minimum?" That is certainly true if $N$ has rank $m$, as then the mapping $X \mapsto M - NX$ is open and any local minimum of $f$ must be a local minimum of $\rho$, which can only be $0$. For lower ranks the answer is less obvious. $\endgroup$ – Niels J. Diepeveen May 29 '18 at 9:45
  • $\begingroup$ @NielsJ.Diepeveen: I don't quite understand your restated version. If it is true, i.e., $1$ is a global minimum, then $E = \emptyset$ and it is certainly true $\bar{E} \neq F$. But I am assuming $E$ is not empty (this can be done by choosing appropriate $M,N$). $\endgroup$ – user1101010 May 29 '18 at 16:29
  • $\begingroup$ @NielsJ.Diepeveen: Thinking about the second part of your comment, I can see $X \mapsto M-NX$ is open if $N$ has full rank, but could not follow why the local minimum of $f$ must be a local minimum of $\rho(\cdot)$. Sorry, I am having too many questions. $\endgroup$ – user1101010 May 29 '18 at 16:36
1
$\begingroup$

$\newcommand{\NN}{{\mathbb{N}}}\newcommand{\CC}{{\mathbb{C}}}\newcommand{\RR}{{\mathbb{R}}}\newcommand{\QQ}{{\mathbb Q}}\newcommand{\ra}{\rightarrow}\newcommand{\ds}{\displaystyle}\newcommand{\mat}[1]{\left(\begin{matrix}#1\end{matrix}\right)}\newcommand{\lam}{\lambda}\renewcommand{\P}{{\mathcal P}}\newcommand{\N}{{\mathcal N}}\newcommand{\M}{{\mathcal M}}\renewcommand{\L}{{\mathcal L}} \newcommand{\EQ}[2]{\begin{equation} {{#2}\label{#1}} \end{equation}}$

Claim: The closure of $E$ is equal to $F.$

Proof: In a first step, we normalise the problem. We can assume that $N$ is a block matrix $$N=\mat{I_r&0\\0&0},$$ where $r$ is the rank of $N$, $I_r$ is the identity of size $r\leq\min(m,n)$ and the other blocks consist of zeros and have appropriate sizes ( $r\times (m-r)$, $(n-r)\times r$ and $(n-r)\times (m-r)$). Some or even all of them can be absent. To justify this recall that any $n$ by $m$ matrix $N$ can be written $$N=U\mat{I_r&0\\0&0}V,\ \ r=\mbox{rank}(N),$$ where $U$ and $V$ are invertible. Then the condition $\rho(M-NX)<1$ can be written $$\rho\left(U^{-1}MU-\mat{I_r&0\\0&0}(VXU)\right)<1,$$ because similar matrices have the same spectrum. Then we can assume that $r=m$ since the zero block column of $N$ (and the correponding rows of $X$) do not contribute anything. Finally we can assume that the first $m$ rows of $M$ contains only zeros: Otherwise, we modify $X$ and $M$ accordingly.

From now on, we assume without loss of generality that $N=\mat{I_m\\0}$ and the first $m$ rows of $M$ vanish.

We first consider the case $m=1.$ This will also be useful as a preparation for the general case. We use the Laplace (or cofactor) expansion for the first row of the determinant giving the characteristic polynomial $p_{M-NX}(\lam)$ $$\tag{1}\label{lap}{\det(\lam I - M+ NX)=(x_1+\lam)C_1(\lam)+\sum_{k=2}^n x_kC_k(\lam)}$$ where $X=(x_1,\dots,x_n)$ and $C_j(\lam)$, $j=1,\dots,n$ are the $1,j$ cofactors of $\lam I - M$, that is $C_j(\lam)=(-1)^{j+1}M_{1j}(\lam)$, where $M_{1j}(\lam)$ is the determinant of the $n-1$ by $n-1$ matrix obtained from $\lam I-M$ by deleting its first row and its $j$-th column. Observe that $C_1(\lam)\in \lam^{n-1}+\P_{n-1}$ and $C_j(\lam)\in\P_{n-1}$, where $\P_k$ denotes the vector space of all polynomials of degree less than $k$. Before continuing the proof, we need some auxiliary statements.

Lemma 1 Let $D(\lam)$ denote the gcd of $C_j(\lam)$, $j=1,\dots,n$ and let $d$ denote its degree. Then the mapping $ \EQ{map}{L:\RR^{ n} \to D(\lam)\P_{n-d},\ \ L(X)=\sum_{k=1}^n x_kC_k(\lam)\mbox{ if } X=(x_1,\dots,x_n)}$ is surjective (or onto).

Remark: The characteristic polynomial of $M-NX$ is the given by $\lam C_1(\lam)+L(X)$.

Proof: Observe first that each $L(X)$ must be divisible by $D(\lam)$ because every $C_j(\lam)$ is divisible by it. Consider now a polynomial $p(\lam)\in\P_{n-d}$. We want to find $X\in\RR^n$ such that $L(X)=D(\lam)p(\lam)$.

Consider the polynomials $B_j(\lam)=C_j(\lam)/D(\lam)$. By assumption, their gcd is 1. So by Bezout's identity, $p$ can be expressed in the form $$p(\lam)=\sum_{j=1}^ng_j(\lam)B_j(\lam),$$ where $g_j(\lam)$ are certain polynomials. The Lemma is proved once we show the

Claim: It is possible to choose constant $g_j(\lam)$.

If $\ell$ denotes the maximum of the degrees of $g_j(\lam)$, $j=2,\dots,n$, then we have to show that we can achieve $\ell=0$. Indeed, then $\sum_{j=2}^ng_jB_j(\lam)$ is in $\P_{n-1-d}$ and as $B_1(\lam)\in \lam^{n-d-1}+\P_{n-d-1}$, the quotient $g_1(\lam)=(p(\lam)-\sum_{j=2}^ng_jB_j(\lam))/B_1(\lam)$ must also be a constant.

Suppose, we could not achieve $\ell=0$ and that a certain $\ell>0$ is the minimal $\ell$ possible. Then we write $g_j(\lam)=h_{j\ell}\lam^\ell\mod\P_{\ell-1}$ for $j=2,\dots,n$. Now let $z_k(\lam)$ denote the $k$-th row of $\lam I-M$ for $k=2,\dots,n$. Its components $z_{k,j}(\lam)$ are constant except for the $k$-th one, which is $z_{kk}(\lam)=\lam-m_{kk}$ with a diagonal element of $M$. Finally define $\tilde M(\lam)=\lam I -M -\lam E_{11}$, where $E_{11}$ is the matrix having a 1 in the upper left position and zeros elsewhere. The determinant of $\tilde M(\lam)- N\,z_k(\lam)$ is zero, because the first and the $k$-th row of the matrix are identical. This means that $$0=\sum_{j=1}^n z_{kj}(\lam)C_j(\lam)=D(\lam)\left(\sum_{j=1}^nz_{kj}(\lam)B_j(\lam)\right).$$ for $k=2,\dots,n$. Therefore we also have $$p(\lam)=\sum_{j=1}^n\left(g_j(\lam)-\sum_{k=2}^nh_{k\ell}z_{kj}(\lam)\lam^{\ell-1}\right) \,B_j(\lam).$$ By construction, the factors of $B_2,\dots,B_n$ have a degree smaller than $\ell$ contradicting the assumed minimality of $\ell$. Therefore we can achieve constant $g_2,\dots,g_n$ and as seen above, the Lemma is proved.

Corollary 1 Let $D(\lam)$ denote the gcd of $C_j(\lam)$, $j=1,\dots,n$ and let $d$ denote its degree. Then the kernel $K$ of the mapping $L$ of Lemma 1 has dimension $d$ and there is a $(n-d)$-dimensional subspace $S$ of $\RR^n$ such that the restriction $L{\big|}_S:S\to D(\lam)\P_{n-d}$ of $L$ is bijective (or one to one and onto).

Proof: The first statement follows from the rank-nullity theorem and the sujectivity of $L$: $\dim K+\dim \P_{n-d}=n$.

For the second, we consider the unit vectors $e_j=(0,\dots,0,1,0,\dots,0)$ with a $1$ at the $j$-th position and their images $L(e_j)$, $j=1,\dots,n$. They generate the image of $D(\lam)\P_{n-d}$ of $L$ which has dimension $n-d$. Therefore we can select a basis $\{L(e_j)\}_{j\in\M}$ among them, where $\M$ is a certain subset of $\{1,\dots,n\}$ with $n-d$ elements. Then we put $S=\langle\{e_j\}_{j\in\M}\rangle$. Clearly $L{\big|}_S:S\to \mbox{im}(L)$ is an isomorphism.

For later use, we select $d$ vectors generating $K$, namely the vectors $z_r=e_r-\left(L{\big|_S}\right)^{-1}L(e_r)$, $r\in\N:=\{1,\dots,n\}\setminus \M$.

After these preliminaries, let us now continue the proof of the claim in the case $m=1$. First, we show that the gcd $D(\lam)$ of the $C_j(\lam)$ has only zeros inside the open unit disk, that is $|\mu|<1$ for any zero $\mu$ of $D$. This comes from the assumption that there exists a matrix $X_0\in E$, i.e.\ such that the spectral radius $\rho(M-N\,X_0)<1$ and the expansion of the characteristic polynomial (see below Lemma 1) $$p_{M-N X_0}(\lam)=\lam C_1(\lam)+L(X_0).$$ Since $D(\lam)$ divides $C_1(\lam)$ and $L(X_0)$, it is a factor of $p_{M-N X_0}(\lam)$, which has only zeros in the open unit disk. So the same holds for $D(\lam)$.

Now let any $X_1\in F$ be given, i.e.\ the characteristic polynomial $p_{M-N X_1}(\lam)=\lam C_1(\lam)+L(X_1)$ has all its zeros in the closed unit disk, i.e.\ $|\mu|\leq 1$ if $\mu$ is a zero of $p_{M-N X_1}(\lam)$. We want to find $X\in E$ (i.e.\ with $\rho(M-NX)<1$) arbitrarily close to $X_1$.

Consider the quotient $q_1(\lam)=p_{M-N X_1}(\lam)/D(\lam)$. Observe that the zeros of $q_1(\lam)$ are in the closed unit disk and that all the zeros of $p_{M-N X_1}(\lam)$ having modulus 1 must be zeros of $q_1$, because $D(\lam)$ has no such zeros. Let us write $q_1(\lam)=\prod_{k=1}^{n-d}(\lam-\mu_k)$ with certain $\mu_k$, $|\mu_k|\leq1$. Now define for $s\in[0,1[$ the polynomials $q_s(\lam)=\prod_{k=1}^{n-d}(\lam-s\mu_k)$. Their coefficients are real because, as for $q_1(\lam)$, its non-real zeros appear in pairs of conjugate complex numbers. By construction, the zeros of $q_s$ are in the open unit disk.

Recall that $L(X_1)=p_{M-N X_1}(\lam)-\lam C_1(\lam)=q_1(\lam)D(\lam)-\lam C_1(\lam) =:p_1(\lam)$. Therefore $X_1-\left(L\big|_S\right)^{-1}p_1(\lam)=:Z_1$ is an element of the kernel $K$ of $L$. Now put $p_s(\lam)=q_s(\lam)D(\lam)-\lam C_1(\lam)$ and $$X_s=Z_1+\left(L\big|_S\right)^{-1}p_s(\lam)$$ for $s\in[0,1[$.

Then as $s\to1-$, we first have $q_s(\lam)\to q_1(\lam)$, next $p_s(\lam)\to p_1(\lam)$ and then by the continuity of $\left(L\big|_S\right)^{-1}$, we have $X_s\to X_1$. As by construction the characteristic polynomials of $M-NX_s$ are $q_s(\lam)D(\lam)$, we have constructed $X_s\in E$, $s\in[0,1[$, tending to the given $X_1$. This completes the proof in the case $m=1$.

For arbitrary $m$, the proof is identical if the gcd $D(\lam)$ of the cofactors $C_j(\lam),\, j=1,\dots,n$ has all its zeros in the open unit disk. Actually, except for the partitioning of the matrix, we are in the case $m=1$. Unfortunately, this is not necessarily the case. To repair this, we will modify row by row of a matrix $X_1\in F$ into rows of algebraically independent transcendants - of course inside $F$ and by arbitrarily small amounts. Then we show that $D(\lam)$ has only zeros $\mu$, $|\mu|<1$ if the rows 2 to $m$ of $X_1$ contain algebraically independent transcendants.

Given $X_1\in\RR^{m,n}$, we denote by $X_1^{(1)}$ its first row and by $\hat X_1$ the matrix in which the elements of the first row have been replaced by zeros. Then $$M-NX_1=M-\tilde N\hat X_1-e_1X_1^{(1)},$$ where $\tilde N$ is obtained from $N$ by replacing the upper left element by 0. Here $e_1$ is the first unit vector in $\RR^n$, later it will also denote the one in $\RR^m$.

Lemma 2 Given $X_1\in F$ and a positive $\delta$, there exists a row vector $y$ such that\ a) $||y-X_1^{(1)}||<\delta,$\ b) $\hat X_1+e_1y\in F$, that is $\rho(M-\tilde N \hat X_1-e_1y)\leq1$ and\ c) the elements of $y$ are algebraically independent transcendents over the field $\QQ(M,\hat X_1)$ generated by the elements of $M$ and $\hat X_1$.

Proof: We proceed as in the proof of the case $m=1$. The matrix $\tilde M=M-\tilde N \hat X_1$ plays the role of $M$, the polynomials $C_j(\lam)$, $j=1,\dots,n$, are the $1,j$ cofactors of $\lam I-\tilde M$ and $D(\lam)$ is their gcd. Lemma 1 and its corollary still hold. Then the characteristic polynomial $$p_{M-NX_1}(\lam)=p_{\tilde M-e_1X_1^{(1)}}(\lam)=\lam C_1(\lam)+L(X_1^{(1)})$$ has all its zeros in the closed unit disk and it is a multiple of $D(\lam).$ Therefore $D(\lam)$ has only zeros in the closed unit disk in the present situation.

Again, we consider $p_1(\lam)=p_{M-NX_1}(\lam)-\lam C_1(\lam)=L(X_1^{(1)})$, $Y_1=\left(L\big|_S\right)^{-1}p_1(\lam)$ and the element $Z_1=X_1^{(1)}-Y_1$ of the kernel $K$ of $L$. We will now modify $Y_1,Z_1$ a little bit to obtain the vector $y$ required in the statement.

We begin with $Z_1$. We can write $Z_1=\sum\{\alpha_j z_j\mid j\in\N\}$, where $\alpha_j$ are certain real numbers and $z_j=e_j-\left(L\big|_S\right)^{-1}(L(e_j))$, $j\in\N\}$, form the basis of the kernel $K$ of $L$ discussed in the proof of the Corollary. Now we choose $A_j$ close to $\alpha_j$ which are algebraically independent transcendents over $\QQ(M,\hat X_1)$. This is possible, because the algebraic closure of $\QQ(M,\hat X_1)$ in $\CC$ is countable. Then $Z_2=\sum\{A_j z_j\mid j\in\N\}$ is in the kernel $K$, close to $Z_1$, and its $j$-th components, $j\in\N$, are algebraically independent transcendants over $\QQ(M,\hat X_1)$.

The quotient $q_1(\lam)=p_{\tilde M-e_1X_1^{(1)}}(\lam)/D(\lam)$ also has only zeros in the closed unit disk and we write it $q_1(\lam)=\prod_{k=1}^{n-d}(\lam-\mu_k)$ with certain $\mu_k$, $|\mu_k|\leq1$. We choose $s\in[0,1[$ such that $\tilde q_2(\lam)=\prod_{k=1}^{n-d}(\lam-s\mu_k)$ is close to $q_1(\lam)$, but it has all its zeros in the open unit disk. Now let $\tilde Y_2=\left(L\big|_S\right)^{-1}(\tilde q_2(\lam)D(\lam)-\lam C_1(\lam))$. Then $\tilde Y_2\in S=\langle\{e_j\mid j\in \M\}\rangle$ is close to $Y_1$ and $L(\tilde Y_2)=\tilde q_2(\lam)D(\lam)-\lam C_1(\lam)$. Now the algebraic closure of $\QQ(M,\hat X_1,\{z_j\}_{j\in\N},\{A_j\}_{\in\N})$ in $\CC$ is countable and therefore there is a vector $Y_2\in S$ close to $\tilde Y_2$ such that its components are algebraically independent transcendents over that field. If $Y_2$ is sufficiently close to $\tilde Y_2$, then the polynomial $q_2(\lam)=(L(Y_2)+\lam C_1(\lam))/D(\lam)$ is so close to $\tilde q_2(\lam)$ that its zeros are still in the open unit disk.

Then the vector $y=Y_2+Z_2$ satisfies the three requirements of the statement: It is close to $X_1^{(1)}$; since $p_{\tilde M-e_1(Y_2+Z_2)}=L(Y_2+Z_2)+\lam C_1\lam= L(Y_2)+\lam C_1(\lam)=q_2(\lam)D(\lam)$, its zeros are in the closed unit disk and hence $\hat X_1+e_1y\in F$; finally the components of $y$ are algebraically independent transcendents over $\QQ(M,\hat X_1)$. Thus Lemma 2 is proved.

We can apply Lemma 2 as well to one of the rows $2,\dots,m$ as to the first row of $M$ -- it is sufficient to exchange the first and this row and the corresponding columns to reach the exact situation of Lemma 2. This allows us to apply Lemma 2 successively to the row $2,\dots,m$. This proves

Corollary 2 Given $X_1\in F$ and positive $\delta$, there exists a $m\times n$-matrix $X_2$ such that $||X_1-X_2||<\delta$, $X_2\in F$ and the components of the rows $2,\dots,m$ of $X_2$ are algebraically independent transcendents over $\QQ(M)$.

Now we claim that the gcd $D(\lam)$ of the cofactors $C_j(\lam)$ for the matrix $\lam I -M -N X_2$ has only zeros in the open unit disk. Once this is proved, the proof of the original claim is complete because, except for the partitioning of the matrix, we are in the case $m=1$.

A priori, $D(\lam)$ is a polynomial in $\lam$ with coefficients in $\QQ(M,\hat X_2)$ because the $C_j(\lam)$ are (Recall that $\hat X_2$ is the matrix obtained from $X_2$ by replacing the first row with zeros). The latter are actually in $K[\hat X_2][\lam]$, where $K=\QQ(M)$. Since $K$ is a field, $K[\hat X_2]$ is a unique factorisation domain because the elements of $\hat X_2$ are algebraically independent transcendents. We multiply $D(\lam)$ by the lcm of the denominators of the coefficients (seen as elements of $K(\hat X_2)$), and then divide by its content (that is the gcd of the coefficients seen as elements of $K[\hat X_2]$). We call the result $D(\lam)$ again. Then $D(\lam)\in K[\hat X_2][\lam]$ has content 1 and divides every $C_j(\lam)$ in $K(\hat X_2)[\lam]$ by definition. By Gauss's Lemma, it follows that $D(\lam)$ divides every $C_j(\lam)$ in $K[\hat X_2][\lam]$.

Now, for $j=1,\dots,n$, $C_j(\lam)$ does not contain any element of the $j$-th column of $\hat X_2$. Therefore $D(\lam)$ must actually be an element of $K[\lam]$.

Now we use that $E$ is not empty, that is there exists a $m\times n$-matrix $X_0$ such that $\rho(M-N X_0)<1$. Let $C_j^{0}$ denote the minors constructed for $\lam I-M+NX_0$ instead of $\lam I-M+NX_2$ where we obtained the $C_j(\lam)$, $j=1,\dots,n$. Since $D(\lam)\in K[\lam]$ divides every $C_j(\lam)$ in $K[\hat X_2][\lam]$, we can replace the elements of $\hat X_2$ by those of $\hat X_0$ in these $n$ relations and obtain that $D(\lam)$ divides every $C_j^{0}$ in $K(\hat X_0)[\lam]\subset \RR[\lam]$. Hence $D(\lam)$ divides also the characteristic polynomial $\det(\lam I-M+NX_0)$ (see (\ref{lap})) and hence has only zeros in the open unit disk as claimed. As shown above, this completes the proof for general $m$.

$\endgroup$
  • $\begingroup$ Thanks for your answers. I am planning to digest them in the weekends. $\endgroup$ – user1101010 Dec 7 '18 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.