線形代数の演習問題をジェネレートする [数学]
線形代数の講義で，「行列$A$の対角化をせよ」の問題は鉄板の一つであるが，整数成分の行列であってもランダムに選ぶと手計算では計算不能になってしまう．できれば，行列$A$は整数成分であって，なおかつ固有値が整数であるような問題にしたい．そうすれば，いらぬ分数の計算で演習問題を解く側の労働量をいたずらに増やすことは避けられる．
そのような$A$を得るには，整数成分で行列式が±1の行列$P$を作って，整数成分対角行列$B$によって
$A=P^{-1}BP$とすればよい．$P$は$GL(n,\mathbb Z)$の元が整数の範囲での基本行列の積で書けることを逆手に取ればいくらでも作れる．以下はsagemath用の関数の定義であり，行列式が±1の$n$次正方整数成分行列をランダムに生成する．$c,d$ は複雑性をコントロールするためのパラメーターである．
ある$n$に対してどのぐらいの$c,d$を選べばよいかは（いまのところ）試行錯誤による他ない．
対角化つながりで言えば，対称行列$A$を直交行列$U$で対角化せよ，というのも鉄板問題である．この種の問題は作るのがさらに難しい感じがあるがどうすればよいだろう．
あまり自信はないのだが，次のような方法を考えてみた．手順は次のとおりである．
sagemath 上では次のようなプロセスをたどる．
sagemathのgram_schmidt()は行に関してSchmidtの直交化を行い，ベクトルの長さを1に揃えない．
次のようにして整数成分の行列にしておく．
対角行列$D=\begin{pmatrix} a & 0 & 0 & 0 \\ 0 & b & 0 & 0 \\ 0 & 0 & c & 0 \\ 0 & 0 & 0 & d\end{pmatrix}$に対して$B^TDB$を計算してみる．
$a,b,c,d$を整数で選ぶ限り，たしかにこれは整数係数の対称行列である．$C$の固有値を計算すると
となって固有値もすべて整数になる．この手の問題が意味を持つのは固有多項式が重解を持つ場合であるが，例えば$a=2,b=1,c=1,d=2$とすれば，
で全体が2で割れるので2で割って，固有値を求めると
となって，2と6をそれぞれ重複度2の固有値として持つ整数成分対称行列が作れた．
もっともこの方法には難点が少なくとも2つある．1つは，行列の成分の絶対値が大きくなってしまいがちだということである．C0 を作る「種」 A の性質に大きく依存するので，いまのところ try & error 以外の方法を知らない（とはいっても，上の操作を何回も試みてリーズナブルなものが出てくるのを待つだけの，頭を全く使わない操作の繰り返しではある）．もう一つの難点は，このようにして得られる C0 は整数係数対称行列で固有値が整数になるようなもののうち非常に特殊なものしか得られていないのではないかという点である．代数群の分解について勉強すればもう少しスマートにできるだろうか．
こんな簡単なことは絶対に何回も既出だろうと思うけど，自分用の備忘のふりをして書いてみた．
そのような$A$を得るには，整数成分で行列式が±1の行列$P$を作って，整数成分対角行列$B$によって
$A=P^{-1}BP$とすればよい．$P$は$GL(n,\mathbb Z)$の元が整数の範囲での基本行列の積で書けることを逆手に取ればいくらでも作れる．以下はsagemath用の関数の定義であり，行列式が±1の$n$次正方整数成分行列をランダムに生成する．$c,d$ は複雑性をコントロールするためのパラメーターである．
def random_GLZ(n,c,d):
A = identity_matrix(n)
p=0
while p < c:
a = int(random()*(2*d+1))-d
i = int(random()*(n-0.1))
j = int(random()*(n-0.1))
if a == 0:
A.swap_rows(i,j)
elif i != j:
A.add_multiple_of_row(i,j,a)
p += 1
return A
ある$n$に対してどのぐらいの$c,d$を選べばよいかは（いまのところ）試行錯誤による他ない．
対角化つながりで言えば，対称行列$A$を直交行列$U$で対角化せよ，というのも鉄板問題である．この種の問題は作るのがさらに難しい感じがあるがどうすればよいだろう．
あまり自信はないのだが，次のような方法を考えてみた．手順は次のとおりである．
- 上のスクリプトで$GL(n,\mathbb Z)$の元$A$を作る．
- $A$の行にSchmidtの直交化を施し$B$を得る．ただしベクトルの長さを1に揃えず，必要ならばスカラー倍によって整数成分にしておく．
- 整数成分対角行列$D$に対して$C=B^TDB$は整数成分で，整数固有値の対称行列になる．
sagemath 上では次のようなプロセスをたどる．
sage: A=random_GLZ(4,10,3); A [ 1 0 2 1] [-2 1 -3 -2] [ 2 1 4 2] [ 0 0 0 1] sage: B=A.gram_schmidt()[0]; B [ 1 0 2 1] [-1/3 1 1/3 -1/3] [ 1/4 1/4 -1/4 1/4] [-1/2 0 0 1/2]
sagemathのgram_schmidt()は行に関してSchmidtの直交化を行い，ベクトルの長さを1に揃えない．
次のようにして整数成分の行列にしておく．
sage: B.rescale_row(1,3); B.rescale_row(2,4); B.rescale_row(3,2); B [ 1 0 2 1] [-1 3 1 -1] [ 1 1 -1 1] [-1 0 0 1]
対角行列$D=\begin{pmatrix} a & 0 & 0 & 0 \\ 0 & b & 0 & 0 \\ 0 & 0 & c & 0 \\ 0 & 0 & 0 & d\end{pmatrix}$に対して$B^TDB$を計算してみる．
sage: var('a,b,c,d')
(a, b, c, d)
sage: D=diagonal_matrix([a,b,c,d]); D
[a 0 0 0]
[0 b 0 0]
[0 0 c 0]
[0 0 0 d]
sage: C=B.transpose()*D*B; C
[a + b + c + d -3*b + c 2*a - b - c a + b + c - d]
[ -3*b + c 9*b + c 3*b - c -3*b + c]
[ 2*a - b - c 3*b - c 4*a + b + c 2*a - b - c]
[a + b + c - d -3*b + c 2*a - b - c a + b + c + d]
$a,b,c,d$を整数で選ぶ限り，たしかにこれは整数係数の対称行列である．$C$の固有値を計算すると
sage: C.eigenvalues() [2*d, 4*c, 12*b, 6*a]
となって固有値もすべて整数になる．この手の問題が意味を持つのは固有多項式が重解を持つ場合であるが，例えば$a=2,b=1,c=1,d=2$とすれば，
C0=C.subs(a=2,b=1,c=1,d=2); C0 [ 6 -2 2 2] [-2 10 2 -2] [ 2 2 10 2] [ 2 -2 2 6]
で全体が2で割れるので2で割って，固有値を求めると
sage: C0 = C0/2; C0 [ 3 -1 1 1] [-1 5 1 -1] [ 1 1 5 1] [ 1 -1 1 3] sage: C0.eigenvalues() [6, 6, 2, 2]
となって，2と6をそれぞれ重複度2の固有値として持つ整数成分対称行列が作れた．
もっともこの方法には難点が少なくとも2つある．1つは，行列の成分の絶対値が大きくなってしまいがちだということである．C0 を作る「種」 A の性質に大きく依存するので，いまのところ try & error 以外の方法を知らない（とはいっても，上の操作を何回も試みてリーズナブルなものが出てくるのを待つだけの，頭を全く使わない操作の繰り返しではある）．もう一つの難点は，このようにして得られる C0 は整数係数対称行列で固有値が整数になるようなもののうち非常に特殊なものしか得られていないのではないかという点である．代数群の分解について勉強すればもう少しスマートにできるだろうか．
こんな簡単なことは絶対に何回も既出だろうと思うけど，自分用の備忘のふりをして書いてみた．
ちょっと調べれば，sagemathには行列式が１の整数行列を作る組み込み関数があるみたいですね．
random_matrix(ZZ,4,algorighm='unimodular')
とかすればいいようで．あと，直交行列の方は，別に行列式±1からスタートする必要はないですね．
by pugnari (2018-01-20 14:47)