The matrix $M=I+A\in \mathbb{R}^{n\times n}$, where $I$ is the identity and $A=-A^T$ is skew-symmetric satisfies $$ Mx\cdot x = \|x\|^2 \quad\text{for all }x\in\mathbb{R}^n. $$ Therefore, $M=LU$ has an unique $LU$-factorization. Numerical experiments with Matlab suggest that there holds the following estimate $$ \|L\| + \|U\|\leq C(1+\|A\|^2), $$ where $\|\cdot\|$ is the spectral norm and the real constant $C>0$ does not depend on the dimension $n\in\mathbb{N}$. Does anyone know of a proof for that?
$\begingroup$
$\endgroup$
9
-
$\begingroup$ I observed $C\leq 1$. $\endgroup$– WinfriedCommented Jul 14, 2014 at 12:59
-
$\begingroup$ @NathanielJohnston You are right, I deleted my remarks. $\endgroup$– Piotr MigdalCommented Jul 14, 2014 at 13:17
-
$\begingroup$ $C \leq 1$ isn't possible, even for $2\times 2$ matrices. Let $a = 0.379$ and consider $A = \begin{bmatrix}0 & a\\ -a & 0\end{bmatrix}$. Then $\|L\| + \|U\| = 2.4984$ but $1 + \|A\|^2 = 1.1436$. In fact, a direct calculation shows that for $2 \times 2$ matrices the smallest possible $C$ is approximately $2.1846$. $\endgroup$– Nathaniel JohnstonCommented Jul 14, 2014 at 13:42
-
$\begingroup$ Are you assuming that $L$ has ones on the diagonal? The claim will be false without some kind of normalisation like this, but that particular choice of normalisation feels quite arbitrary in this context. It would seem more natural to set things up so that if the chosen factorisation of $I+A$ is $LU$, then the chosen factorisation of $I-A$ is $U^TL^T$. $\endgroup$– Neil StricklandCommented Jul 14, 2014 at 20:35
-
2$\begingroup$ For what it's worth, it seems like the smallest possible $C$ in the $3\times 3$ case is also approximately $2.1846$, based on parametrizing all such $3\times 3$ matrices and constructing a mesh over them. So we might (naively) guess that this $C$ works in all dimensions. $\endgroup$– Nathaniel JohnstonCommented Jul 15, 2014 at 15:36
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
EDIT 1. For $n=2$, the smallest $C$ is as follows. In all calculations we use the "Groebner" library of Maple. Let $C_n$ be the smallest $C$ (if there exists) in dimension $n$.
Let $a\approx 0.3787$ be the number satisfying $4a^8+27a^6+34a^4-117a^2+16=0$. Note that $a$ can be calculated by radicals. Then
$C_2=\dfrac{\sqrt{2a^2+4+2a\sqrt{a^2+4}}+\sqrt{2a^4+6a^2+4+2a(a^2+1)\sqrt{a^2+4}}}{2(a^2+1)}$.
Moreover $C_2\approx 2.184596$ is a root of the following polynomial: $20736x^8-122832x^6+126913x^4-62224x^2+1024$. Note that $C_2$ can be calculated by radicals.
EDIT 2. When $n=3$, let $A=\begin{pmatrix}0&-a_3&a_2\\a_3&0&-a_1\\-a_2&a_1&0\end{pmatrix}$ ; there are $2$ cases.
Case 1. $a_1a_2a_3\geq 0$. Then the bound for $C$ seems to be $C_2$.
Case 2. $a_1a_2a_3\leq 0$. Then the bound is $>C_2$ and $C_3>C_2$. Indeed, let $a_1=-0.25,a_2=0.29,a_3=0.029$ ; then $(||L||+||U||)/(1+{a_1}^2+{a_2}^2+{a_3}^2)\approx 2.18577$.
