2.Skewed Commutative(?)なMatrix(Gilbert Strang)

AB = -BA となる Matrix の組はいくつあるのか?

私は最初これを要素の問題とみて，それを満たすものの条件がみつかるかもしれないと考えた．つまり，

Equation: First try

これらが等しいとしてその条件を使おうとした．しかし，あまりに様々な場合がでてきてしまい，私は正しいことをしている自信がなくなった．

次の方法は matlab/octave を使うことだ．ここで問題を簡単にするために次の条件を入れた．

行列の要素は {-1,0,1} に限る．

アルゴリズムは generate and test 法であり，6561通り(= 3^4 3^4)の全ての組合せを生成し，AB=-BA (ただし，AB=0 を除く)の行列を列挙する．私は組合せではなく，順列を生成したため，全ての組合せを単に数えると，組として同じものを二度数えてしまう．しかし二度数えるとわかっているので，半分にする．(たとえば，前回の Blog の Equation(1) の D = B, E = A とした時，AB と DE を別の解答としてしまう．)

結果は，112 であったので，56 の条件を満たす行列の組をみつけることができた．

1.Skewed Commutative(?)なMatrix(Gilbert Strang)

Introduction to Linear Algebra by Gilbert Strang
Chapter 2, Section 4, Problem 22


概要

私が Gilbert Strang の Introduction to Linear Algebra 4th ed. の第 2 章4 節，問題 22,「DE = -ED (ただし，DE = 0 は除く) となる行列を試行錯誤によってみつけよ．」の解答を得た後，次の疑問が生まれた．「いったいいくつのこのような行列の組があるのだろう?」私は 56 という解答を得た．この話を友人の Marco にしたところ，彼は「そのような行列を可視化できるか」という質問を私に投げかけた．この疑問に対する一応の解答が得られたので，ここで述べる．


Linear Algebra, 2.4, Problem 22

Gilbert Strang の Introduction to Linear Algebra 4th ed.の問題にはいくつも面白いものがある．たとえば，第2章4節の問題 22 には，

By trial and error find real nonzero 2 by 2 matrices such that
A^2 = -I, BC = 0, DE = -ED (not allowing DE = 0)

これは，

試行錯誤で次の条件を満たす 2x2 の行列を求めよ
A^2 = -I, BC = 0, DE = -ED (ただし，DE = 0 は除く)

という問題がある．私は試行錯誤によって，

Equation(1)


の解を得た．本の解答には別の matrix があり，そこに一つのコメントがあった．You can find more examples (p.521). (他にもこのような例をみつけることができる．)

それを見て私は思った．このような行列はいったいいくつあるのだろうか?

つづく

迷路を画像処理(モーフォロジカル演算)で解く．

たまたまみつけた迷路ソルバ．

http://www.mathworks.com/matlabcentral/fileexchange/27175-mazesolution

通常はスタート地点から右手を壁につけて進むという手法だが，これは図形的に解くという面白い手法のようだ．

ちょっと理解が足らないとは思うが，どうやら次のようにして迷路を解くらしい．

仮定: 解となる道は一つだけ．つまり，トポロジ的には壁が2つのコンポーネントになっている．

1. モーフォロジカル演算(上下左右につながっているピクセルを見つけるとか，その領域を広げるなどの演算)を用いて2つの壁を分離する．

2. 2つの壁をモーフォロジカル演算にて道の幅だけ広げる．

3. AND 領域が答えである．

Cool だ．