4
$\begingroup$

Given a positive definite matrix $Q\in\mathbb{R}^{n \times n}$, I want to find a diagnonal matrix $D$ such that $rank(Q-D) \leq k < n$.

I think this can be regarded as a generalization of eigenvalue problem, which is basically problem of finding a diagonal matrix $\lambda I$ such that $rank(Q-\lambda I) < n$.

Is there any theory about this problem?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Good question. But, 1) is there any reason to think that, in general, you can reduce the rank by more than 1? 2) why the restriction to positive definite matrices? isn't the question of interest for all matrices? $\endgroup$
    – Gerry Myerson
    Commented Dec 27, 2017 at 16:05
  • $\begingroup$ 1) For example, think of the matrix $\begin{bmatrix} 2 &2& 1\\ 2 & 6 & 2\\1 & 2 & 4\end{bmatrix}$. We cannot reduce its rank more than one by just substracting $\lambda I$, but if we substract $\begin{bmatrix} 1 &0& 0\\ 0 & 2 & 0\\0 & 0 & 3\end{bmatrix}$, we can reduce the rank by 2. 2) Yes, but I am especially interested in the case where $Q$ is positive definite. $\endgroup$
    – Minji Kim
    Commented Dec 28, 2017 at 2:28
  • 1
    $\begingroup$ OK, that's an example where you can reduce the rank by more than 1 (a simpler example would be $$\pmatrix{1&0&0\cr0&2&0\cr0&0&3\cr}$$ but what about in general? $\endgroup$
    – Gerry Myerson
    Commented Dec 28, 2017 at 4:16

2 Answers 2

Reset to default
4
$\begingroup$

Your problem can be restated as follows: To a given symmetric matxix, can you add a diagonal matrix so that the result has eigenvalue $0$ with high multiplicity?

This belongs to the theory which is called Additive Inverse Eigenvalue Problems. See, for example this paper, which seems to treat a very similar problem:

D.Paul Phillips, Some partial inverse eigenvalue problems: recovering diagonal entries of symmetric matrices, Linear Algebra and its Applications Volume 380, 263-270,

however the exact statement you ask does not follow from this result, and I suppose that your problem is unsolved.

Here is a survey of such problems:

Moody T. Chu, Inverse eigenvalue problems, SIAM Rev. Vol. 40, No. 1, pp. 1–39.

Improve this answer
$\endgroup$
0
3
$\begingroup$

You can limit the question to real symmetric matrices $A$ (with diagonal $0$ if desired). For large enough $k,$ the matrix $A+kI$ will be positive definite and you are then allowed to change all the diagonal entries.

As noted in a comment (and overlooked in my earlier answer) this $5 \times 5$ matrix (where the diagonal entries are free to be assigned) will have rank at least $4.$

$$ \left[ \begin {array}{ccccc} a&1&0&0&0\\ 1&b&1&0&0\\ 0&1&c&1&0\\ 0&0 &1&d&1\\ 0&0&0&1&e\end {array} \right] $$ The same construction works for any $n.$

It is curious that having the freedom to chose any diagonal matrix may be no more effective than being restricted to choosing a multiple of the identity matrix. Perhaps the thing to generalize is not $\lambda I$ to $D$ but $\lambda I$ to $\lambda D$ for a given $D$. Hence:

Given $n \times n$ matrices $Q,D$ with $D$ diagonal, consider scalars $\lambda$ such that $rank(Q-\lambda D) < n.$ Discuss the theory.

We might call $\lambda$ an eigenvalue for $Q$ with respect to $D.$ Likewise a vector $X$ with $Qx=\lambda Dx$ (which there will then be) might be termed a $\lambda$-eigenvector for $Q$ with respect to $D.$

When $D$ is has all entries non-zero, $D^{-1}$ exists and we are simply looking at the eigenvalues and eigenvectors of $D^{-1}Q.$ When $D$ itself has rank $k \lt n$ one can still consider the degree $k$ polynomial $|Q-xD|$, it's roots etc. I'm not sure how it would all work out.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ What about the matrix that has ones in the lower and upper tridiagonal ($|i-j|=1$) and zeros elsewhere? It has an invertible $(n-1)\times (n-1)$ submatrix (because it's triangular) no matter what you add to its diagonal. $\endgroup$
    – Federico Poloni
    Commented Dec 28, 2017 at 14:28
  • $\begingroup$ True. I'll change the answer. I at first was trying to maximize the dimension of the null-space and only partially switched back. $\endgroup$
    – Aaron Meyerowitz
    Commented Dec 28, 2017 at 23:07
  • 1
    $\begingroup$ More generally, the eigenvalues of an irreducible Hessenberg matrix are geometrically simple (the argument is that described by Federico). This statement, applied to Hermitian matrix tells you that if $H$ is tridiagonal and irreducible (the $h_{ij}\ne0$ for $|j-i|=1$), then it has simple eigenvalues. Therefore, no matter what is the diagonal $D$, the rank of $H+D$ is always $\ge n-1$. $\endgroup$
    – Denis Serre
    Commented Dec 29, 2017 at 7:13
  • $\begingroup$ Regarding your last paragraph: finding $\lambda$ such that $\det (A-\lambda B) = 0$ is known as generalized eigenvalue problem, and the theory holds together quite well. The only new element is 'eigenvalues (and Jordan blocks) at $\infty$', which appear when $B$ is singular. There is a canonical form (under transformations $P(A-\lambda B)Q$, with $P,Q$ square invertible) which extends Jordan's. The case in which $\det(A-\lambda B)$ is zero identically is a bit more complicated, but again there is a canonical form, and the ranks and nullspaces can be identified from it. $\endgroup$
    – Federico Poloni
    Commented Dec 29, 2017 at 9:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .