xとyの積を含む連立方程式：解の存在条件

質問

2以上の自然数M, N, Kと，M×N実行列Aが与えられたとき，
X Y = A …(1)
を満たすM×K実行列Xと，K×N実行列Yを求めたい状況にあります．但し，Xの各行の要素の和は1であるという制約条件をつけます．

この問題を，連立方程式を解く問題と捉えると，
○未知数の数 n1 = M×(K-1) + K×N
○線形独立な式の最大数 n2 = M×N
となりますが，そもそも線形方程式系ではないため，「n1 >= n2 ⇒ 少なくとも1つの解が存在する」，等とは言えないようです．

そこで，この問題について，
Q1. X, Yの解の存在条件は，どのようなものでしょうか？
Q2. 数学的には，どのように呼ばれる（インターネットで調べるとき，どのようなキーワードで検索すればよい）でしょうか？

よろしくお願い致します。

回答No.1

sugakusya · ベストアンサー

Q１ は下に示した通りです。あるいはA^T=(XY)^T=(Y^T)(X^T)を用いて、Y^T→X、X^T→Yとして考えて、同じことがいえる。

Q２ については何とも言えませんが、線形代数のうちであることは間違い無い。

見にくかったらすいません。画像。

お礼

早速回答頂き，また画像でわかりやすく説明頂き，誠にありがとうございます。
このように扱えるとは…まさに目からウロコです！！

