3
$\begingroup$

Is there any way of creating a positive matrix which has integer eigenvalues? Each entry $a_{ij}$ of the matrix must be strictly greater than $0$. I get how to create a matrix with certain eigenvalues using diagonal matrices, but I do not know how to make sure the matrix is strictly positive

$\endgroup$
  • 1
    $\begingroup$ @J. W. Tanner The OP wants $>0$ entries everywhere. $\endgroup$ – Jean Marie Jan 28 at 15:44
  • 1
    $\begingroup$ By "positive" do you mean positive definite or positive entries? $\endgroup$ – Robert Israel Jan 28 at 15:54
2
$\begingroup$

The problem of determining which complex spectrum can be realised by a nonnegative matrix is known as a nonnegative inverse eigenvalue problem. For an overview, you may read the following survey paper:

Egleston, Lenker, and Narayan, The nonnegative inverse eigenvalue problem, Linear Algebra and Its Applications, 379 (2004), 475-490.

Your requirement is more demanding because the matrix in question is not just nonnegative, but positive. Certainly, not every spectrum is realisable, because the spectrum has to satisfy the Perron condition (that the spectral radius is a simple eigenvalue) and some other necessary conditions (such as the trace condition $\operatorname{tr}(A^k)=\sum_i\lambda_i^k>0$ for every positive integer $k$). Since the literature is vast, I am not sure if the problem has been solved yet, or whether there is a constructive method for a wide class of spectra, but I'll exhibit a simple constructions below that is applicable for some spectra.

Given any decreasing sequence of integers $\lambda_1>\lambda_2\ge\cdots\ge \lambda_n\ge0$, the matrix $$ \begin{aligned} A&=\pmatrix{1\\ t&1\\ t&&1\\ \vdots&&&\ddots\\ t&&&&1} \pmatrix{\lambda_1&1&1&\cdots&1\\ &\lambda_2\\ &&\lambda_3\\ &&&\ddots\\ &&&&\lambda_n} \pmatrix{1\\ -t&1\\ -t&&1\\ \vdots&&&\ddots\\ -t&&&&1}\\ &=\pmatrix{\lambda_1-(n-1)t&1&1&\cdots&1\\ (\lambda_1-\lambda_2)t-(n-1)t^2&\lambda_2+t&t&\cdots&t\\ (\lambda_1-\lambda_3)t-(n-1)t^2&t&\lambda_3+t&\ddots&\vdots\\ \vdots&\vdots&\ddots&\ddots&t\\ (\lambda_1-\lambda_n)t-(n-1)t^2&t&\cdots&t&\lambda_n+t} \end{aligned} $$ is entrywise positive when $t>0$ is sufficiently small, and the eigenvalues of $A$ are the integers $\lambda_1,\lambda_2,\ldots,\lambda_n$. When $\lambda_1-\lambda_2\ge n$, we may choose $t=1$, so that the previous construction gives a positive integer matrix with a prespecified integer spectrum.

This construction can be generalised to the case where $$ \begin{cases} \lambda_1>\lambda_2\ge\cdots\ge\lambda_k\ge0>\lambda_{k+1}\ge\cdots\ge\lambda_n \text{ and}\\ \lambda_1-\lambda_2>\sum_{i=k+1}^n|\lambda_i|. \end{cases} $$ Let $e$ and $\tilde{e}$ denote the all-one vector in $\mathbb R^{k-1}$ and $\mathbb R^{n-k}$ respectively, $\Lambda=\operatorname{diag}(\lambda_2,\ldots,\lambda_k)$ and $\widetilde{\Lambda}=\operatorname{diag}(\lambda_{k+1},\ldots,\lambda_n)$. Now let $t>0$ be sufficiently small. Define $$ \begin{aligned} A&= \pmatrix{1\\ te&I\\ \tilde{e}&&I} \pmatrix{\lambda_1&e^T&\tilde{e}^T(tI-\widetilde{\Lambda})\\ &\Lambda\\ &&\widetilde{\Lambda}} \pmatrix{1\\ -te&I\\ -\tilde{e}&&I}\\ &= \pmatrix{\lambda_1&e^T&\tilde{e}^T(tI-\widetilde{\Lambda})\\ \lambda_1te&tee^T+\Lambda&te\tilde{e}^T(tI-\widetilde{\Lambda})\\ \lambda_1\tilde{e}&\tilde{e}e^T&\tilde{e}\tilde{e}^T(tI-\widetilde{\Lambda})+\widetilde{\Lambda}} \pmatrix{1\\ -te&I\\ -\tilde{e}&&I}\\ &= \pmatrix{\lambda_1-te^Te-\tilde{e}^T(tI-\widetilde{\Lambda})\tilde{e}&e^T&\tilde{e}^T(tI-\widetilde{\Lambda})\\ t\lambda_1e-t(tee^T+\Lambda)e-te\tilde{e}^T(tI-\widetilde{\Lambda})\tilde{e}&tee^T+\Lambda&te\tilde{e}^T(tI-\widetilde{\Lambda})\\ \lambda_1\tilde{e}-t\tilde{e}e^Te-\tilde{e}\tilde{e}^T(tI-\widetilde{\Lambda})\tilde{e}-\widetilde{\Lambda}\tilde{e}&\tilde{e}e^T&\tilde{e}\tilde{e}^T(tI-\widetilde{\Lambda})+\widetilde{\Lambda}}. \end{aligned} $$ The first column of $A$ is given by $$ a_{i1}= \begin{cases} \lambda_1-\sum_{i=k+1}^n|\lambda_i|-(n-1)t&\text{when } i=1,\\ \left(\lambda_1-\lambda_i-\sum_{i=k+1}^n|\lambda_i|-(n-1)t\right)t&\text{when } 1<i\le k,\\ \left(\lambda_1-\lambda_i-\sum_{i=k+1}^n|\lambda_i|-(n-1)t\right)&\text{when } i>k \end{cases} $$ and hence it is positive. The second block column of $A$ is clearly positive. On the last block column, since $\tilde{e}^T(tI-\widetilde{\Lambda})$ is a positive vector, the first two sub-blocks are positive. The last sub-block $\tilde{e}\tilde{e}^T(tI-\widetilde{\Lambda})+\widetilde{\Lambda}$ is equal to $$ \pmatrix{t+|\lambda_{k+1}|&t+|\lambda_{k+2}|&\cdots&t+|\lambda_n|\\ t+|\lambda_{k+1}|&t+|\lambda_{k+2}|&\cdots&t+|\lambda_n|\\ \vdots&\vdots&&\vdots\\ t+|\lambda_{k+1}|&t+|\lambda_{k+2}|&\cdots&t+|\lambda_n|} -\pmatrix{|\lambda_{k+1}|\\ &|\lambda_{k+2}|\\ &&\ddots\\ &&&|\lambda_n|}, $$ which is positive too. Therefore $A$ is a positive matrix.

