整数値行列のベクトルによる行の置換

質問

以前からちびちび考えていたのですが
原理的に不可能なような気もして、
ひょっとすると人生を無為に過ごしているかもしれないので
質問させてください。

整数値M×N次元行列{a[m,n]}に対して
整数値N次元ベクトル{b[n]}を
　c[m,n] = a[m,n]+b[n] (mod q)
と作用させたときc[m,n]がa[m,n]の
行の値の置換となっている
すなわち、m=1,2,..,Mがある置換Pによって
P(1),P(2),...,P(M)と置きかえられるとき
　c[m,n] = a[P(m),n]
となっている、行列aとベクトルbの組、そしてq
を求めたいのですが
こんな組み合わせってあるのでしょうか？
※置換の数はM!通りあるわけなので
　それぞれに対応した変換を与える
　ベクトル{b[m]}の組{{b[m]}}が
　全部存在していて欲しいと思います。
※もちろん
　a[m,n] と a[m',n]はすべての(m,m')の組に対して
　等しくないとします。
多分、a[m,n] と a[m',n] の値を上手い具合に
不等間隔に並べればいいかと思うのですが...？

あるいは類似の問題（できれば、答えが導かれているもの）
を教えていただければと思います。

MやNに制限は設けませんが、
できればある程度の大きさがあったほうがいいです
（逆に、無限大というのもこまりますが）

以上、不明な点は補足させて頂きますので、
要求をお願い致します。
（回答はできるだけ簡単に
　あらすじだけでも結構ですのでよろしくお願いします。）

回答No.2

stomachman · ベストアンサー

この話、ベクトルも行列も関係ないでしょう。
列<a[m]> (m=1,2,....M。∀n,m(n≠m→a[n]≠a[m])）の各要素に定数bを加えて作った列 <c[m]> (∀m(c[m]=(a[m]+b) mod q)） が列<a[m]>の置換になっているようにしたい。そしてb（0＜b＜q ）を変えるだけで全ての置換が網羅されるようにしたい。
という問題ですね。違います？

そういう<M, <a[m]> , q>があったとしましょう。
さて、M個の要素に関する置換全部の集合をPとするとき、M個の要素に関する互換の集合SはS⊂P。従って、ある互換sについて
<c[m]> = <a[s(m)]> = <(a[m]+b) mod q>
となるbが存在する。従って任意のmについて、
<c[s(m)]> =<a[s(s(m))]> = <a[m]>
つまり
<a[m]> =<(a[m]+2b) mod q>
でなくてはなりません。よって、
2b ≡ 0 (mod q)
ゆえに2b=q でなくちゃならんことになりますね。
このようなbは一つしかない。一方、互換はM (M-1)/2個ある。よってM>2の時には無理。

だから、この問題は「不可能」が答、かな？

お礼

stomachmanさん。回答ありがとうございます。

証明了解いたしました。もともとの問題は x の関数 f_j(x) (j=0,1,2,...,N) があって、
　exp[ i (f_j(x)+ g(x)) ] = exp[ i f_P(j)(x) ]　（ i は虚数単位）
となるようなg(x)があったら、便利だろうな、というところから、行列になってしまいました。そういう都合がいいことはそうそう起こらないと思っていましたがやっぱりそうですか。
（※oodaikoさんが等差数列のときを示してくださったように、
　　同じ列に同じ値が複数含まれる場合はN＞１で
　　行単位の置換の意味がちょっと違うのだなと思いました。
　　多分、の場合は同じ列に同じ値が複数含まれる場合を許す場合だと思います。
　　a[1,1]=1, a[1,2]=0, a[2,1]=1, a[2,1]=1 のようにです。
　　ただ、stomachmanさんの証明自体は生きますよね。）

方法としては、似たような置き換えを何回かくりかえしてもいいかと思っています。
（ごめんなさい、問題自体が固まっていないもんで。最終目標は、「とにかく足し算だけで置き換える」ということなんです。）
a[m,n]+b_w[n] (mod q_w) (w=1,...,W)
として（Wはできるだけ小さく）、何回か繰り返していつかは、目的とする置換になっているというようなイメージです。（歯車のついたくるくるお絵かき定規（？）みたいに（スピログラフというらしいです）。）
ともあれ、stomachmanさんのおかげで一歩前進です。ありがとうございます。

回答No.5

stomachman

め、滅相もない。全然怒ってないですてば。
えらそな事申し上げて、こちらこそ失礼しました。

　modを使うのは周期性の意味ですよね。
　必ずしも足し算に拘らないなら、いろんな系が作れそうに思われます。線形空間論、直交関数論で、応用数学として必要に迫られて開発された方法がたくさんある。
　是非、新たな手法を開発なさることを期待しています。
　直交性云々については、upしてから自分でアレ？と思ってました。見なかったことにしてくださいな。

お礼

回答どうもありがとうございます。

質問の出し方がまずかったようです。また出直します。
どうもありがとうございました。

回答No.4

stomachman

> もともとの問題は x の関数 f_j(x) (j=0,1,2,...,N) があって、
>　exp[ i (f_j(x)+ g(x)) ] = exp[ i f_P(j)(x) ]　（ i は虚数単位）
>となるようなg(x)があったら、便利だろうな

仮にあったとして、f_j(x)として好き勝手な関数が使えず、また直交どころか線形従属である。そういう関数族f_jがどう便利なのか、ちょっと想像が付きかねます。また、

> a[m,n]+b_w[n] (mod q_w) (w=1,...,W)

つまり法qを毎回変えても良い、という風に問題を拡張していらっしゃいますが、「もともとの問題」に照らせばq = 2π/k (k∈正の自然数) 以外では意味を持たないのでは？
　失礼を省みず、アドバイスということで：もし実用目的が何かあるのでしたら、それをストレートに質問なさった方が良さそうですよ。

お礼

stomachmanさん、夜分遅くまでありがとうございます。

>　exp[ i (f_j(x)+ g(x)) ] = exp[ i f_P(j)(x) ]　（ i は虚数単位）
はそのままです。空間に位相分布しているような波面を取りかえるようなものを考えています。すぐにどうこうというわけではないのですが、止まらない信号（メモリ／バッファを用いずに）を処理するような場合に使えるかなという程度です（他にはアナログＣＤＭ回路のようなものにもつかえるかもしれません・・・あとづけです）。f_j(x)というような分布を作ること自体が大変ですし、式のような変換は実際は原理的に無理だと思っています。
　でも、他の似た形態では何かあるかもしれないので、そのヒントのようなものが得られればと考えて質問しました。以上の意味で、実用というよりは単なる興味＝関連知識が欲しと思っています（その意味で、完全な回答よりも、刺激的なアイデアを期待しているとも言えるかも知れません）。もちろん答えそのものがあれば、それを応用して上記のような系への適用を考えるかもしれませんが。
　ご気分を害されたのでしたら申し訳ありません。２次の合同式とか良く知らないもので、なんかその当たりで、こういう変な数を使えば上手くいくよとか、oodaikoさんのように、制限つきの入れ替えであればできるなどなにか示唆していただければと考えています。

　さて、
＞直交どころか線形従属である
というご指摘ですが、exp[ i f_j(x) ] (j=1,2,...）という関数の系は線形従属ではないので
それなりに意味があるのだと思います。また、 g(x)がある程度ランダムであれば、
exp[ i f_j(x) ] (j=1,2,...）は積分により内積を定義すればある程度直交性をもつようになると思います。（もちろんそんな系があればですが）

＞「もともとの問題」に照らせばq = 2π/k (k∈正の自然数) 以外では意味を持たないのでは？
ですが、上記の具体的な系を何段かに組んだようにしてもいいかなという程度です。
というか、最初に述べたように具体的な構成があるわけではないので．．．

stomachmanさんにお手を煩わせて大変申し訳ないと思っています。
本当に気軽な気持ちで訊いているだけなので、お叱りはごもっともだと思いますが許してください。

回答No.3

oodaiko

N=1なら簡単です。以後特に断らない限り演算や等式はすべて環Ｚ/q 上で考えます。
すなわちmod qで考えます。

さてqは固定してN=1の場合を考えます。stmachmanさんが書かれているように
この問題でベクトルとか行列は本質的なことではありません。問題を

<a[1],a[2],…,a[m]>を Z/q 上の列とするとき すべてのi ∈{1,2,…,m} に対し
a[i] + b = a[P(i)]となるような b ∈ Z/q と{1,2,…,m}上の置換Pが存在するための
条件を求めよ。

と言う形で考えてみましょう。
mを１つ固定して考えても、任意の置換に対して条件を満たすような
{<a[i]>,b}が存在するとは言えないということはstomachmanさんの証明の通りです。
しかし置換の形によっては条件を満たすものも作れます。
以下で問題の条件に合うような m,<a[i]>,b,P の満たすべき条件を考えます。
証明をきちんと書こうとするとかなり表記が面倒なものになりそうなので概要だけ書きます。

（０） まずi≠jならa[i]≠a[j]と言う条件から当然 m≦q であることが必要です。
（１）さらに各成分 a[i] は公差k（ただしk∈{1,2,…,q}）の循環する等差数列のそれぞれ
異なる要素であることが必要です。すなわち<a[i]>の要素を適当に並べ変えて
a[i_1]+k = a[i_2] ,a[i_2]+k = a[i_3],… ,a[i_{m-1}]+k = a[i_{m}] ,a[i_{m}]+k = a[i_1]
となっている必要があります。q = 12 としていくつかこのような等差数列の例を挙げると
{ 2,5,8,11 } （公差3）, { 11 ,5 }（公差6) , { 0,1,2,3,4,5,6,7,8,9,10,11}（公差1）
などです。

（２）ここで公差kは1からqまでの任意の整数をとることが出来ますがmは（１）の条件があるので
kによって決まります。具体的にはkとqの最小公倍数をlとし、l = sk（これは通常の整数演算です）
とするとm=sになります。従ってkがqの約数ならm = q/k、kとqが互いに素ならm = qとなります。
そこでqによっては取り得ないmもあります。例えばq = 12ならm= 5とすることはできません。

（３）もうおわかりだと思いますが（１）のような<a[i]>は問題の条件を満たし、そのときの
bの値はkになります。証明は省略しますが、直観的に問題の要請を満たすものであることは
おわかりいただけると思います。

q = 12 として例を作ってみましょう。k=10とします。等差数列として
{1,11,9,7,5,3 }をとります。適当に並べ変えて
a = ( 5,9,1,7,11,3 )としましょう。aの各要素に10を足したものは
c = ( 3,7,11,5,9,1) となるので
置換P＝
/1　2　3　4　5　6\
\6　4　5　1　2　3/
によってc[i] = a[P(i)]と表現できます。

またbとして公差のt倍の数を取れば
c[i] = a[P^t(i)]となります。
今の例で言えばk=20とすると
c=(1,5,9,3,7,11)であって c[i] = a[P^2(i)]となっています。

（４）またどんな置換に対してもaがとれる訳ではなく、恒等置換以外で”不動点”がある置換
（すなわちP(i)= iとなるようなiが存在する）の場合は a はとれません。
それは不動点iに対してa[i]+ k = a[P(i)] = a[i]であるから必然的に k= 0となり
従って<c[i]>= <a[i]>となってしまうからです。
m > 2なら互換は不動点を持ちますから
互換に対して条件を満たすような<a[i]> ,bはとれません。
以上でN=1に対する問題はおわりです。

N ≧ 2 に対してはN=1の場合を応用します。
＞ N>1の場合は、各列が違う系列
ということですから、異なるkに対する等差数列を並べれば良いですね。
このとき公差k_1,k_2,…,k_Nに対する項数をそれぞれm_1,m_2,…,m_Nとすると
全体の項数mは{m_1,m_2,…,m_N}の最小公倍数である必要があります。

q=12の例を一つ作ってみましょう。

０　　４　　２　　５
１　　８　　５　　７
２　　０　　８　　９
３　　４　　１１　１１
４　　８　　２　　１
５　　０　　５　　３
６　　４　　８　　５
７　　８　　１１　７
８　　０　　２　　９
９　　４　　５　　１１
１０　８　　８　　１
１１　０　　１１　３

１列目の公差は１、２列目は４、３列目は３、４列目は２となっています。
そこでb= <1,4,3,2>となります。この行列の行を適当に入れ換えたものも
条件を満たします。また任意の列の要素を循環的に入れ換えても同様です。
なんだか符合理論のような匂いがしてきた……
というより情報代数の中ですでに知られている結果のような気がしてきました。

大部はしょったので計算ミスなどがあるかも知れません。わかりにくいところがあれば
補足要求して下さい。

お礼

oodaikoさん、回答ありがとうございます。
　等差数列で公差の倍数で変換するということですよね。
実例を交えてお示しいただきありがとうございます。
　私が漠然と思っていたのは、たとえば、数列が a_n=c*n^2 のような2次式であたえられていれば、適当なｑの合同式を考えて還元すると、ちょうど２次関数のグラフを還元すると、初めはゆっくり立ち上がって、あとになるほど傾きが急になることから、それを平行移動するような操作をするともう少しいろいろな変換が可能になるのかなということでした。（stomachmanさんに蹴られちゃったですけど。）
　oodaikoさんに示して頂いたように、線形の場合も結構ランダムな変換が起こっているように見えるものだと感動しました。また、stomachmanさんのお礼にも書かせていただいたように、ちょっと見落としていた大事なところにもおかげで気がつきました。ありがとうございました。
　　oodaikoさんご指摘のように、この手のことは結構考えられているのかなと思いますので、もうちょっと、この質問を開いておきたいと思います。

回答No.1

oodaiko

補足要求です。
c[m,n] = a[m,n]+b[n] (mod q)
とは何のことでしょうか。ベクトルと行列の和とはどういう風に定義するのでしょうか。
またmod q と言うのは(両辺がm×nの行列だとして)各成分がqを法として合同
と言う意味でしょうか。

また、(この式の右辺がm×nの行列だとして)ある置換Pによって c[m,n] = a[P(m),n]
と表せるようなあるa,b,q の組が得られたとして
＞それぞれに対応した変換を与える
＞ベクトル(b[m])の組{(b[m])}が
＞全部存在していて欲しいと思います。
ということは行列aと整数qは固定して別の置換P'を持って来たら、そのP'に
対してもc'[m,n] = a[P'(m),n]となるようなb'が存在する。
そのようなa,qの組を求めたいと言うことなのでしょうか。

あと補足要求ではありませんがベクトルや行列は丸括弧を使って(a[m,n])、(b[m])と
書くべきです。この場合は一応ベクトル、行列と断っているので間違えることはないと
いうものの、中括弧は集合を要素として書くときの記号なので、黙って{a[m,n]}と
書くと a[m,n] を要素とする集合の意味になってしまいます。

おっと追加質問です。
＞ある置換Pによって
＞c[m,n] = a[P(m),n]
＞となっている
この等式もmod q の意味での等式ですね。

補足

補足要求ありがとうございます。
質問を出したあとしまったと思ったのですが、
出てくる行列とベクトルはすべてqを法として合同なものを考えてください。

> ということは行列aと整数qは固定して別の置換P'を持って来たら、そのP'に
> 対してもc'[m,n] = a[P'(m),n]となるようなb'が存在する。
> そのようなa,qの組を求めたいと言うことなのでしょうか。
おっしゃるとおりです。

あともうひとつ設定を忘れておりました。
本質的にN=1の場合だけ考えれば良いので
この場合だけ考えてくださっても良いかと思います。

N>1の場合は、各列が違う系列のものを求めていただければと思います。
つまり、n,n'が異なるときa[m,n]を
並べ替えただけのa[P(m),n’]のようなものではないものを
考えていただければと思います。

分かりにくい説明で申し訳ありませんがよろしくお願いします。