行列の場合 $A \in \mathbb{R}^{N\times N}$ 行と列の両方が対角的に支配的です、それは満足しますか $(x^{2p-1})^T A x \geq 0, p \geq 1$？
行列の場合 $A = \{a_{i,j}\} \in \mathbb{R}^{N\times N}$ 行と列の両方が対角的に優勢であり、非負の対角エントリがあります。
- $a_{i,i} \geq 0$、 $\forall i = 1, \cdots, N$
- $a_{i,i} \geq \sum_{j = 1,\cdots, N; j\neq i} |a_{i,j}|$、 $\forall i = 1, \cdots, N$
- $a_{i,i} \geq \sum_{l = 1,\cdots, N; l\neq i} |a_{l, i}|$、 $\forall i = 1, \cdots, N$
それは満足しますか
- $x^T A x \geq 0, \forall \mathbf{x} \in \mathbb{R}^N$？真の編集、回答者
Minus One-Twelfth - $(\mathbf{x}^{(2p-1)})^T A \mathbf{x} \geq 0$、 どこ $p \geq 2$ インタージャーですか？
編集：$\mathbf x^{2p-1} = [x_1^{2p-1}, x_2^{2p-1}, \cdots, x_N^{2p-1}]^T$。
どうもありがとうございました！
私はmatlabこれを確認するために短いコードを書きました：
N = 5;
for i = 1:100000
A = 2*rand(N, N) - 1; % random value in [-1, 1]
rowsum = sum(abs(A), 2) - abs(diag(A));
columnsum = sum(abs(A), 1)' - abs(diag(A));
v = max(rowsum, columnsum);
A = A - diag(diag(A)) + diag(v); % column/row diagonally dominant
xv = 4*rand(N, 100000) - 2; % random vector in [-2, 2]
p = 1;
minvalue = min(dot((xv.^(2*p-1)), A * xv))
if minvalue < 0
fprintf('wrong!\n');
pause;
end
end
回答
答えはイエスです。
しましょう $B = \frac{1}{2}\left(A+A^T\right)$。次に$B$は対称行列です。また、すべてのために$i=1,\ldots,N$、 我々は持っています
$$\begin{align*}\sum\limits_{j\ne i}\left|b_{i,j}\right| &= \frac{1}{2}\sum\limits_{j\ne i}\left|a_{i,j}+a_{j,i}\right| \\ &\le \frac{1}{2}\left(\sum\limits_{j\ne i}\left|a_{i,j}\right| + \sum\limits_{j\ne i}\left|a_{j,i}\right|\right) \quad (\text{triangle inequality}) \\ &\le \frac{1}{2}\left(a_{i,i}+ a_{i,i}\right) \\ &= a_{i,i} \\ &= b_{i,i}. \end{align*} $$
したがって、 $B$は、対角的に優勢で、非負の対角要素を持つ実対称行列です。これは、$B$ 正の半確定なので、 $\mathbf{x}^T B\mathbf{x}\ge 0$ すべてのために $\mathbf{x}\in \Bbb{R}^N$。以来$\mathbf{x}^T B\mathbf{x} = \mathbf{x}^T A\mathbf{x}$、 我々は持っています $\mathbf{x}^T A\mathbf{x}\ge 0$ すべてのために $\mathbf{x}\in \Bbb{R}^N$。
問題の不等式は、以下の定理の最初の部分の直接の結果です。 $y=x^{2p-1}$。便宜上、行列と呼びます$A\in M_n(\mathbb R)$ 二重支配的な、それは非負対角を持っており、それは両方の各行と各列の斜めに支配的であり、そして我々はそれが呼び出す場合完全に支配的な場合$a_{kk}=\sum_{j\ne k}|a_{kj}|=\sum_{i\ne k}|a_{ik}|$ それぞれについて $k$。
定理。しましょう$A\in M_n(\mathbb R)$ 二重に支配的であり、 $x,y\in\mathbb R^n$、その後 $y^TAx\ge0$ いつ
- $|y_{\sigma(1)}|\ge\cdots\ge|y_{\sigma(n)}|$ そして $|x_{\sigma(1)}|\ge\cdots\ge|x_{\sigma(n)}|$ いくつかの順列のために $\sigma$、および
- $y_ix_i\ge0$ それぞれについて $i$。
さらに、 $A$ は完全に優勢であり、その非対角エントリはすべて非正です。 $y^TAx$ の場合も非負です $y_{\rho(1)}\ge\cdots\ge y_{\rho(n)}$ そして $x_{\rho(1)}\ge\cdots\ge x_{\rho(n)}$ いくつかの順列のために $\rho$。
証明。二重に優勢な場合$A$、有向グラフを定義する場合があります $G$ 自己ループのないように、すべてのそれ$i\ne j$、ノード $i$ ノードに接続されています $j$ 場合に限り $a_{ij}\ne0$。グラフの構造に注意してください$G$ の非対角エントリにのみ依存します $A$。の対角エントリは使用しません$A$ たとえ自己ループを構築する場合でも $a_{ii}\ne0$。
すべての優対角行列 $A$ 次の形式で書くことができます $D+\sum_{k=1}^mA_k$、 どこ $D$ は非負の対角行列であり、それぞれ $A_k$は、グラフがサイクルまたは非巡回パスのいずれかである優対角行列です。これは再帰的に実行できます。
まず、 $G$ いくつかのサイクルが含まれています $C$。一般性を失うことなく、$C$ です $1\to2\to\cdots\to L\to1$。しましょう$m=\min\{|a_{12}|,\,|a_{23}|,\ldots,|a_{L-1,L}|,\,|a_{L1}|\}$ そして $B$ ゼロ以外の非対角エントリのみがである行列である $b_{ij}=m\operatorname{sign}(a_{ij})$ エッジごとに $i\to j$ に $C$ ゼロ以外の対角要素は $b_{11}=\cdots=b_{LL}=m$。次に$B$ 完全に優勢であり、すべての非ゼロの非対角エントリ $B$ の対応するものと同じ兆候があります $A$。したがって、$A-B$ は二重に優勢ですが、ゼロ以外のエントリは $A$。だから、私たちが置き換える場合$A$ 沿って $A-B$ このように続けると、最終的には削減されます $A$ グラフが非巡回である優対角行列に。
今、仮定します $G$非巡回です。パスを検討してください$P$ に $G$最大長の。一般性を失うことなく、$P$ です $1\to2\to\cdots\to L$。次に、私たちは持っている必要があります$a_{Lj}=0$ すべてのために $j<L$ （さもないと $L\to j\to\cdots\to L$ サイクルです）、 $a_{Lj}=0$ すべてのために $j>L$ （さもないと $1\to \cdots\to L\to j$ より長いパスです $P$）および $a_{i1}=0$ すべてのために $i>1$ （さもないと $i\to1\to\cdots\to L$ より長いパスです $P$）。言い換えると、最初の列のすべての非対角エントリと$L$-の3行目 $A$ ゼロです。
からサイクルを削除する方法と同様です $A$、 $m=\min\{|a_{12}|,\,|a_{23}|,\ldots,|a_{L-1,L}|\}$ そして $B$ ゼロ以外の非対角エントリのみがである行列である $b_{ij}=m\operatorname{sign}(a_{ij})$ エッジごとに $i\to j$ に $P$ ゼロ以外の対角要素は $b_{11}=\cdots=b_{LL}=m$。次に$B$建設によって二重に支配的です。のすべての非ゼロの非対角エントリは$B$ の対応するものと同じ記号を持っています $A$、および最初の列のすべての非対角エントリと $L$-の3行目 $A$ ゼロです、 $A-B$また、二重に支配的です。繰り返しますが、$A-B$ ゼロ以外のエントリが $A$、交換する場合 $A$ 沿って $A-B$ このように続けると、最終的には削減されます $A$グラフが空の優対角行列に。したがって、$A$ は非負の対角行列になり、再帰は停止します。
これは、 $A$ 問題のは等しい $D+\sum_{k=1}^mA_k$、 どこ $D$ は非負の対角行列であり、それぞれ $A_k$ インデックスの再作成までは、 $$ A_k=m\pmatrix{1&s_1\\ &1&s_2\\ &&\ddots&\ddots\\ &&&\ddots&s_{L-1}\\ s_L&&&&1}\oplus0,\tag{3} $$ どこ $m>0,\,s_1,s_2,\ldots,s_{L-1}=\pm1$ そして $s_L\in\{0,1,-1\}$ （のグラフ $A_k$ 次の場合はサイクルです $s_L=\pm1$ または非循環パスの場合 $s_L=0$）。このインデックスの再作成により、次のことがわかります。\begin{aligned} \frac{1}{m}y^TA_kx &=\sum_{i=1}^Ly_ix_i+\sum_{\text{cyc}}s_iy_ix_{i+1}\\ &\ge\sum_{i=1}^Ly_ix_i-\sum_{\text{cyc}}|y_i||x_{i+1}|\\ &\ge\sum_{i=1}^Ly_ix_i-\sum_{\text{cyc}}|y_i||x_i|\quad\text{(by rearrangement ineq. and condition 1)}\\ &=0\quad\text{(by condition 2)}. \end{aligned} 以来 $y^TDx=\sum_id_{ii}y_ix_i$ また、（条件2により）非負であることがわかります。 $y^TAx\ge0$。これで定理の最初の部分は終わりです。
2番目の部分については、 $A$ は完全に優勢であり、その非対角エントリはすべて非正であり、分解では $A=D+\sum_{k=1}^mA_k$ 上記、それぞれのグラフ $A_k$ サイクルでなければなりません、 $s_1=s_2=\cdots=s_L=-1$ に $(3)$ そして $D$ゼロでなければなりません。確かに、すべてのサイクルを削除した後、$X$まだ完全に支配的です。グラフが空でない場合、（必要に応じてインデックスを再作成することにより）非循環パスが含まれていると見なすことができます。$1\to2\to\cdots\to L$ 最大長であり、前の引数は、最初の列のすべての非対角エントリと $L$-の3行目 $X$ゼロです。したがって、$X$完全に支配的ではなく、矛盾しています。したがって、のグラフ$X$すべてのサイクルが削除されると、は空になります。しかし、$X$は完全に支配的であり、グラフが空の場合はゼロでなければなりません。したがって、$D=0$ そしてそれぞれ $A_k$サイクルを表します。再配置の不等式から、$\frac{1}{m}y^TA_kx=\sum_{i=1}^Ly_ix_i-\sum_{\text{cyc}}y_ix_{i+1}\ge0$ いつ $A_k$ の形を取ります $(3)$。したがって、$y^TAx\ge0$。