ブログ

線形代数の枠組みで$n$次正方行列の行列式(determinant)を取り扱うにあたっては置換(permutation)という概念を抑えておく必要があります。当記事では置換(permutation)と行列式(determinant)について取りまとめを行いました。
作成にあたっては「チャート式シリーズ 大学教養 線形代数」の第$4$章「行列式」を主に参考にしました。

・数学まとめ
https://www.hello-statisticians.com/math_basic

チャート式シリーズ 大学教養 線形代数 (チャート式・シリーズ)

3,080円(05/09 21:06時点)

Amazon

置換と行列式

互換の符号

互換$\sigma=(i \quad j)$の符号は常に$\mathrm{sgn}(\sigma)=-1$であり、全ての互換は奇置換である。

置換を用いた行列式の定義

$n$次正方行列$A=(a_{ij})$の行列式$\det{(A)}$は$1, \cdots , n$の$n$個の文字の置換$\sigma$を用いて下記のように定義される。
$$
\large
\begin{align}
\det{(A)} = \sum_{\sigma} \mathrm{sgn}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{n \sigma(n)}
\end{align}
$$

上記を元に、$2$次正方行列$\displaystyle A = \left( \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right)$の行列式$\det{(A)}$は、置換$\sigma$が$\displaystyle \sigma_{1} = \left[ \begin{array}{cc} 1 & 2 \\ 1 & 2 \end{array} \right]$と$\displaystyle \sigma_{2} = \left[ \begin{array}{cc} 1 & 2 \\ 2 & 1 \end{array} \right]$の$2$種類取り得ることから下記のような式で計算することができる。
$$
\large
\begin{align}
\det{(A)} &= \sum_{\sigma} \mathrm{sgn}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \\
&= \mathrm{sgn}(\sigma_{1}) a_{1 \sigma_{1}(1)} a_{2 \sigma_{1}(2)} + \mathrm{sgn}(\sigma_{2}) a_{1 \sigma_{2}(1)} a_{2 \sigma_{2}(2)} \\
&= a_{11} a_{22} \, – \, a_{12} a_{21}
\end{align}
$$

上記の式変形の理解にあたっては$\sigma_{1}$は単位置換であるから$\mathrm{sgn}(\sigma_{1})=1$、$\sigma_{2}$は互換であるから$\mathrm{sgn}(\sigma_{2})=-1$であることを注意しておくと良い。

例題の確認

以下、「チャート式シリーズ 大学教養 線形代数」の例題の確認を行う。

基本例題$058$

・$[1]$
$$
\large
\begin{align}
A = \left( \begin{array}{cc} 1 & 2 \\ 3 & 4 \end{array} \right)
\end{align}
$$

$\det{(A)}$は下記のように計算できる。
$$
\large
\begin{align}
\det{(A)} &= \left| \begin{array}{cc} 1 & 2 \\ 3 & 4 \end{array} \right| \\
&= 1 \cdot 4 \, – \, 2 \cdot 3 \\
&= 4 \, – \, 6 = -2
\end{align}
$$

・$[2]$
$$
\large
\begin{align}
A = \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)
\end{align}
$$

$\det{(A)}$は下記のように計算できる。
$$
\large
\begin{align}
\det{(A)} &= \left| \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right| \\
&= 0 \cdot 0 \, – \, 1 \cdot 1 \\
&= 0 \, – \, 1 = -1
\end{align}
$$

基本例題$062$

・$[1]$
$i$列目が$\mathbf{a}_{i}$である$n$次正方行列$A$は下記のように表される。
$$
\large
\begin{align} A &= \left( \begin{array}{ccc} \mathbf{a}_{1} & \cdots & \mathbf{a}_{n} \end{array} \right) \\
\mathbf{a}_{i} &= \left( \begin{array}{c} a_{1i} \\ \vdots \\ a_{ni} \end{array} \right) = \left( \begin{array}{c} 0 \\ \vdots \\ 0 \end{array} \right)
\end{align}
$$

