拙著『図解　線形代数：ストラング流直感的理解』のブログシリーズです。 前回、モンドリアン行列のランクを調べましたが、同じようなルールで各国の国旗を調べてみましょう。ランクとは、線形独立な最大な行数です。旗の例では、足し算や色の交換だけで重複を省いた行のパターン数です。 ちなみに、正確に線形代数のランクを測るための、行列の変換規則を書いておきます。以下の行基本を行なっても行列のランクは変化しません。（）の中に旗で考えるときのわかりやすい解釈も入れましたので、この変換で置き換えてから、最後に残るパターンの数を数え、自分でランクを計算してみてください。 行基本変形 さらに、うえの変形を行でなく列にしても大丈夫。行と列を混ぜて変形してもランクは不変です。 Fracne, Sweden, Greece France はすべてが同じ行の繰り返しでパターンが1つ。Sweden の行のパターンは2つですね。Greeceの行のパターンは少し難しいですが、4つありそうです。しかし、2行目+3行目=1行目なので、ランク3です。あるいは、列のパターン数を数えた方が分かりやすく、明らかに3パターンです。 Japan さて、問題は日本です。このような行列の問題では「斜めのライン」がランクに大きく効きます。行基本変形で消えにくいのです。縦や横にぴったり沿ったライン（水平・垂直）は他の行や列と同じパターンになるので、ランクの増加に効きにくいのです。これに対して、三角行列や単位行列を思い出して下さい。斜めのラインがあるために、ランクは最大（斜め線のサイズ）になります。 下図を見て下さい。縦横に整列した正方形は最小ランクで1、45°傾いた正方形＝ダイヤモンドは最大ランクで$n$。と大きな開きがあり、円はその間の数になります。 Prof. Gilbert Strang と Prof. Alex Townsend は、この円のランクを $0.5858n$ 程度と計算しています。動画『なぜ特異値は急激に減少するのか』および書籍『ストラング：教養の線形代数』には、日本の国旗のランクを求める問題があります。解答は動画中で分かりやすく解説されているほか、 Solution Manual の 7.2 節の練習問題 5（p.82）にあります。 ここで、解答のあらすじを。 $$2(n – 1/\sqrt{2}n) = (2 – \sqrt{2})n \approx 0.5858n$$ となります。では数値実験してみましょう。 日本国旗のランク計算 キャンバスサイズを 200×300 ピクセル、円の半径を $n=100$ と設定して計算します。ランクの計算には特異値分解を用います（ランクは非零特異値の数です）。ランクは整数ですが、零と非零の境界（$\epsilon$）をどこにおくかで、現実的にその数は変わります。特異値分解はその安定したアルゴリズムによって、ランクを連続的に特異値（実数）の列として見ることができます。 今回設定した半径 $n=100$ をこの公式に当てはめると、次のようになります。 $$(2-\sqrt{2}) \times 100 \approx 0.58578 […]

拙著『図解　線形代数：ストラング流直感的理解』の表紙のデザインはモンドリアン風のデザインになっています。 このようなブロック的なデザインを行列に見立てて、そのランクを求めるという問題です。白の背景はすべて0、色が付いている部分には、色ごとに違う数字が入っていると考えます。 3つの解法を紹介します。 解答例1　ガウスの消去法 ガウスの消去法を使います。最上部の灰色四角形にまず注目してください。この灰色部分が仮に2行分あるとします（何行でも構いません）。1行目（灰色が少し入っている帯）を2行目（1行目と同じ帯）から引き算すると、2行目を0にできます。灰色の行はすべて1行目と同じなので、同様にしてすべての灰色の行を0にできます。 次に、灰色の下に赤色があります。赤色の行はすべて同じなので、赤色の1行目をその下の行たちから引き算して、赤色の行を0にできます。 この操作を同様に続けると、青も黄色も1行を残して0にできます。最下部の赤ですが、これは青の行のスカラー倍になります。 行基本変形でこれ以上の行は消せません。したがって、ランクは残った非零行数＝4です。 解答例2　行優先の $CR$ 分解 本書『図解　線形代数：ストラング流直感的理解』列優先の $CR$ 分解を行う方法を説明しています。線形独立な列を選び、残りの列を線形結合で表す方法です。 ここでは、行に対して同様の方法を使います。行列の掛け算を、右の行列の行の線形結合として見る見方です。以下の図のような分解です。 すると、線形独立な行は4行が選べて、残りの行はそれらの線形結合で表せます。 線形結合と言っても実際には上の行の1倍、最後の赤だけ、これは青の行のスカラー倍（ $c=青色/赤$ ）になります。ランクは線形独立な行の本数=4です。右辺の右の行列に行空間の基底が、左の行列には、1と0が並びます。ちょうど、1が並ぶ部分は、同じ色の区画を引き延ばす役割です。ちょうど機械学習でのデコーダのように、もとの次元に戻す操作を担当しています。 上の式は、$A\transp$に対して通常の$CR$分解を行ったという解釈もできます。 解答例3 $CR$分解 ここで、本文で詳説した$CR$分解をそのまま行います。実は、この行列は列方向に見ると複数の色が混じって少し複雑です（本書や『ストラング：教養の線形代数』で $CR$ 分解を習得していない方は、ここをスキップしても構いません）。その理由でこの解法を最後に紹介しています。線形独立な列を選び、残りの列をそれらの線形結合で表します。図の要領です。 少々見にくいですが、線形独立な列は4本、残りの列はそれらの線形結合で表せます。 線形結合と言っても実際には上の列の1倍です。ランクは線形独立な列の本数=4です。 ここからさらに派生して、各国の国旗のランクを調べるという問題を次のブログで扱います。