( ) ( ) 行 列 式 置 換 n文字の置換σ: n個の文字{1,2,・・・,n}から自分自身への1対1の写像 1 2 ・・・ n

Slides:



Advertisements
Similar presentations
1 線形代数学. 2 履修にあたって 電子情報システム学科 必修 2005 年度1セメスタ開講 担当 草苅良至 (電子情報システム学科) 教官室: G I 511 内線: 2095 質問等は上記のいずれかに行なうこと。 注意計算用のノートを準備すること。
Advertisements

陰関数定理と比較静学 モデルの連立方程式体系で表されるとき パラメータが変化したとき 如何に変数が変化するか 至るところに出てくる.
0章 数学基礎.
      ベクトル空間   実数体 体:数の集合で四則がその中で行えるもの 例)有理数全体、実数全体、複素数全体 R:実数体     C:複素数体  ベクトル空間
2章 文字の式 文字を使った式(第2時) 第1時の内容はスライド4~7の板書写真を参考にしてください。1時間で行こうと思えば行けます。
数理統計学(第四回) 分散の性質と重要な法則
det(tA)=Σ sgn(σ)aσ(1)1aσ(2)2・・・aσ(n)n
東邦大学理学部情報科学科 白柳研究室 小泉宏美
第1章 場合の数と確率 第1節 場合の数  3  順列 (第1回).
コンパイラ 2011年10月17日
円順列.
4.3 連立1次方程式   Ax = b   (23) と書くことができる。
群論とルービックキューブ 白柳研究室  水野貴裕.
計算の理論 I ー DFAとNFAの等価性 ー 月曜3校時 大月 美佳.
本時の目標 負の数をふくむ3つ以上の数の乗法や除法の効率のいい計算のしかたに気づき、効率よく計算することができる。
上坂吉則 尾関和彦 文一総合出版 宮崎大輔2003年6月28日(土)
論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる.
線形代数学 4.行列式 吉村 裕一.
4章 平行と合同 2 多角形の外角の和.
      線形写像  線形写像 U,V:R上のベクトル空間 T:UからVへの写像 (1)T(u+v)=T(u)+T(v)  (u,v∈U),
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
補数 n:桁数、b:基数 bの補数 bn-x 253(10進数)の10の補数は、 =747
コンパイラ 2012年10月15日
8.Intersecting Families
電気回路学Ⅱ エネルギーインテリジェンスコース 5セメ 山田 博仁.
10. 積分 積分・・確率モデルと動学モデルで使われる この章は計算方法の紹介 積分の定義から
情 報 A ー ディジタル化のしくみ ー.
3次元での回転表示について.
コンパイラ 2011年10月24日
数学 ---> 抽象化、一般化 より複雑な関係ー>解析学 一次関数 y=ax+b より多くの要素ー>線形代数 x y f(x) y1 x1
k 個のミスマッチを許した点集合マッチング・アルゴリズム
計算の理論 I -Myhill-Nerodeの定理 と最小化-
せん断力図(SFD)と 曲げモーメント図(BMD)
【第四講義】接空間と接写像.
【第二講義】1次元非線形写像の不変集合とエントロピー
 2 文字の式 1章 文字を使った式 §4 式の計算         (4時間).
