Se una matrice$A \in \mathbb{R}^{N\times N}$è sia riga che colonna diagonalmente dominante, soddisferà$(x^{2p-1})^T A x \geq 0, p \geq 1$?
Se una matrice$A = \{a_{i,j}\} \in \mathbb{R}^{N\times N}$è sia riga che colonna diagonalmente dominante con voci diagonali non negative, ad es
- $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$
soddisferà
- $x^T A x \geq 0, \forall \mathbf{x} \in \mathbb{R}^N$? EDIT Vero, ha risposto da
Minus One-Twelfth - $(\mathbf{x}^{(2p-1)})^T A \mathbf{x} \geq 0$, dove$p \geq 2$è un numero intero?
MODIFICA :$\mathbf x^{2p-1} = [x_1^{2p-1}, x_2^{2p-1}, \cdots, x_N^{2p-1}]^T$.
Grazie mille!
Ho scritto un matlabcodice breve per verificarlo:
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
Risposte
La risposta è si.
Permettere$B = \frac{1}{2}\left(A+A^T\right)$. Quindi$B$è una matrice simmetrica. Inoltre, per tutti$i=1,\ldots,N$, noi abbiamo
$$\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*} $$
Quindi$B$è una vera matrice simmetrica che è diagonalmente dominante e ha elementi diagonali non negativi. Ciò implica che$B$è semidefinito positivo, quindi$\mathbf{x}^T B\mathbf{x}\ge 0$per tutti$\mathbf{x}\in \Bbb{R}^N$. Da$\mathbf{x}^T B\mathbf{x} = \mathbf{x}^T A\mathbf{x}$, noi abbiamo$\mathbf{x}^T A\mathbf{x}\ge 0$per tutti$\mathbf{x}\in \Bbb{R}^N$.
La disuguaglianza in questione è una diretta conseguenza della prima parte del teorema sotto se poniamo$y=x^{2p-1}$. Per comodità chiamiamo matrice$A\in M_n(\mathbb R)$ doppiamente dominante se ha una diagonale non negativa ed è sia diagonalmente dominante su ogni riga che su ogni colonna, e lo chiamiamo perfettamente dominante se$a_{kk}=\sum_{j\ne k}|a_{kj}|=\sum_{i\ne k}|a_{ik}|$per ciascuno$k$.
Teorema. Permettere$A\in M_n(\mathbb R)$è doppiamente dominante e$x,y\in\mathbb R^n$, poi$y^TAx\ge0$quando
- $|y_{\sigma(1)}|\ge\cdots\ge|y_{\sigma(n)}|$e$|x_{\sigma(1)}|\ge\cdots\ge|x_{\sigma(n)}|$per qualche permutazione$\sigma$, e
- $y_ix_i\ge0$per ciascuno$i$.
Se, inoltre, quello$A$è perfettamente dominante e tutte le sue voci fuori diagonale sono quindi non positive$y^TAx$è anche non negativo quando$y_{\rho(1)}\ge\cdots\ge y_{\rho(n)}$e$x_{\rho(1)}\ge\cdots\ge x_{\rho(n)}$per qualche permutazione$\rho$.
Prova. Dato qualsiasi doppiamente dominante$A$, possiamo definire un grafo diretto$G$ senza self-loop tale che per ogni$i\ne j$, nodo$i$è connesso al nodo$j$se e solo se$a_{ij}\ne0$. Si noti che la struttura del grafico$G$dipende esclusivamente dalle voci fuori diagonale di$A$. Non usiamo le voci diagonali di$A$per costruire qualsiasi self-loop anche se$a_{ii}\ne0$.
Ogni matrice doppiamente dominante$A$può essere scritto sotto forma di$D+\sum_{k=1}^mA_k$, dove$D$è una matrice diagonale non negativa e ciascuna$A_k$è una matrice doppiamente dominante il cui grafico è un ciclo o un percorso aciclico. Questo può essere fatto in modo ricorsivo.
Innanzitutto, supponiamo$G$contiene un ciclo$C$. Senza perdita di generalità, supponiamo che$C$è$1\to2\to\cdots\to L\to1$. Permettere$m=\min\{|a_{12}|,\,|a_{23}|,\ldots,|a_{L-1,L}|,\,|a_{L1}|\}$e$B$essere la matrice le cui uniche voci fuori diagonale diverse da zero sono$b_{ij}=m\operatorname{sign}(a_{ij})$per ogni bordo$i\to j$in$C$e le cui uniche voci diagonali diverse da zero sono$b_{11}=\cdots=b_{LL}=m$. Quindi$B$è perfettamente dominante e ogni ingresso fuori diagonale diverso da zero di$B$ha lo stesso segno della sua controparte in$A$. Perciò$A-B$è doppiamente dominante, ma ha meno elementi diversi da zero di$A$. Quindi, se sostituiamo$A$di$A-B$e continuando in questo modo, alla fine ridurremo$A$ad una matrice doppiamente dominante il cui grafico è aciclico.
Supponiamo ora$G$è aciclico. Considera un percorso$P$in$G$di lunghezza massima. Senza perdita di generalità, supponiamo che$P$è$1\to2\to\cdots\to L$. Allora dobbiamo avere$a_{Lj}=0$per tutti$j<L$(altrimenti$L\to j\to\cdots\to L$è un ciclo),$a_{Lj}=0$per tutti$j>L$(altrimenti$1\to \cdots\to L\to j$è un percorso più lungo di$P$) e$a_{i1}=0$per tutti$i>1$(altrimenti$i\to1\to\cdots\to L$è un percorso più lungo di$P$). In altre parole, tutte le voci fuori diagonale sulla prima colonna e il$L$-esima fila di$A$sono zero.
Simile al modo in cui rimuoviamo i cicli da$A$, permettere$m=\min\{|a_{12}|,\,|a_{23}|,\ldots,|a_{L-1,L}|\}$e$B$essere la matrice le cui uniche voci fuori diagonale diverse da zero sono$b_{ij}=m\operatorname{sign}(a_{ij})$per ogni bordo$i\to j$in$P$e le cui uniche voci diagonali diverse da zero sono$b_{11}=\cdots=b_{LL}=m$. Quindi$B$è doppiamente dominante per costruzione. Poiché ogni voce fuori diagonale diversa da zero di$B$ha lo stesso segno della sua controparte in$A$, e tutte le voci fuori diagonale sulla prima colonna e sul$L$-esima fila di$A$sono zero,$A-B$è anche doppiamente dominante. Di nuovo, come$A-B$ha meno voci diverse da zero rispetto a$A$, se sostituiamo$A$di$A-B$e continuando in questo modo, alla fine ridurremo$A$a una matrice doppiamente dominante il cui grafico è vuoto. Quindi$A$diventa una matrice diagonale non negativa e la nostra ricorsione si ferma.
Ciò dimostra che il$A$in questione è uguale a$D+\sum_{k=1}^mA_k$, dove$D$è una matrice diagonale non negativa e ciascuna$A_k$fino alla reindicizzazione è sotto forma di$$ A_k=m\pmatrix{1&s_1\\ &1&s_2\\ &&\ddots&\ddots\\ &&&\ddots&s_{L-1}\\ s_L&&&&1}\oplus0,\tag{3} $$dove$m>0,\,s_1,s_2,\ldots,s_{L-1}=\pm1$e$s_L\in\{0,1,-1\}$(il grafico di$A_k$è un ciclo se$s_L=\pm1$o un percorso aciclico se$s_L=0$). Con questa reindicizzazione, lo vediamo\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}Da$y^TDx=\sum_id_{ii}y_ix_i$è anche non negativo (per la condizione 2), lo vediamo$y^TAx\ge0$. Questo conclude la prima parte del teorema.
Per la seconda parte, se$A$è perfettamente dominante e tutte le sue voci fuori diagonale sono non positive, quindi nella decomposizione$A=D+\sum_{k=1}^mA_k$sopra, il grafico di ciascuno$A_k$deve essere un ciclo,$s_1=s_2=\cdots=s_L=-1$in$(3)$e$D$deve essere zero. Infatti, dopo la rimozione di tutti i cicli, il ridotto$X$sarà ancora perfettamente dominante. Se il suo grafico non è vuoto, possiamo assumere (reindicizzando se necessario) che contenga un percorso aciclico$1\to2\to\cdots\to L$di lunghezza massima, e il nostro argomento precedente mostra che tutte le voci fuori diagonale sulla prima colonna e il$L$-esima fila di$X$sono zero. Quindi$X$non è perfettamente dominante, il che è una contraddizione. Così il grafico di$X$è vuoto quando tutti i cicli vengono rimossi. Tuttavia, come$X$è perfettamente dominante, deve essere zero quando il suo grafico è vuoto. Quindi$D=0$e ciascuno$A_k$rappresenta un ciclo Dalla disuguaglianza di riarrangiamento segue che$\frac{1}{m}y^TA_kx=\sum_{i=1}^Ly_ix_i-\sum_{\text{cyc}}y_ix_{i+1}\ge0$quando$A_k$assume la forma di$(3)$. Quindi$y^TAx\ge0$.