Ранговая факторизация

В математике , если дана область $\mathbb {F}$, неотрицательные целые числа $m,n$и матрица $A\in \mathbb {F} ^{m\times n}$, ранговое разложение или ранговая факторизация A - это факторизация A формы A = CF , где $C\in \mathbb {F} ^{m\times r}$ и $F\in \mathbb {F} ^{r\times n}$, где $r=\operatorname {rank} A$ это ранг ​ $A$.

Существование

Любая конечномерная матрица имеет ранговое разложение: пусть ${\textstyle A}$ быть ${\textstyle m\times n}$ которой матрица, ранг столбца равен ${\textstyle r}$. Таким образом, существуют ${\textstyle r}$ линейно независимые столбцы в ${\textstyle A}$; эквивалентно размерность пространства столбцов , ${\textstyle A}$ является ${\textstyle r}$. Позволять ${\textstyle \mathbf {c} _{1},\mathbf {c} _{2},\ldots ,\mathbf {c} _{r}}$ быть любой основой для пространства столбцов ${\textstyle A}$ и поместите их как векторы-столбцы, чтобы сформировать ${\textstyle m\times r}$ матрица ${\textstyle C={\begin{bmatrix}\mathbf {c} _{1}&\mathbf {c} _{2}&\cdots &\mathbf {c} _{r}\end{bmatrix}}}$. Следовательно, каждый вектор-столбец ${\textstyle A}$ представляет собой линейную комбинацию столбцов ${\textstyle C}$. Если быть точным, если ${\textstyle A={\begin{bmatrix}\mathbf {a} _{1}&\mathbf {a} _{2}&\cdots &\mathbf {a} _{n}\end{bmatrix}}}$ это ${\textstyle m\times n}$ матрица с ${\textstyle \mathbf {a} _{j}}$ как ${\textstyle j}$-й столбец, тогда

$\mathbf {a} _{j}=f_{1j}\mathbf {c} _{1}+f_{2j}\mathbf {c} _{2}+\cdots +f_{rj}\mathbf {c} _{r},$

где ${\textstyle f_{ij}}$'s - скалярные коэффициенты ${\textstyle \mathbf {a} _{j}}$ с точки зрения основы ${\textstyle \mathbf {c} _{1},\mathbf {c} _{2},\ldots ,\mathbf {c} _{r}}$. Это означает, что ${\textstyle A=CF}$, где ${\textstyle f_{ij}}$ это ${\textstyle (i,j)}$-й элемент ${\textstyle F}$.

Неуникальность

Если ${\textstyle A=C_{1}F_{1}}$ представляет собой ранговую факторизацию, принимая ${\textstyle C_{2}=C_{1}R}$ и ${\textstyle F_{2}=R^{-1}F_{1}}$ дает еще одну факторизацию ранга для любой обратимой матрицы ${\textstyle R}$ совместимых размеров.

И наоборот, если ${\textstyle A=F_{1}G_{1}=F_{2}G_{2}}$ представляют собой двухранговые факторизации ${\textstyle A}$, то существует обратимая матрица ${\textstyle R}$ такой, что ${\textstyle F_{1}=F_{2}R}$ и ${\textstyle G_{1}=R^{-1}G_{2}}$.

Строительство

Ранговая факторизация из сокращенных форм эшелонов строк

На практике мы можем построить одну конкретную ранговую факторизацию следующим образом: мы можем вычислить ${\textstyle B}$, эшелона строк сокращенная форма ${\textstyle A}$. Затем ${\textstyle C}$ получается удалением из ${\textstyle A}$ все столбцы, не являющиеся сводными (которые можно определить, выполнив поиск столбцов в ${\textstyle B}$ которые не содержат опорной точки), и ${\textstyle F}$ получается путем исключения всех нулевых строк ${\textstyle B}$.

Примечание. Для полного ранга квадратной матрицы (т. е. когда ${\textstyle n=m=r}$), эта процедура даст тривиальный результат ${\textstyle C=A}$ и ${\textstyle F=B=I_{n}}$ ( ${\textstyle n\times n}$ единичная матрица ).