線 形 代 数 (linear algebra) linear ・・・ line(直線)の形容詞形 直線的な、線形の、一次の
独立成分分析 (ICA:Independent Component Analysis )
4次元時空間(複素数)と ミンコフスキー時空間(実数)の差異
3次元での回転表示について.
本時のねらい 「二等辺三角形の作図から証明を使って性質を導くことができる。」 「定義や定理の用語の意味を理解する。」
Ibaraki Univ. Dept of Electrical & Electronic Eng.
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
計算の理論 I -Myhill-Nerodeの定理 と最小化-
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
様々な情報源(4章).
9.通信路符号化手法1 (誤り検出と誤り訂正の原理)
中点連結定理 本時の目標 「中点連結定理を理解する。」
進化ゲームと微分方程式 第15章 n種の群集の安定性
計算の理論 I ー閉包性ー 月曜3校時 大月 美佳.
資料 線型変換のイメージ 固有値、固有ベクトル 平賀譲(209研究室) 資料
第1回、平成22年6月30日 ー FEM解析のための連続体力学入門 - 応力とひずみ 解説者:園田 恵一郎.
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
計算の理論 I 非決定性有限オートマトン(NFA)
行列式 方程式の解 Cramerの公式 余因数展開.
計算の理論 I -数学的概念と記法- 火曜 12:50~14:20 大月 美佳 2004年4月20日.
本時のねらい 「合同な三角形の作図を通して三角形の合同条件を導き、それを理解する。」
解析学 ー第9〜10回ー 2019/5/12.
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
2009/11/27 グラフ (1) 第9講: 平成21年11月27日 (金) 4限 E252教室 コンピュータアルゴリズム.
行列 一次変換,とくに直交変換.
電気回路学Ⅱ 通信工学コース 5セメ 山田 博仁.
本時の目標 かっこのついた式の乗法と除法を、分配法則を使って効率よく解くことができる。
割り当て問題(assignment problem)
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
計算の理論 I ー ε-動作を含むNFA ー 月曜3校時 大月 美佳.
線形符号(10章).
空間図形の取り扱いについて.
2012年度 情報数理 ~ ハミング距離 ~.
Presentation transcript:

( ) ( ) 行 列 式 置 換 n文字の置換σ: n個の文字{1,2,・・・,n}から自分自身への1対1の写像 1 2 ・・・ n          行 列 式     置 換 n文字の置換σ:  n個の文字{1,2,・・・,n}から自分自身への1対1の写像 ( 1 2 ・・・  n ) σ = k1 k2 ・・・ kn 1→k1, 2→k2, ・・・ ,n→kn ( ) 1 2 3 4 σ(1)=3, σ(2)=1, σ(3)=4, σ(4)=2 例) σ = 3 1 4 2

( ) ( ) ( ) 置換の積 2つのn文字の置換σ,τの積στを στ(i)=σ(τ(i)) (i=1,2,・・・,n) と定義する。   置換の積 2つのn文字の置換σ,τの積στを στ(i)=σ(τ(i))    (i=1,2,・・・,n) と定義する。 ( ) ( ) 1 2 3 4 1 2 3 4 例) σ = τ = 4 3 1 2 2 3 4 1 στ(1)=σ(2)=3, στ(2)=σ(3)=1   στ(3)=σ(4)=2, στ(4)=σ(1)=4   ( ) 1 2 3 4 σ τ = 3 1 2 4

( ) ( ) ( ) ( ) ( ) 単位置換、逆置換 単位置換ε:全ての文字を動かさない置換 σの逆置換:σ-1 1 2 ・・・ n   単位置換、逆置換 単位置換ε:全ての文字を動かさない置換 σの逆置換:σ-1 ( ) ( 1 2 ・・・  n ) k1 k2 ・・・ kn σ = σ-1 = 1 2 ・・・  n k1 k2 ・・・ kn σ-1 σ= σ σ -1= ε ( ) 1 2 3 4 5 例) σ = 4 5 1 3 2 ( 4 5 1 3 2 ) ( 1 2 3 4 5 ) σ-1 = = 1 2 3 4 5 3 5 4 1 2

( ) 巡回置換 {1,2,・・・,n}のうち、 k1, k2, ・・・, kr 以外は動かさないで、     巡回置換 {1,2,・・・,n}のうち、 k1, k2, ・・・, kr 以外は動かさないで、 K1, k2, ・・・, kr のみを k1→k2 , k2→k3, ・・・ kr→k1 と順にずらす置換 ( k1 k2 ・・・ kr ) σ = を巡回置換といい k2 k3 ・・・ k1 σ = ( k1 k2 ・・・ kr ) と書く. 例) σ =(2 5 3) σ :2→5, 5→3, 3→2 σ =(2 5 3) =(5 3 2) =(3 2 5) 任意の置換は,巡回置換の積で表される.