また、行列$A$の行列式は行列式の定義より下記のように表される。
$$
\large
\begin{align}
\det{(A)} = \sum_{\sigma} \mathrm{sgn}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{n \sigma(n)}
\end{align}
$$

ここで任意の$\sigma$について$\sigma(k)=i$となる$k$が存在するが、$\mathbf{a}_{i}=\mathbf{0}$であるので$\sigma(k)=i$に対応する任意の$j$について$a_{j \sigma(k)} = a_{ji} = 0$である。よって行列式$\det{(A)}$は$\det{(A)}=0$となる。

ベクトル(vector)や行列(matrix)のノルム(norm)は類似度の計算など、様々な場面で応用される重要トピックです。当記事ではシンプルかつよく用いられるフロベニウスノルムに加えて行列のpノルム(p-norm)の定義や成立する式と、具体的な計算例の確認などを行いました。
作成にあたっては「Matrix Computations」のSection$\, 2.3$「Matrix Norms」の内容を主に参考にしました。

・数学まとめ
https://www.hello-statisticians.com/math_basic

Matrix Computations (Johns Hopkins Studies in the Mathematical Sciences Book 3) (English Edition)

Golub, Gene H, Van Loan, Charles F

11,163円(05/09 18:25時点)

発売日: 2012/12/27

Amazon

行列のノルムの定義

フロベニウスノルム

行列$A \in \mathbb{R}^{m \times n}$のフロベニウスノルム(Frobe­nius norm)を$||A||_{F}$とおくと、$||A||_{F}$は下記のような式で定義されます。
$$
\large
\begin{align}
||A||_{F} = \left( \sum_{i=1}^{m} \sum_{j=1}^{n} |a_{ij}|^{2} \right)^{\frac{1}
2}
\end{align}
$$

上記はベクトルの$2$-normのシンプルな拡張と見なすこともできます。一方で行列の$2$-normを含む$p$-normは上記とは異なる式で定義されるので注意が必要です。行列の$p$-normの定義については次項で問い扱います。

p-norm

行列$A \in \mathbb{R}^{m \times n}$の$p$-normを$||A||_{p}$とおくと、$||A||_{p}$は下記のような式で定義されます。
$$
\large
\begin{align}
||A||_{p} = \sup_{x \neq 0} \frac{||Ax||_{p}}{||x||_{p}} = \sup_{x \neq 0} \left| \middle| A \left( \frac{x}{||x||_{p}} \right) \middle| \right|_{p} = \max_{||x||_{p}=1} ||Ax||_{p} \quad (1)
\end{align}
$$

次節では$\displaystyle ||A||_{p} = \max_{||x||_{p}=1} ||Ax||_{p}$を元に$||A||_{p}$について成立する式を詳しく確認します。

行列のp-normについて成立する式

$1$-norm

行列$A \in \mathbb{R}^{m \times n}$の$1$-normである$||A||_{p}$は下記のように計算することができます。
$$
\large
\begin{align}
||A||_{1} = \max_{1 \leq j \leq n} \sum_{i=1}^{m} |a_{ij}| \quad (2)
\end{align}
$$

上記は「行列$A$の$1$-norm」は「$j$列の要素の絶対値の和が最大となる際に、$j$列の絶対値の和を計算することで得られる」と解釈できます。以下、$(2)$式を$(1)$式から導出します。まず、$(1)$式に$p=1$を代入することで下記のような式を得ることができます。
$$
\large
\begin{align}
||A||_{1} &= \max_{||x||_{1}=1} ||Ax||_{1} \quad (1)’ \\
&= \max_{||x||_{1}=1} \sum_{i=1}^{m} |a_{i1}x_{1} + \cdots a_{in}x_{n}| \\
& \leq \max_{||x||_{1}=1} \sum_{i=1}^{m} \sum_{j=1}^{n} |a_{ij}| |x_{j}|
\end{align}
$$

上記の式では$||x||_{1}=1$より$|x_1| + \cdots |x_n| = 1$であるので、$\displaystyle \sum_{i=1}^{m} |a_{ij}|$が最大となる$j$について$|x_j|=1$とすることで$||A||_{1}$は最大値を取ります。よって$(2)$式が成立することが確認できます。

