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

Question

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. 数学的には，どのように呼ばれる（インターネットで調べるとき，どのようなキーワードで検索すればよい）でしょうか？

よろしくお願い致します。

sugakusya · Accepted Answer

Q１ は下に示した通りです。あるいはA^T=(XY)^T=(Y^T)(X^T)を用いて、Y^T→X、X^T→Yとして考えて、同じことがいえる。

Q２ については何とも言えませんが、線形代数のうちであることは間違い無い。

見にくかったらすいません。画像。

noname#101087 · Answer

>..... 「XY ＝ A を満たすX, Yが存在するとき，X, Yは一意に定まる」 ことを期待していたのですが，今回の結果より，これは望めなそうです。 ....

そうですね。
たとえば X が正方行列なら、任意の正則行列で XY ＝ A を満足させられますからね。

sugakusya · Answer

＞例えば，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)を満たすように決められること。

今度はあってるのでは？てか、あっててほしい。先ほどの回答は無視でお願いします。実験までさせてしまい、すいません。

sugakusya · Answer

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

noname#101087 · Answer

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
これって、線形方程式系ではないのでしょうか？
単に、当方が曲解しているのかも。

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

Q１ は下に示した通りです。

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

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

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

m×n 実行列A と k×n 実行列Y を

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

Q１は下に示した通りです。

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