互換 置換の符号 2文字の巡回置換 (i j) を互換という. 任意の巡回置換は     互換 2文字の巡回置換 (i j) を互換という. 任意の巡回置換は (k1 k2 ・・・ kr)= (k1 kr) ・・・(k1 k3) (k1 k2) と表されるので、全ての置換は互換の積で表される.   置換の符号 置換σがm個の互換の積で表されるとき sgn(σ)=(-1) m :σの符号 sgn(στ)= sgn(σ) sgn(τ) sgn(σ-1)= sgn(σ)

偶置換、奇置換 置換全体の集合 sgn(σ)=1 :偶置換 sgn(σ)=-1 :奇置換 Sn:n文字の置換全体   偶置換、奇置換 sgn(σ)=1    :偶置換 sgn(σ)=-1   :奇置換   置換全体の集合 Sn:n文字の置換全体 Snの元の個数=n!(=n個の順列の個数) 例) S3={ε, (1 2), (2 3), (1 3), (1 2 3), (1 3 2)}

det(A)=Σ sgn(σ)a1σ(1)a2σ(2)・・・anσ(n)    行列式の定義と性質(1)   行列式 n次正方行列 A=[aij] det(A)=Σ sgn(σ)a1σ(1)a2σ(2)・・・anσ(n) σ∈ Sn 例) a11 a12 a21 a22 = sgn(ε)a11a22 + sgn((1 2))a12a21 = a11a22 - a12a21 a11 a12 a13 a21 a22 a23 a31 a32 a33 = a11a22a33 +a12a23a31 + a13a21a32 -a12a21a33 -a11a23a32 -a13a22a31

サラスの方法 a11 a12 a13 a21 a22 a23 a31 a32 a33 a11 a12 a21 a22 ー + + + + ー ー ー a11 a12 a13 a21 a22 a23 a31 a32 a33 a11 a12 a13 a21 a22 a23 a31 a32 a33 ー ー ー + + +

det(A)=Σ sgn(σ)a1σ(1)a2σ(2)・・・anσ(n) 定理3.2.1 a11 a12 ・・・ a1n a22 ・・・ a2n 0  a22 ・・・ a2n =a11 ・・・ ・・・ ・・・ ・・・ ・・・ an2 ・・・ ann 0  an2 ・・・ ann det(A)=Σ sgn(σ)a1σ(1)a2σ(2)・・・anσ(n) σ     =Σ sgn(σ)a1σ(1)a2σ(2)・・・anσ(n) σ(1)=1     =a11 Σ sgn(σ) a2σ(2)・・・anσ(n) σ(1)=1 a22 ・・・ a2n =a11 ・・・ ・・・ an2 ・・・ ann

3 1 2 2 3 0 2 3 = 3 = 3(2・4ー1・3) = 15 1 4 0 1 4 上三角行列の行列式 a11 a12 ・・・ a1n a22 ・・・ a2n 0  a22 ・・・ a2n 0  ・ 0  0  = a11 =・・・= a11a22 ・・・ann ・ ・・・ ・ ・ ・・・ ・ ・ ・・・ ・・・ ・・・ ・ ・ ・ ・ 0 ・・・0 ann 0  0 ・・・0 ann |E|=1

Σ sgn(σ)a1σ(1) ・・・caiσ(i)・・・anσ(n) 定理3.2.2 (1)1つの行をc倍すると行列式はc倍になる。 a11  ・・・ a1n a11  ・・・ a1n ・・・ ・・・ ・・・ ・・・ cai1 ・・・ cain = c ai1 ・・・  ain ・・・ ・・・ ・・・ ・・・ an1  ・・・ ann an1  ・・・ ann Σ sgn(σ)a1σ(1) ・・・caiσ(i)・・・anσ(n) σ =cΣ sgn(σ)a1σ(1) ・・・aiσ(i)・・・anσ(n) σ