$$
\large
\begin{align}
A = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \end{array} \right)
\end{align}
$$

たとえば上記のように$A$が定義されるとき、$|x_3| = 1$のとき$||A||_{1} = 9$が得られます。

$\infty$-norm

行列$A \in \mathbb{R}^{m \times n}$の$1$-normである$||A||_{\infty}$は下記のように計算することができます。
$$
\large
\begin{align}
||A||_{\infty} = \max_{1 \leq i \leq m} \sum_{j=1}^{n} |a_{ij}| \quad (3)
\end{align}
$$

以下、$(3)$式の導出を行います。$(1)$式と$\displaystyle ||x||_{\infty} = \max_{1 \leq i \leq m} |x_{i}|$に基づいて$||A||_{\infty}$は下記のような式で表すことができます。
$$
\large
\begin{align}
||A||_{\infty} &= \max_{||x||_{\infty}=1} ||Ax||_{\infty} \quad (1)^{”} \\
&= \max_{1 \leq i \leq m} | a_{i1}x_{1} + \cdots a_{in}x_{n} | \\
&= \max_{1 \leq i \leq m} \sum_{j=1}^{n} |a_{ij}| |x_{j}|
\end{align}
$$

ここで$||x||_{\infty}=1$より、$\displaystyle \sum_{j=1}^{n} |a_{ij}| |x_{j}|$は$x_1 = \cdots = x_{n} = 1$のとき最大値$\displaystyle \sum_{j=1}^{n} |a_{ij}|$を取ります。よって$(3)$式が成立することが確認できます。

$$
\large
\begin{align}
A = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \end{array} \right)
\end{align}
$$

たとえば上記のように$A$が定義されるとき、$|x_1| = |x_2| = |x_3| = 1$のとき$||A||_{\infty} = 15$が得られます。

$2$-normの計算式

行列$A \in \mathbb{R}^{m \times n}$について$A^{\mathrm{T}} A$の固有多項式を$p(\lambda)=\det{(A^{\mathrm{T}} A \, – \, \lambda I_{n})}$とおくとき$2$-normである$||A||_{2}$は下記のような式で計算することができます。
$$
\large
\begin{align}
||A||_{2} = \sqrt{\lambda_{\max} (A^{\mathrm{T}} A)} \quad (4)
\end{align}
$$

上記の$\lambda_{\max} (A^{\mathrm{T}} A)$は$A^{\mathrm{T}} A$の最大固有値に対応します。

$2$-normの計算式の導出

$A \in \mathbb{R}^{m \times n}$と$x \in \mathbb{R}^{n}$についてスカラー関数$g(x)$を下記のように定義します。
$$
\large
\begin{align}
g(x) = \frac{1}{2} \cdot \frac{||Ax||_{2}^{2}}{||x||_{2}^{2}} = \frac{1}{2} \cdot \frac{x^{\mathrm{T}} A^{\mathrm{T}} A x}{x^{\mathrm{T}} x}
\end{align}
$$

このとき、$g(x)$のベクトル微分$\displaystyle \nabla g(x) = \frac{\partial}{\partial x} g(x)$は下記のように計算できます。
$$
\large
\begin{align}
\nabla g(x) &= \frac{(x^{\mathrm{T}} x) A^{\mathrm{T}} A x \, – \, (x^{\mathrm{T}} A^{\mathrm{T}} A x)x}{(x^{\mathrm{T}} x)^{2}}
\end{align}
$$

ここで$||Az||_{2}=||A||_{2}$が成立するように$A \in \mathbb{R}^{m \times n}$について$z \in \mathbb{R}^{n}, \, ||z||_{2}=z^{\mathrm{T}} z=1$を仮定するとき、$\nabla g(z) = 0$が成立し、下記のような式を得ることができます。
$$
\large
\begin{align}
\nabla g(z) &= 0 \\
\frac{(z^{\mathrm{T}} z) A^{\mathrm{T}} A z \, – \, (x^{\mathrm{T}} A^{\mathrm{T}} Az)z}{(z^{\mathrm{T}} z)^{2}} &= 0 \\
1 \cdot A^{\mathrm{T}} A z \, – \, (z^{\mathrm{T}} A^{\mathrm{T}} A z)z &= 0 \\
A^{\mathrm{T}} A z &= (z^{\mathrm{T}} A^{\mathrm{T}} A z)z \\
A^{\mathrm{T}} A z &= \mu^{2} z
\end{align}
$$