$\endgroup$
  • $\begingroup$ Excellent method [+1]. Great idea to use this "change of base $PTP^{−1}$ with a matrix $P$ having a tunable $t$ and, moreover, the choice of $T$ with this line of ones ! How have these ideas come up to you ? $\endgroup$ – Jean Marie Jan 28 at 21:13
  • 1
    $\begingroup$ @JeanMarie I can't explain. It just came to mind. $\endgroup$ – user1551 Jan 29 at 2:19
4
$\begingroup$

The $n \times n$ matrix with diagonal entries $b$ and off-diagonal entries $a$ has eigenvalues $b-a$ (with multiplicity $n-1$) and $b + (n-1) a$.

$\endgroup$
3
$\begingroup$

If you are fine with some restrictions on eigenvalues, then this procedure might be helpful:

  1. Generate orthonormal matrix $S$ with the first column being in the direction of $u=(1,1,\ldots 1)$. For example, you can start with the vector $u$ and $d-1$ random vectors and apply Gram-Schmidt process to them.

  2. Create $J=\begin{pmatrix}\lambda_1&0&\cdots\\0&\lambda_2&\cdots\\\cdots&\cdots&\cdots\end{pmatrix}$. Where all lambdas are positive and $\lambda_1$ is sufficiently large.

  3. Now matrix $M=SJS^{-1}$ has all positive values (if not, increase $\lambda_1$) and eigenvalues $\lambda_i$.

You can also make matrix $M$ integer by replacing $S$ with its rational approximation ($S_1=\frac1N[NS]$) and multiplying the matrix $M$ by the common denominator of its elements. That will also increase the eigenvalues, but if you don't care what they are, that's fine.

Example: Start with $$ S_0 = \begin{pmatrix}1&0&0&0\\1&1&0&0\\1&0&1&0\\1&0&0&1\end{pmatrix}. $$ After Gram-Schmidt and rationalization: $$ S_1 = \begin{pmatrix}0.5&-0.29&-0.41&-0.71\\0.5&0.87&0&0\\0.5&-0.29&0.82&0\\0.5&-0.29&-0.41&0.71\end{pmatrix}. $$ Take $$ M=S_1\begin{pmatrix}5&0&0&0\\0&1&0&0\\0&0&2&0\\0&0&0&3\end{pmatrix}S_1^{-1} = \frac16\begin{pmatrix}19&6&4&1\\6&12&6&6\\4&6&16&4\\1&6&4&19\end{pmatrix}. $$ Thus, matrix $M'=6M$ is integer and has eigenvalues $(30,6,12,18)$.

$\endgroup$
  • $\begingroup$ I am sorry but how can you prove that this method works in general ? $\endgroup$ – Jean Marie Jan 28 at 21:15
1
$\begingroup$

One special case that the matrix entries are strictly positive and it has integer eigenvalues is the reciprocal matrix defined as \begin{equation} A = \begin{pmatrix} 1 & a_{12} & \dots & a_{1N}\\ \frac{1}{a_{12}} & 1 & &\vdots \\ \vdots &&&\vdots \\ \frac{1}{a_{1N}} &\dots &\dots& 1 \end{pmatrix} \end{equation} whose rank is $1$ (all eigenvalues are $0$ except one), and its Perron-Frobenius eigenvalue is proved to be $\lambda_\mathrm{pf}=N$.

$\endgroup$

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.