10
$\begingroup$

Let $A=(a_{ij})$ be an arbitrary $n \times n$ real symmetric matrix and $n\geq 2$. Let $\| \cdot \|$ denote the operator $2$-norm or equivalently the maximum absolute value of eigenvalues for symmetric matrices. Define

$$d(A) := \min_{D \text{ is diagonal}} \|A-D\|,$$

as the minimum distance of $A$ from diagonal matrices. What is the best constant $C$ that we can put in the following inequality?

$$d(A) \leq C \max_{i \neq j} |a_{ij}|.$$

The constant $C=n-1$ obviously works, by considering the distance of $A$ from its own diagonal, but it can be shown that it's not the smallest constant for $n>2$.

Improve this question
$\endgroup$
9
  • $\begingroup$ "But it can be shown that it's not the smallest constant." Please show us a smaller (the smallest) constant you know with proof. $\endgroup$
    – Mark L. Stone
    Commented Dec 24, 2019 at 13:38
  • 1
    $\begingroup$ @Stone I don't know a smaller constant, but there is a smallest constant (compactness argument) and I know that there is no matrix such that $d(A)/\max(|a_{ij}|)=n-1$. My proof for this fact is rather long and may be irrelevant to finding the best $C$, so I didn't write it here. $\endgroup$
    – Mostafa - Free Palestine
    Commented Dec 24, 2019 at 13:47
  • 1
    $\begingroup$ I don't think there's a smaller constant for $n=1, 2$. $\endgroup$
    – Christian Remling
    Commented Dec 24, 2019 at 18:06
  • 4
    $\begingroup$ @MarkL.Stone To set up the "triviality level", the obvious lower bound is $n/2$ (consider all ones outside the diagonal) and the obvious upper bound is $\sqrt{\frac{n(n-1)}2}$ (take the distance from the off-diagonal part to multiples of identity and take into account that the sum of the squares of the eigenvalues is $\le n(n-1)\max|a_{ij}|^2$). So, roughly speaking, we are between $\frac n2$ and $\frac n{\sqrt 2}$ and I do not know which bound is closer to the truth... $\endgroup$
    – fedja
    Commented Dec 25, 2019 at 13:07
  • 1
    $\begingroup$ @MTyson - Does your argument suggest that the closest diagonal matrix to A is the diagonal of A? If so, that's not true (when $n \geq 3$). For what it's worth, we solved the problem of finding the closest matrix D when A has rank 1 in arXiv:1601.06269, but the formula is quite nasty (see Theorem 1). $\endgroup$
    – Nathaniel Johnston
    Commented Dec 26, 2019 at 3:06

1 Answer 1

Reset to default
2
$\begingroup$

In my paper it is shown that $C=\frac{n}{2}$ is the best constant for the above problem. Also the similar problem for Hermitian matrices is also investigated and it is shown that for this more larger set of matrices, the best constant $C$, is equal to $\cot(\frac{\pi}{2n})$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @FedericoPoloni Please see the edited version of the question. $\endgroup$
    – Mostafa - Free Palestine
    Commented Oct 28, 2023 at 14:49

You must log in to answer this question.

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