Пример

Рассмотрим матрицу

$A={\begin{bmatrix}1&3&1&4\\2&7&3&9\\1&5&3&1\\1&2&0&8\end{bmatrix}}\sim {\begin{bmatrix}1&0&-2&0\\0&1&1&0\\0&0&0&1\\0&0&0&0\end{bmatrix}}=B{\text{.}}$

${\textstyle B}$ имеет форму сокращенного эшелона.

Затем ${\textstyle C}$ получается удалением третьего столбца ${\textstyle A}$, единственный, который не является сводным столбцом, и ${\textstyle F}$ избавившись от последней строки нулей из ${\textstyle B}$, так

$C={\begin{bmatrix}1&3&4\\2&7&9\\1&5&1\\1&2&8\end{bmatrix}}{\text{,}}\qquad F={\begin{bmatrix}1&0&-2&0\\0&1&1&0\\0&0&0&1\end{bmatrix}}{\text{.}}$

Это несложно проверить

$A={\begin{bmatrix}1&3&1&4\\2&7&3&9\\1&5&3&1\\1&2&0&8\end{bmatrix}}={\begin{bmatrix}1&3&4\\2&7&9\\1&5&1\\1&2&8\end{bmatrix}}{\begin{bmatrix}1&0&-2&0\\0&1&1&0\\0&0&0&1\end{bmatrix}}=CF{\text{.}}$

Доказательство

Позволять ${\textstyle P}$ быть ${\textstyle n\times n}$ матрица перестановок такая, что ${\textstyle AP=(C,D)}$ в блочно-секционированной форме, где столбцы ${\textstyle C}$ являются ${\textstyle r}$ поворотные колонны ${\textstyle A}$. Каждый столбец ${\textstyle D}$ представляет собой линейную комбинацию столбцов ${\textstyle C}$, значит, есть матрица ${\textstyle G}$ такой, что ${\textstyle D=CG}$, где столбцы ${\textstyle G}$ содержат коэффициенты каждой из этих линейных комбинаций. Так ${\textstyle AP=(C,CG)=C(I_{r},G)}$, ${\textstyle I_{r}}$ быть ${\textstyle r\times r}$ идентификационная матрица. Мы сейчас покажем, что ${\textstyle (I_{r},G)=FP}$.

Преобразование ${\textstyle A}$ в уменьшенную форму эшелона строк ${\textstyle B}$ представляет собой умножение слева на матрицу ${\textstyle E}$ которое является произведением элементарных матриц , поэтому ${\textstyle EAP=BP=EC(I_{r},G)}$, где ${\textstyle EC={\begin{pmatrix}I_{r}\\0\end{pmatrix}}}$. Затем мы можем написать ${\textstyle BP={\begin{pmatrix}I_{r}&G\\0&0\end{pmatrix}}}$, что позволяет нам идентифицировать ${\textstyle (I_{r},G)=FP}$, то есть ненулевое ${\textstyle r}$ строк уменьшенной ступенчатой ​​формы, с той же перестановкой на столбцах, что и для ${\textstyle A}$. Таким образом, мы имеем ${\textstyle AP=CFP}$, и поскольку ${\textstyle P}$ обратимо, это означает ${\textstyle A=CF}$, и доказательство завершено.

Разложение по сингулярным значениям

Если $\mathbb {F} \in \{\mathbb {R} ,\mathbb {C} \},$ то можно также построить факторизацию полного ранга ${\textstyle A}$ через разложение по сингулярным значениям

$A=U\Sigma V^{*}={\begin{bmatrix}U_{1}&U_{2}\end{bmatrix}}{\begin{bmatrix}\Sigma _{r}&0\\0&0\end{bmatrix}}{\begin{bmatrix}V_{1}^{*}\\V_{2}^{*}\end{bmatrix}}=U_{1}\left(\Sigma _{r}V_{1}^{*}\right).$

