Нахождение квадратного корня из матрицы Лапласа

11

Предположим следующую матрицу дается с транспонированной . Продукт дает , $A$

[\begin{array}{ccc} 0.500 & - 0.333 & - 0.167 \\ - 0.500 & 0.667 & - 0.167 \\ - 0.500 & - 0.333 & 0.833 \end{array}]

$\left[\begin{array}{ccc} 0.500 & -0.333 & -0.167\\ -0.500 & 0.667 & -0.167\\ -0.500 & -0.333 & 0.833\end{array}\right]$

A^{T}

$A^T$

A^{T} A = G

$A^TA=G$

[\begin{array}{ccc} 0.750 & - 0.334 & - 0.417 \\ - 0.334 & 0.667 & - 0.333 \\ - 0.417 & - 0.333 & 0.750 \end{array}]

$\left[\begin{array}{ccc}0.750 & -0.334 & -0.417\\ -0.334 & 0.667 & -0.333\\ -0.417 & -0.333 & 0.750\end{array}\right]$

где - матрица Лапласа . Заметим , что матрицы и имеют ранга 2, с нулевым собственным значением , соответствующим собственным вектором . $G$ $A$ $G$ $1_n=\left[\begin{array}{ccc}1 & 1 & 1\end{array}\right]^T$

Интересно, каким был бы способ получить если бы дали только ? Я попытался eigendecomposition , а затем установить , но получается другой результат. Я думаю, это связано с недостатком ранга. Может кто-нибудь объяснить это? Ясно, что приведенный выше пример для иллюстрации; Вы могли бы рассмотреть общее разложение Лапласа матрицы вышеупомянутой формы. $A$ $G$ $G=UEU^T$ $A'=UE^{1/2}$

Так как, например, разложение Холецкого можно использовать для нахождения , разложение на может дать много решений. Меня интересует решение, которое можно выразить как где - единичная матрица , , а - некоторый вектор, удовлетворяющий $G=LL^T$ $G$

A = (I - 1_{n} w^{T}),

$A=(I-1_nw^{T}),$

I

$I$

3 \times 3

$3\times 3$

1_{n} = [1 1 1]

$1_n=[1~ 1~ 1]$

w

$w$

w^{T} 1_{n} = 1

$w^T1_n=1$ , Если это упрощает ситуацию, вы можете предположить, что записи

неотрицательны.

w

$w$

linear-algebra matrix eigensystem Usero
источник

Я думаю, что комментарий, который вы добавили о представлении

, только частично полезен. Предполагается, что существует ровно одно собственное значение, равное нулю, но недетерминированность всегда присутствует, не так ли?

A

$A$

Вольфганг Бангерт

@WolfgangBangerth Я пытаюсь выяснить значение слова «недетерминированность». Если это

, то имеет место для приведенного выше примера, и я не уверен , если она может быть обобщена на

. Однако, за исключением

, я сомневаюсь, что решение будет существовать всегда.

d e t (A) = 0

$det(A)=0$

A = I - 1_{n} w^{T}

$A=I-1_nw^T$

n = 3

$n=3$

Usero

Нет, я имел в виду, что решение вашей проблемы не определено однозначно. Я указывал на тот факт, что то, имеет ли матрица нулевое собственное значение или нет, на самом деле не меняет того факта, что проблема квадратного корня не имеет единственного решения.

Вольфганг Бангерт

11

$G=A^TA$ $\lambda_0\leq\lambda_1\leq\ldots\leq \lambda_n$ $G\in\mathbb{R}^{n\times n}$ $\lambda_0 = 0$ $G$

A = [\begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array}],

$A=\left[\!\!\begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array} \!\!\right],$

A = [\begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array}] = [\begin{array}{cc} 0 & 0 \\ \sin θ & \cos θ \end{array}] [\begin{array}{cc} 0 & \sin θ \\ 0 & \cos θ \end{array}] = L L^{T} .

$A=\left[\!\begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array} \!\right] = \left[\!\begin{array}{cc} 0 & 0 \\ \sin\theta & \cos\theta \end{array} \!\right] \left[\!\begin{array}{cc} 0 & \sin\theta \\ 0 & \cos\theta \end{array} \!\right]=LL^T.$

$G$ $G$ $A$ $G\in\mathbb{R}^{4\times 4}$

G = [\begin{array}{cccc} 3 & - 1 & - 1 & - 1 \\ - 1 & 1 & 0 & 0 \\ - 1 & 0 & 1 & 0 \\ - 1 & 0 & 0 & 1 \end{array}]

$G=\left[\!\begin{array}{cccc} 3 & -1 & -1 & -1\\ -1 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ \end{array}\!\right]$

A

$A$

m

$m$

n

$n$

A

$A$

m \times n

$m\times n$