上記の変形にあたって、$\mu^{2} = z^{\mathrm{T}} A^{\mathrm{T}} A z = ||Az||_{2}^{2}$のように$\mu$を定義しました。このとき$||Az||_{2}=||A||_{2}$を仮定したことより、$\mu^{2} = ||Az||_{2}^{2} = ||A||_{2}^{2}$が成立します。よって、$||A||_{2}$を得るにあたっては、$A^{\mathrm{T}} A z = \mu^{2} z$が成立する最大の$\mu$を求めれば良いことが確認できます。したがって固有方程式$\det{(A^{\mathrm{T}} A \, – \, \lambda I_{n})}$の最大固有値$\lambda(A^{\mathrm{T}} A)$を用いて$||A||_{2}$は下記のように表すことができます。
$$
\large
\begin{align} ||A||_{2} = \sqrt{\lambda_{\max} (A^{\mathrm{T}} A)}
\end{align}
$$

上記は前項の$(4)$式に一致します。

・ベクトル微分の式の導出について

直交行列とフロベニウスノルム

$Q \in \mathbb{R}^{m \times m}, \, Z \in \mathbb{R}^{n \times n}$が直交行列であるとき、$A \in \mathbb{R}^{m \times n}$のノルムについて下記の式が成立します。
$$
\large
\begin{align}
||QAZ||_{F} &= ||A||_{F} \quad (5) \\
||QAZ||_{2} &= ||A||_{2} \quad (6)
\end{align}
$$

$(5)$式の導出

まず、$A$の$j$列を$A(:,j)$とおくとき、$||QA||_{F}^{2}$は下記のように表すことができます。
$$
\large
\begin{align}
||QA||_{F}^{2} = \sum_{j=1}^{n} ||QA(:,j)||_{2}^{2}
\end{align}
$$

上記の式の$||QA(:,j)||_{2}^{2}$は行列ではなくベクトルの$2$-normであることに注意が必要です。また、ここで$Q$が直交行列であることより下記が成立します。
$$
\large
\begin{align}
||QA||_{F}^{2} &= \sum_{j=1}^{n} ||QA(:,j)||_{2}^{2} \\
&= \sum_{j=1}^{n} (QA(:,j))^{\mathrm{T}}(QA(:,j)) \\
&= \sum_{j=1}^{n} A(:,j)^{\mathrm{T}} Q^{\mathrm{T}} QA(:,j) \\
&= \sum_{j=1}^{n} A(:,j)^{\mathrm{T}} A(:,j) \\
&= \sum_{j=1}^{n} ||A(:,j)||_{2}^{2} \\
&= ||A||_{F}^{2}
\end{align}
$$

上記に基づいて、$||QAZ||_{F}^{2}$は下記のように式変形することができます。
$$
\large
\begin{align}
||QAZ||_{F}^{2} &= ||Q(AZ)||_{F}^{2} \\
&= ||AZ||_{F}^{2} \\
&= ||(AZ)^{\mathrm{T}}||_{F}^{2} \\
&= ||Z^{\mathrm{T}} A^{\mathrm{T}}||_{F}^{2} \\
&= ||A^{\mathrm{T}}||_{F}^{2} \\
&= ||A||_{F}^{2} \quad (5)’
\end{align}
$$

上記の導出にあたっては直交行列$Z$の転置である$Z^{\mathrm{T}}$も直交行列であることを用いました。直交行列の転置が直交行列であることは下記のように示すことができます。
$$
\large
\begin{align}
Z Z^{\mathrm{T}} &= I_{n} \\
(Z Z^{\mathrm{T}})^{\mathrm{T}} &= I_{n}^{\mathrm{T}} \\
(Z^{\mathrm{T}})^{\mathrm{T}} Z^{\mathrm{T}} &= I_{n}
\end{align}
$$