С ${\textstyle U_{1}}$ представляет собой матрицу полного столбца ранга и ${\textstyle \Sigma _{r}V_{1}^{*}}$ является матрицей полного ранга, мы можем взять ${\textstyle C=U_{1}}$ и ${\textstyle F=\Sigma _{r}V_{1}^{*}}$.

Последствия

ранг(А) = ранг(А ^Т )

См. также: Доказательства того, что ранг столбца = ранг строки.

Непосредственным следствием ранговой факторизации является то, что ранг ${\textstyle A}$ равен рангу его транспонирования ${\textstyle A^{\textsf {T}}}$. Поскольку столбцы ${\textstyle A}$ это ряды ${\textstyle A^{\textsf {T}}}$, столбца ранг ${\textstyle A}$ равен рангу строки .

Доказательство. Чтобы понять, почему это так, давайте сначала определим ранг как средний ранг столбца. С ${\textstyle A=CF}$, отсюда следует, что ${\textstyle A^{\textsf {T}}=F^{\textsf {T}}C^{\textsf {T}}}$. Из определения умножения матриц это означает, что каждый столбец ${\textstyle A^{\textsf {T}}}$ представляет собой линейную комбинацию столбцов ${\textstyle F^{\textsf {T}}}$. Следовательно, пространство столбцов ${\textstyle A^{\textsf {T}}}$ содержится в пространстве столбца ${\textstyle F^{\textsf {T}}}$ и, следовательно, ${\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq \operatorname {rank} \left(F^{\textsf {T}}\right)}$.

Сейчас, ${\textstyle F^{\textsf {T}}}$ является ${\textstyle n\times r}$, так что есть ${\textstyle r}$ столбцы в ${\textstyle F^{\textsf {T}}}$ и, следовательно, ${\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq r=\operatorname {rank} \left(A\right)}$. Это доказывает, что ${\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq \operatorname {rank} \left(A\right)}$.

Теперь примените результат к ${\textstyle A^{\textsf {T}}}$ чтобы получить обратное неравенство: поскольку ${\textstyle \left(A^{\textsf {T}}\right)^{\textsf {T}}=A}$, мы можем написать ${\textstyle \operatorname {rank} \left(A\right)=\operatorname {rank} \left(\left(A^{\textsf {T}}\right)^{\textsf {T}}\right)\leq \operatorname {rank} \left(A^{\textsf {T}}\right)}$. Это доказывает ${\textstyle \operatorname {rank} \left(A\right)\leq \operatorname {rank} \left(A^{\textsf {T}}\right)}$.

Таким образом, мы доказали ${\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq \operatorname {rank} \left(A\right)}$ и ${\textstyle \operatorname {rank} \left(A\right)\leq \operatorname {rank} \left(A^{\textsf {T}}\right)}$, так ${\textstyle \operatorname {rank} \left(A\right)=\operatorname {rank} \left(A^{\textsf {T}}\right)}$.

Ссылки

• Банерджи, Судипто; Рой, Аниндья (2014), Линейная алгебра и матричный анализ для статистики , Тексты по статистическим наукам (1-е изд.), Чепмен и Холл / CRC, ISBN  978-1420095388
• Лэй, Дэвид К. (2005), Линейная алгебра и ее приложения (3-е изд.), Аддисон Уэсли, ISBN  978-0-201-70970-4
• Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996), Матричные вычисления , Исследования Джонса Хопкинса в области математических наук (3-е изд.), Издательство Университета Джонса Хопкинса, ISBN  978-0-8018-5414-9
• Стюарт, Гилберт В. (1998), Матричные алгоритмы. I. Базовые декомпозиции , SIAM, ISBN  978-0-89871-414-2
• Пизяк Р.; Оделл, Польша (1 июня 1999 г.). «Полноранговая факторизация матриц». Журнал «Математика» . 72 (3): 193. дои : 10.2307/2690882 . JSTOR   2690882 .