A_{e v} = {\begin{array}{lc} 1 & if e = (v, w) and v < w \\ - 1 & if e = (v, w) and v > w \\ 0 & otherwise, \end{array}

$A_{ev} = \left\{\begin{array}{lc} 1 & \textrm{if }e=(v,w)\textrm{ and }v<w \\ -1 & \textrm{if }e=(v,w)\textrm{ and }v>w \\ 0 & \textrm{otherwise}, \end{array} \right.$

e = (v, w)

$e=(v,w)$

v

$v$

w

$w$

G

$G$

A = [\begin{array}{cccc} 1 & - 1 & 0 & 0 \\ 1 & 0 & - 1 & 0 \\ 1 & 0 & 0 & - 1 \end{array}],

$A = \left[\!\begin{array}{cccc} 1 & -1 & 0 & 0\\ 1 & 0 & -1 & 0 \\ 1 & 0 & 0 & -1 \\ \end{array}\!\right],$

G = A^{T} A

$G=A^TA$

G

$G$

A

$A$

G

$G$

Обновить:

$N$ $M$ $G$ $G=N-M$

G = [\begin{array}{cccc} 3 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}] - [\begin{array}{cccc} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{array}] .

$G=\left[\!\begin{array}{cccc} 3 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array}\!\right] - \left[\!\begin{array}{cccc} 0 & 1 & 1 & 1\\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ \end{array}\!\right].$

G

$G$

A

$A$

A

$A$