Σ sgn(σ)a1σ(1) ・・・(biσ(i)+ciσ(i))・・・anσ(n) 定理3.2.2 (2)第i行が2つのベクトルの和である行列の行列    式は、他の行は同じで第i行に各々の行ベクトル    をとった行列の行列式の和になる。 a11  ・・・ a1n a11・・・a1n a11・・・a1n ・・・ ・・・ ・・・ ・・・ ・・・ ・・・ bi1+ci1・・・bin+cin = + bi1・・・ bin ci1・・・cin ・・・ ・・・ ・・・ ・・・ ・・・ ・・・ an1  ・・・ ann an1・・・ann an1 ・・・ann Σ sgn(σ)a1σ(1) ・・・(biσ(i)+ciσ(i))・・・anσ(n) σ =Σ sgn(σ)a1σ(1) ・・・biσ(i)・・・anσ(n) σ +Σ sgn(σ)a1σ(1) ・・・ciσ(i)・・・anσ(n) σ

-1 2 0 -1 2 0 -1 2 0 a+3 b+6 c+9 = a b c + 3 6 9 7 2 4 7 2 4 7 2 4 -1 2 0 -1 2 0 = a b c + 3 1 2 3 7 2 4 7 2 4

Σ sgn(σ)a1σ(1) ・・・ajσ(i)・・・aiσ(j)・・・anσ(n) 定理3.2.3 (1)2つの行を入れ替えると行列式は-1倍になる。 (2) 2つの行が等しい行列の行列式は0である。 a11 ・・・ a1n a11 ・・・ a1n ・・・・・ ・・・・・ aj1 ・・・  ajn ai1 ・・・  ain i → ← i ・・・・・ ・・・・・ = - j → ai1 ・・・  ain aj1 ・・・  ajn ← j ・・・・・ ・・・・・ an1 ・・・ ann an1 ・・・ ann τ=σ(i j) とする Σ sgn(σ)a1σ(1) ・・・ajσ(i)・・・aiσ(j)・・・anσ(n) σ =-Σ sgn(τ)a1τ(1) ・・・ajτ(j)・・・aiτ(i)・・・anτ(n) τ

2 3 1 2 3 1 4 6 2 = 2 2 3 1 = 0 1 6 7 1 6 7 0 0 1  3 -1 1 0 2 2 = ー 0 2 2 = ー6 3 -1 1  0 0 1

定理3.2.4  行列の1つの行に他の行の何倍かを加えても、行列式の値は変わらない。 a11 ・・・ a1n a11 ・・・ a1n ・・・・・ ・・・・・ ai1+caj1・・・ain+cajn ai1 ・・・  ain i → ← i ・・・・・ ・・・・・ = j → aj1 ・・・  ajn aj1 ・・・  ajn ← j ・・・・・ ・・・・・ an1 ・・・ ann an1 ・・・ ann a11 ・・・ a1n a11 ・・・ a1n a11 ・・・ a1n ・・・・・ ・・・・・ ・・・・・ ai1+caj1・・・ain+cajn ai1 ・・・  ain aj1 ・・・  ajn ・・・・・ ・・・・・ ・・・・・ = + c aj1 ・・・  ajn aj1 ・・・  ajn aj1 ・・・  ajn ・・・・・ ・・・・・ ・・・・・ an1 ・・・ ann an1 ・・・ ann an1 ・・・ ann

1 3 4 1 3 4 1 15 -2 -5 7 = 0 1 15 = 11 11 -3 2 -1 0 11 11 1 15 1 15 =11 = 11 11 11 0 -14 =11・(-14) = ー154