$(6)$式の導出

$||QA||_{2}$は$(1)$式に基づいて下記のように表すことができます。
$$
\large
\begin{align}
||QA||_{2} = \max_{||x||_{p}=1} ||QAx||_{2}
\end{align}
$$

ここで$Q$が直交行列、$QAx$がベクトルであることに基づいて$||QAx||_{2}^{2}$について下記のような変形を行うことができます。
$$
\large
\begin{align}
||QAx||_{2}^{2} &= (QAx)^{\mathrm{T}} (QAx) \\
&= x^{\mathrm{T}} A^{\mathrm{T}} Q^{\mathrm{T}} Q A x \\
&= x^{\mathrm{T}} A^{\mathrm{T}} A x \\
&= (Ax)^{\mathrm{T}} (Ax) \\
&= ||Ax||_{2}^{2}
\end{align}
$$

よって、$||QA||_{2}$は下記のように表すことができます。
$$
\large
\begin{align}
||QA||_{2} &= \max_{||x||_{p}=1} ||QAx||_{2} \\
&= \max_{||x||_{p}=1} ||Ax||_{2} \\
&= ||A||_{2}
\end{align}
$$

上記に基づいて、$||QAZ||_{2}^{2}$は$(5)$式の導出と同様に下記のように式変形することができます。
$$
\large
\begin{align}
||QAZ||_{2}^{2} &= ||Q(AZ)||_{2}^{2} \\
&= ||AZ||_{2}^{2} \\
&= ||(AZ)^{\mathrm{T}}||_{2}^{2} \\
&= ||Z^{\mathrm{T}} A^{\mathrm{T}}||_{2}^{2} \\
&= ||A^{\mathrm{T}}||_{2}^{2} \\
&= ||A||_{2}^{2} \quad (6)’
\end{align}
$$

ベクトル(vector)や行列(matrix)のノルム(norm)は類似度の計算など、様々な場面で応用される重要トピックです。当記事ではベクトルのpノルム(p-norm)の定義と成立する等式(equality)や不等式(inequality)、具体的な計算例の確認などを行いました。
作成にあたっては「Matrix Computations」のSection$\, 2.2$「Vector Norms」の内容を主に参考にしました。

・数学まとめ
https://www.hello-statisticians.com/math_basic

Matrix Computations (Johns Hopkins Studies in the Mathematical Sciences Book 3) (English Edition)

Golub, Gene H, Van Loan, Charles F

11,163円(05/09 18:25時点)

発売日: 2012/12/27

Amazon

p-normの定義

p-normの式定義

$n$次元ベクトル$x \in \mathbb{R}^{n}$のp-normを$||x||_{p}$とおくとき、$||x||_{p}$は下記のように定義されます。
$$
\large
\begin{align}
||x||_{p} &= (|x_1|^{p} + |x_2|^{p} + \cdots + |x_n|^{p})^{\frac{1}{p}} \quad (1) \\
&= \left( \sum_{i=1}^{n} |x_i|^{p} \right)^{\frac{1}{p}}
\end{align}
$$

上記に基づいて$1$-norm、$2$-norm、$\infty$-normはそれぞれ下記のように表すことができます。
$$
\large
\begin{align}
||x||_{1} &= |x_1| + |x_2| + \cdots + |x_n| = \sum_{i=1}^{n} |x_i| \\
||x||_{2} &= (|x_1|^{2} + |x_2|^{2} + \cdots + |x_n|^{2})^{\frac{1}{2}} = (x^{\mathrm{T}} x)^{\frac{1}{2}} \\
||x||_{\infty} &= \max_{1 \leq i \leq n} |x_{i}|
\end{align}
$$

$1$-norm、$2$-normについては$p$に$p=1, p=2$を代入することで式が成立することが確認できるので、以下$\infty$-normについて具体例を元に詳しく確認します。
$$
\large
\begin{align}
x = \left( \begin{array}{c} 1 \\ 2 \\ 0 \end{array} \right)
\end{align}
$$