画像のご説明では，K次元列ベクトル yi (i=1,2,…,N+1) を未知数とする連立方程式 X'Y'=A' の解の存在条件を，
rank(X'|A') = rank(X') …(2)
として示されているかと存じます。このアプローチでは，
「X, Yが(1)を満たす」条件を，「与えられたXについてYが(1)を満たす
」条件として捉え直されていると理解してよろしいでしょうか。

ところで，条件：
rank(X|ai) = rank(X) …(3)
K = rank(X) …(4)
に関して，なぜ (4) ⇒ (3) ⇔ (2) が成り立つのか，まだ理解できておりません。

X'の形から，
rank(X'|A') = Σrank(X|ai)
rank(X') = N * rank(X)
だと思いますので，
(2) ⇔ Σrank(X|ai) = N * rank(X)
となるかとは存じます。

（もしかすると，関係 (4) ⇒ (3) に関しては，M, N, Kの間に大小関係を仮定されていますでしょうか？）

恐縮ですが，ヒントを頂ければ幸いです。
よろしくお願い申し上げます。

回答No.5

noname#101087

>..... 「XY ＝ A を満たすX, Yが存在するとき，X, Yは一意に定まる」 ことを期待していたのですが，今回の結果より，これは望めなそうです。 ....

そうですね。
たとえば X が正方行列なら、任意の正則行列で XY ＝ A を満足させられますからね。

お礼

貴重なご指摘を頂き、ありがとうございます。
確かに，Xが正則行列のとき，Y = (X^-1) A と置けば，
X Y = A ですね！
ありがとうございます。

回答No.4

sugakusya

＞例えば，M > K, rank(X) = K, かつ，(X|ai)の各列から成るベクトルの集合が線形独立であるとき，rank(X|ai) = K + 1 となるように思います。

おっしゃる通りで。すいません。かなりひどい間違いです。
質問者さんは間違いと気付きつつ「躓いてしまいました」なんて言ってますよね？小憎いです(笑)。

さて、もう一度冷静に考えました。
まず、解の存在条件としてあげられるのが、
rank(X'|A')=rank(X') …(*1)
これを満たせば文句なしにY’が存在します。そしてこれは次と同値です。

すべてのiにおいて、rank(X|ai) = rank(X) …(*2)

(*2) ⇒ (*1) は自明。

(*1) ⇒ (*2) を示す。
(*1)⇔Σrank(X|ai) = N * rank(X)　である。

ここで仮に、

Σrank(X|ai) = N * rank(X) …(*1')
rank(X|ai) ＞ rank(X) となるiが存在する

が同時に成立したとする。
その時、(*1')からrank(X|ai) ＜ rank(X) となる iが存在することになる。しかしrank(X|ai) ＜ rank(X)はありえない。よって(*1')が成立したときrank(X|ai) ＞ rank(X) となるiは存在しない。
すなわち
(*1) ⇒ すべてのiにおいて rank(X|ai) = rank(X)が成立。

よって(*1)⇔(*2)

さらに(*2)⇔rank(X|A)=X　(*2)を認めればこれは自明ですね。

結局XY＝AとなるようなX,Yが存在するための条件はXがrank(X|A)=rank(X)を満たすように決められること。

今度はあってるのでは？てか、あっててほしい。先ほどの回答は無視でお願いします。実験までさせてしまい、すいません。

お礼

ご丁寧にありがとうございます。
今度は全て理解できました！

> 質問者さんは間違いと気付きつつ「躓いてしまいました」
> なんて言ってますよね？小憎いです(笑)。
いえいえ（笑）、私はいつも勘違いしてばかりですので、自分の考察に自信がありません。

結局，質問の答えは，
XY＝A を満たすX, Yが存在する ⇔ rank(X|A)=rank(X) を満たすXが存在する
という，すっきりした形にまとめて頂けました。

仕事上は，
「XY ＝ A を満たすX, Yが存在するとき，X, Yは一意に定まる」
ことを期待していたのですが，今回の結果より，これは望めなそうです。XY ＝ A を満たすX, Yが存在するならば，Xが無数にありそうです（まだ証明はできていません）。

取り急ぎ，お礼申し上げます！
本当にありがとうございます。

回答No.3

sugakusya

＞「X, Yが(1)を満たす」条件を，「与えられたXについてYが(1)を満たす」条件として捉え直されていると理解してよろしいでしょうか。

いや、違います。「rank(X'|A')=rank(X')」を満たすように自分でXを決めれば、 (1)を満たすYが必ず存在する。よってそのとき「(1)を満たすX,Yが存在する」という主張です。
与えられたXではなく、Xは自分で決めます。それに伴いYが決まりますが、どちらも自分で決めたことになります。

＞もしかすると，関係 (4) ⇒ (3) に関しては，M, N, Kの間に大小関係を仮定されていますでしょうか？

特にM, N, K間での大小関係についてはなにも考えてません。

＞ところで，条件：
rank(X|ai) = rank(X) …(3)
K = rank(X) …(4)
に関して，なぜ (4) ⇒ (3) ⇔ (2) が成り立つのか，まだ理解できておりません。

すべてのiにおいて、
K ≧ rank(X|ai) ≧ rank(X)　…(a)ですよね？
また、
rank(X')=(N+1) * rank(X)　…(b)
K(N+1) ≧ rank(X'|A') ≧ rank(X')　…(c)

ここで、(4)が成立するとすると、つまり、rank(X)=Kだとすると、
すべてのiにおいて、(a)より、
rank(X|ai) = rank(X) = K　 …(3)
が成立する。
よって(4) ⇒ (3)が証明できた。

そして(b)より、
rank(X') = (N+1)K
が成立し、(c)より
(N+1)K = rank(X'|A') = rank(X') …(2)
すなわち、(4) ⇒ (3) ⇒ (2)

さらに、(2)が成立し、
rank(X'|A') = rank(X')
だとする。このとき、
rank(X|ai) ≠ rank(X) となるiが、すなわち
rank(X|ai) ＞ rank(X)　となるiが
存在すると(2)が成立しているから、rank(X|ai) ＜ rank(X)となるiが必要になるが、rank(X|ai) ＜ rank(X)はありえない。よって(2)が成立しているときrank(X|ai) ≠ rank(X)はありえず、
(2)⇒(3)すなわち、(4)⇒( (3)⇔(2) )である。

コメント
じつは感覚で適当に書いてしまい、真剣に証明しようとすれば結構難しく、ほんとに成り立つかドキドキしてました(汗)。
欠陥があれば教えてください。

お礼

詳しいご説明を頂き，ありがとうございます。とても助かります。

解の存在条件の捉え方について，理解できました！

(4) ⇒ (3) ⇔ (2) の証明については，躓いてしまいました：

> すべてのiにおいて、
> K ≧ rank(X|ai) ≧ rank(X)　…(a)ですよね？

ここで，
K ≧ rank(X|ai)
は，方程式(1) : X Y = A の解であるXに関しては成り立ちますが，全てのM×K実行列Xに関しては成り立たないのではないでしょうか。
例えば，M > K, rank(X) = K, かつ，(X|ai)の各列から成るベクトルの集合が線形独立であるとき，rank(X|ai) = K + 1 となるように思います。
(c)も同様に，全てのXに関しては成り立たないかと存じます。

(4) ⇒ (3)の成立性を調べる実験として，(M, N, K) = (5, 4, 3)と設定し，M×N実行列AとM×K実行列Xを，擬似乱数で作る試行を10回繰り返しました。その結果，全ての試行について，rank(X) = 3 = K, rank(X|ai) = 4 = K + 1 となりました（擬似乱数では，線形従属の列ベクトルが生まれる確率は非常に低いため）。また，X Y = Aを満たすYは見つかりませんでした。

(3) ⇒ (2)の成立性については，まだ実験できておりません。

(b)に関して，回答1に対する私のお礼では，(N+1)をNと誤記しておりました。失礼致しました。

回答No.2

noname#101087

m×n 実行列A と k×n 実行列Y を
　A = [a1 a2 ..... an]
　Y = [y1 y2 ..... yn]
と列行列に分けましょう。

m×n 実行列X を Y に掛ければ、
　XY = [Xy1 Xy2 ..... Xyn] = [a1 a2 ..... an]
ですね。
つまり、
　Xy1 = a1
　Xy2 = a2
　.....
　Xyn = an
これって、線形方程式系ではないのでしょうか？
単に、当方が曲解しているのかも。

お礼

貴重な回答を頂き，ありがとうございます。
ご指摘の通り，列行列に分ければ，線形方程式系ですね。
自分自身では，恥ずかしながら気づきませんでした。
線型方程式系：
Xy1 = a1
Xy2 = a2
.....
Xyn = an
を，（Xの各行の要素の和は1であるという制約を含めて）1つの行列方程式にまとめ，解の条件を探したのが，最初に頂いた回答の方法ですね。