114. 正則行列
【問題概要】
正則行列とは、逆行列が存在する正方行列のことである。逆行列は、ある行列Aに対して、Aと逆行列Bの積が単位行列となる行列Bのことである。
以下の条件をすべて満たす場合、行列Aは正則行列であると言える。
(1) 行列Aは正方行列である。
(2) 行列Aの行列式det(A)が0でない。
(3) 行列Aの逆行列が存在する。
(4) 正方行列 A が正則であるとは、逆行列 A^-1 が存在することをいう。
n次正則行列Aに対して、次の式を計算するアルゴリズムを考える。
det(A) = a11A11 + a12A12 + ... + a1n*An1
ただし、Aijは(i,j)要素を除くn-1次正則行列である。このアルゴリズムの時間計算量を求めよ。
【解説】
n 次正方行列 A の逆行列 A^-1 を求める方法として、以下の手順が挙げられる。
行列 A と単位行列 E の拡大係数行列 [A|E] を作成する。
行基本変形によって、[A|E] を [I|B] の形に変形する。このとき、B が逆行列 A^-1 になる。
B が求まったら、A^-1 = B となる。
このアルゴリズムを行うことで、n 次正方行列 A の逆行列 A^-1 を求めることができる。
この式は、行列Aの行列式を対角成分のn個の余因子展開によって表現しています。各余因子は、行列Aの(i,j)要素を除いたn-1次正則行列の行列式に符号をかけたもの (Aの各行または各列について、その要素を除いたn-1次正則行列の行列式と、その要素に対する係数を掛け算して足し合わせることでdet(A)を求めるもの)で、
この式を計算するためには、n個の余因子展開を計算する必要があります。各余因子展開には、n-1次正則行列の行列式を計算する必要があります。このため、このアルゴリズムの時間計算量は、n個の余因子展開それぞれに対してn-1次正則行列の行列式を計算することに相当します。
n次正則行列Aの行列式を計算するためには、n回のn-1次正則行列の行列式を計算が必要であり、各行列式の計算にLU分解を用いて行列を三角行列に分解する方法のことです。このアルゴリズムの時間計算量はO(n^3)です。したがって、n個の余因子展開それぞれに対してn-1次正則行列の行列式を計算する時間計算量は、O(n^4)になります。
【関連するAtcoderの例題】
「行列操作」
レーティング難易度(★): 500
ACした回答者に絞った場合のレーティング帯の範囲(数値): 1230~2263
レーティング難易度(%): 10.2%
レーティング(数値): 1933
AC率(%): 20.3%
ACしたスコアの高い回答者: https://atcoder.jp/users/doggy729
解説ブログ: https://blog.hamayanhamayan.com/entry/2021/05/22/090000
この問題は、行列の積や逆行列の計算を行う問題であり、正則行列の扱い方を問う問題としても取り上げられている。
「Matrix Power Series」: https://atcoder.jp/contests/abc205/tasks/abc205_e
レーティング難易度(★): ** / レーティング帯の範囲(数値): 800 - 1600 / レーティング難易度(%): 46.44% / レーティング(数値): 1318 / AC率(%): 12.94% / ACしたスコアの高い回答者: - / 解説ブログ: https://atcoder.jp/contests/abc205/editorial/2229
この問題は、行列の冪級数を求める問題であり、正則行列の逆行列の計算を行う必要がある。行列の冪級数は、行列の固有値と固有ベクトルを用いて計算することができるため、正則行列の逆行列の計算ができることが求められる。
「Matrix Determinant」https://atcoder.jp/contests/abc184/tasks/abc184_f
レーティング難易度(★): 300
ACした回答者に絞った場合のレーティング帯の範囲(数値): 1900~3000
レーティング難易度(%): 20%
レーティング(数値): 2625
AC率(%): 18.50%
ACしたスコアの高い回答者: taymison
解説ブログ: https://taymison.hatenablog.com/entry/2020/12/22/203913
Discussion