たとえば上記のように$x \in \mathbb{R}^{3}$が表される場合、$||x||_{10}$は$(1)$式に$p=10$を代入することで下記のように計算できます。
$$
\large
\begin{align}
||x||_{10} &= (|1|^{10} + |2|^{10} + 0^{10})^{\frac{1}{10}} \quad (1)’ \\
&= ( 1 + 2^{10} )^{\frac{1}{10}} \\
& \simeq ( 2^{10} )^{\frac{1}{10}} = 2
\end{align}
$$

上記は$p=20, p=100$の場合も同様です。よって、$p \to \infty$のとき$\displaystyle ||x||_{p} \to \max_{1 \leq i \leq n} |x_{i}|$が成立するであろうことが推察できます。

Absolute and Relative Errors

統計や機械学習の分野では誤差を定義することが多いので、当項ではノルムを用いたAbsolute ErrorやRelative Errorの定義について確認を行います。ベクトル$x \in \mathbb{R}^{n}$をベクトル$\hat{x} \in \mathbb{R}^{n}$で近似するときのAbsolute Errorを$\epsilon_{\mathrm{abs}}$、Relative Errorを$\epsilon_{\mathrm{rel}}$とおくとき、$\epsilon_{\mathrm{abs}}$と$\epsilon_{\mathrm{rel}}$はそれぞれ下記のように定義されます。
$$
\large
\begin{align}
\epsilon_{\mathrm{abs}} &= ||\hat{x} \, – \, x||_{p} \\
\epsilon_{\mathrm{rel}} &= \frac{||\hat{x} \, – \, x||_{p}}{||x||_{p}}
\end{align}
$$

上記の計算にあたっては$p=2$が用いられることが一般的です。

p-normについて成立する式

Holder不等式

ベクトル$x \in \mathbb{R}^{n}, y \in \mathbb{R}^{n}$について下記のHolder不等式が成立します。
$$
\large
\begin{align}
|x^{\mathrm{T}} y| \leq ||x||_{p} ||y||_{p}
\end{align}
$$

上記は下記のように定義されるコーシー・シュワルツの不等式(Cauchy-Schwarz inequality)の一般形です。
$$
\large
\begin{align}
|x^{\mathrm{T}} y| \leq ||x||_{2} ||y||_{2}
\end{align}
$$

以下、具体例に基づいてーシー・シュワルツの不等式が成立することを確認します。
$$
\large
\begin{align}
x = \left( \begin{array}{c} 1 \\ 2 \\ 0 \end{array} \right), \quad x = \left( \begin{array}{c} 2 \\ 1 \\ 0 \end{array} \right)
\end{align}
$$

上記に対し、$x^{\mathrm{T}} y, \, ||x||_{2}, \, ||y||_{2}$はそれぞれ下記のように計算できます。
$$
\large
\begin{align}
x^{\mathrm{T}} y &= 1 \cdot 2 + 2 \cdot 1 + 0 \cdot 0 = 4 \\
||x||_{2} &= \sqrt{1^{2} + 2^{2} + 0^{2}} = \sqrt{5} \\
||y||_{2} &= \sqrt{2^{2} + 1^{2} + 0^{2}} = \sqrt{5}
\end{align}
$$

$4 \leq \sqrt{5} \cdot \sqrt{5}$であるので、$|x^{\mathrm{T}} y| \leq ||x||_{2} ||y||_{2}$が成立していることが確認できます。

直交行列について成立する式

$Q \in \mathbb{R}$を直交行列とするとき、$Q$とベクトル$x \in \mathbb{R}^{n}$について下記が成立します。
$$
\large
\begin{align}
||Qx||_{2}^{2} &= (Qx)^{\mathrm{T}} (Qx) \\
&= x^{\mathrm{T}} Q^{\mathrm{T}} Q x \\
&= x^{\mathrm{T}} x = ||x||_{2}^{2}
\end{align}
$$

上記の導出にあたっては直交行列の定義である$Q^{T} Q = Q^{-1} Q = I_{n}$を用いました。