A_{e v} = {\begin{array}{lc} 1 & if e = (v, w) and v < w \\ - 1 & if e = (v, w) and v > w \\ 0 & otherwise, \end{array} .

$A_{ev} = \left\{\begin{array}{lc} 1 & \textrm{if }e=(v,w)\textrm{ and }v<w \\ -1 & \textrm{if }e=(v,w)\textrm{ and }v>w \\ 0 & \textrm{otherwise}, \end{array} \right..$

e_{1}

$e_1$

v_{1}

$v_1$

v_{2}

$v_2$

A_{e_{1}, v_{1}}

$A_{e_1,v_1}$

v_{1}

$v_1$

v_{2}

$v_2$

v < w

$v<w$

A_{e v}

$A_{ev}$

A_{e_{1}, v_{1}} = 1

$A_{e_1,v_1} = 1$

A_{e_{1}, v_{2}} = - 1

$A_{e_1,v_2} = -1$

A

$A$

A = \begin{array}{ccccc} v_{1} & v_{2} & v_{3} & v_{4} \\ e_{1} & 1 & - 1 & 0 & 0 \\ e_{2} & 1 & 0 & - 1 & 0 \\ e_{3} & 1 & 0 & 0 & - 1 \end{array} .

$A = \begin{array}{c|cccc} & v_1 & v_2 & v_3 & v_4 \\ \hline e_1 & 1 & -1 & 0 & 0\\ e_2 & 1 & 0 & -1 & 0 \\ e_3 & 1 & 0 & 0 & -1 \\ \end{array}.$

$Gr$ $V$ $E$

w : V \times V \to R^{+},

$w: V\times V\rightarrow \mathbb{R}^+,$

u

$u$

v

$v$

w (u, v)

$w(u,v)$

u \in V

$u\in V$

u

$u$

d_{u} = \sum_{v \in V} w (u, v) .

$d_u = \sum_{v\in V}w(u,v).$

G r

$Gr$

A d (G r)

$Ad(Gr)$

n \times n

$n\times n$

V

$V$

w (u, v)

$w(u,v)$

D (G r)

$D(Gr)$

V

$V$

G

$G$

G = D (G r) - A d (G r) .

$G = D(Gr) - Ad(Gr).$

G = [\begin{array}{ccc} \frac{3}{4} & - \frac{1}{3} & - \frac{5}{12} \\ - \frac{1}{3} & \frac{2}{3} & - \frac{1}{3} \\ - \frac{5}{12} & - \frac{1}{3} & \frac{3}{4} \end{array}] .

$G=\left[\!\begin{array}{ccc} \tfrac{3}{4} & -\tfrac{1}{3} & -\tfrac{5}{12} \\ -\tfrac{1}{3} & \tfrac{2}{3} & -\tfrac{1}{3} \\ -\tfrac{5}{12} & -\tfrac{1}{3} & \tfrac{3}{4} \\ \end{array}\!\right].$

G

$G$

G = A^{T} A

$G=A^TA$

A

$A$

A = I - 1_{n} w^{T}

$A=I-1_nw^T$

w^{T} 1_{n} = 1

$w^T1_n=1$

A

$A$

A

$A$

A d (G r)

$Ad(Gr)$

G

$G$

G = [\begin{array}{ccc} \frac{5}{4} & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & \frac{11}{12} \end{array}] - [\begin{array}{ccc} \frac{1}{2} & \frac{1}{3} & \frac{5}{12} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{5}{12} & \frac{1}{3} & \frac{1}{6} \end{array}] = D (G r) - A d (G r) .

$G=\left[\!\begin{array}{ccc} \tfrac{5}{4} & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & \tfrac{11}{12} \\ \end{array}\!\right]-\left[\!\begin{array}{ccc} \tfrac{1}{2} & \tfrac{1}{3} & \tfrac{5}{12} \\ \tfrac{1}{3} & \tfrac{1}{3} & \tfrac{1}{3} \\ \tfrac{5}{12} & \tfrac{1}{3} & \tfrac{1}{6} \\ \end{array}\!\right] = D(Gr)-Ad(Gr).$

v_{1}

$v_1$

v_{2}

$v_2$

v_{3}

$v_3$

1 / 2

$1/2$

1 / 3

$1/3$

1 / 6

$1/6$

w

$w$

[\frac{1}{2}

$[\frac{1}{2}$

\frac{1}{3}

$\frac{1}{3}$

\frac{1}{6}]^{T}

$\frac{1}{6}]^T$

A

$A$

A = I - 1_{n} w^{T} = [\begin{array}{ccc} \frac{1}{2} & - \frac{1}{3} & - \frac{1}{6} \\ - \frac{1}{2} & \frac{2}{3} & - \frac{1}{6} \\ - \frac{1}{2} & - \frac{1}{3} & \frac{5}{6} \end{array}] .

$A = I-1_nw^T = \left[\!\begin{array}{ccc} \tfrac{1}{2} & -\tfrac{1}{3} & -\tfrac{1}{6} \\ -\tfrac{1}{2} & \tfrac{2}{3} & -\tfrac{1}{6} \\ -\tfrac{1}{2} & -\tfrac{1}{3} & \tfrac{5}{6} \\ \end{array}\!\right].$

$A$

Эндрю Винтерс
источник

A

$A$

G

$G$

O (n^{2})

$O(n^2)$

G

$G$

G

$G$

G

$G$

A

$A$

G

$G$

A

$A$

G

$G$

1

G

$G$

A = I - 1_{n} w^{T}

$A=I-1_nw^T$

G

$G$

G = A^{T} A = (I - 1_{n} w^{T})^{T} (I - 1_{n} w^{T})

$G=A^TA=(I-1_nw^T)^T(I-1_nw^T)$

9

$A$ $B$

B^{2} = A,

$B^2 = A,$

$C$

C^{H} C = A,

$C^H C = A,$

$C \mapsto Q C$ $Q$

Наконец, можно конструктивно определить уникальный квадратный корень матрицы эрмитовой положительной полуопределенной матрицы посредством ее разложения по собственным значениям, скажем,

A = U Λ U^{H},

$A = U \Lambda U^H,$

$U$ $\Lambda$ $A$

B = U \sqrt{Λ} U^{H} .

$B = U \sqrt{\Lambda} U^H.$

Джек Полсон
источник

A

$A$

6

G = A^{T} A .

$G = A^T A.$

G

$G$

G

$G$

G = L^{T} L

$G=L^TL$

A = L

$A=L$

A

$A$

G

$G$ и если вы хотите иметь один конкретный вопрос, вам нужно перефразировать вопрос таким образом, чтобы указать структурные свойства "ветви" квадратного корня, который вас интересует.

Я бы сказал, что эта ситуация не отличается от получения квадратного корня среди действительных чисел с использованием комплексных чисел: там, как правило, тоже есть два корня, и вы должны сказать, какой из них вы хотите сделать ответ уникальным.

Вольфганг Бангерт
источник

Ты определенно прав. Другим способом был бы подход спектральной декомпозиции, как я утверждаю выше. Я сделал правку, чтобы сделать решение уникальным. Надеюсь, это не усложнит ситуацию.

Usero

Всегда ли существует решение с приведенным выше ограничением? Возможно, это справедливо только в некоторых случаях, а не в целом.

Usero

На самом деле, Холецкий не работает в его случае, поскольку он (по существу) требует, чтобы матрица была эрмитовой положительно определенной.

Джек Полсон,

4

$LDL^{T}$ $\hat{D} = \sqrt{D}$ $G = L\hat{D}$

Willowbrook
источник

L D L^{T}

$LDL^T$

1

@JackPoulson Я пробую особую матрицу A в matlab и запускаю ldl, все работает. Нулевые собственные значения соответствуют нулям на диагонали D.

Уиллоубрук

2

L D L^{T}

$LDL^T$

P A P^{'} = L D L^{T}

$PAP'=LDL^T$

D

$D$

2 \times 2

$2 \times 2$

Нахождение квадратного корня из матрицы Лапласа

Ответы: