Прямоугольник | сайт посвященный точным наукам

Подстановки, перестановки

Posted by admin on 23 Июль 2010 with Comments Closed
in Лекции по алгебре
as алгебра, лекции, обучение, уравнения, формулы

Перестановки и транспозиции

Рассмотрим перестановку двух элементов i и j, $i\neq j$ , в перестановке (i₁,…,i_n) (все остальные элементы, отличные от i, j, остаются на своих местах). Эта процедура называется транспозицией перестановки (i₁,…,i_n).

Лемма 5.2.1.

Умножение слева (i j)fподстановки
$f = \begin{pmatrix} i_1 & ... & i_n\\ j_1 & ... & j_n \end{pmatrix}$

на цикл (i j) длины 2 приводит к транспозиции элементов i и j в нижней строке (перестановке) (j₁,…,j_n).
Умножение справа f(i j) подстановки
$f = \begin{pmatrix} i_1 & ... & i_n\\ j_1 & ... & j_n \end{pmatrix}$

на цикл (i j) длины 2 приводит к транспозиции элементов i и j в верхней строке (перестановке) (i₁,…,i_n).

Доказательство.

$\begin{mult} \begin{pmatrix} ... & i & ... & j & ...\\ ... & j & ... & i & ... \end{pmatrix} \begin{pmatrix} i_1 & ... & i_k & ... & i_l & ... & i_n\\ j_1 & ... & j_k=i & ... & j_l=j & ... & j_n \end{pmatrix}={} \\ {}= \begin{pmatrix} i_1 & ... & i_k & ... & i_l & ... & i_n\\ j_1 & ... & j=j_l & ... & i=j_k & ... & j_n \end{pmatrix}. \end{mult}$
$\begin{mult} \begin{pmatrix} i_1 & ... & i_r=i & ... & i_s=j & ... & i_n\\ j_1 & ... & j_r & ... & j_s & ... & j_n \end{pmatrix} \begin{pmatrix} ... & i & ... & j & ...\\ ... & j & ... & i & ... \end{pmatrix}={} \\ {}= \begin{pmatrix} i_1 & ... & j=i_s & ... & i=i_r & ... & i_n\\ j_1 & ... & j_r & ... & j_s & ... & j_n \end{pmatrix}. \end{mult}$

Лемма 5.2.2 (о списке перестановок). Все n! перестановок из n элементов {1,2,…,n} можно расположить в список, начиная с произвольной перестановки (i₁,i₂,…,i_n), так, что каждая следующая перестановка в этом списке получается из предыдущей с помощью некоторой транспозиции двух элементов.

Доказательство. Проведем индукцию по n. Начало индукции n=2, n!=2, наши списки:

$\begin{array}{@{}l@{}} (1, 2)\\ (2, 1) \end{array}\,;\quad \begin{array}{@{}l@{}} (2, 1)\\ (1, 2) \end{array}.$

Пусть наше утверждение верно для всех k, k<n. Пользуясь этим, создадим первый блок из различных (n-1)! перестановок с i_1 на первом месте (т. е. перестановок из элементов {i₂,…,i_n}), при этом каждая следующая перестановка получается из предыдущей с помощью транспозиции:

$\scriptstyle{(n-1)!} \left\{ \begin{array}{@{}l@{}} (i_1,i_2,...,i_n),\\ \quad \vdots\\ (i_1,...,i_2,...). \end{array} \right.$

Совершая транспозицию i₁ и i₂ в последней перестановке первого блока и повторяя наше рассуждение, построим второй блок из различных (n-1)! перестановок с i₂ на первом месте (т. е. перестановок элементов {i₁,i₃,…,i_n}), при этом каждая следующая перестановка получается из предыдущей применением транспозиции:

$\scriptstyle{(n-1)!} \left\{ \begin{array}{@{}l@{}} (i_2,...),\\ \quad \vdots\\ (i_2,...,i_3,...). \end{array} \right.$

Продолжая этот процесс, получим n блоков из (n-1)! перестановок каждый, всего n! перестановок. Они все различны: в одном блоке по индуктивному предположению, в разных блоках перестановки различаются на первом месте. Таким образом, в этом списке присутствуют все n! перестановок из n элементов, при этом каждая следующая получается из предыдущей с помощью одной транспозиции.

Следствие 5.2.3. От любой перестановки (i₁,…,i_n) можно перейти к любой другой перестановке (j₁,…,j_n) с помощью конечного числа транспозиций.

Доказательство. В списке с началом (i₁,…,i_n) надо найти перестановку (j₁,…,j_n).

Следствие 5.2.4. Каждая подстановка

$\tau= \begin{pmatrix} 1 & 2 & ... & n\\ k_1 & k_2 & ... & k_n \end{pmatrix} \in S_n$

является произведением $\tau = \tau_r...\tau_1$ конечного числа циклов $\tau_i$ длины два (называемых также транспозициями). Таким образом, циклы длины два (транспозиции) дают одну из систем образующих группы S_n

Доказательство. Составим список перестановок, начинающийся с перестановки (1,2,…,n), в котором каждая l-я перестановка получается из (l-1)-й транспозицией элементов i_l-1 и j_l-1, и найдем в нем нашу перестановку (k₁,…,k_n) из канонической записи подстановки $\tau$ (пусть она занимает (r+1)-е место). Тогда (по лемме об умножении слева на цикл длины два)

$(i_r\quad j_r)... (i_1\quad j_1) \begin{pmatrix} 1 & 2 & ... & n\\ 1 & 2 & ... & n \end{pmatrix} = \begin{pmatrix} 1 & 2 & ... & n\\ k_1 & k_2 & ... & k_n \end{pmatrix} = \tau,$

т. е. $\tau=\tau_r...\tau_1$ , где $\tau_r=(i_r\quad j_r),..., \tau_1=(i_1\quad j_1)$ .

Замечание 5.2.5. Ясно, что представление подстановки $\tau\=\tau_1...\tau_r$ в виде произведения транспозиций возможно разными способами (например, (1 2)=(1 2)³).

Линейные пространства

Posted by admin on 23 Июль 2010 with Comments Closed
in Лекции по алгебре
as алгебра, лекции, обучение, уравнения, формулы

Вывод свойств линейного пространства из аксиом

Пусть K — поле (например, K= R — поле действительных чисел). Многочисленные конкретные примеры линейных пространств, с которыми мы уже столкнулись (линейные пространства строк Kⁿ, столбцов $\hat K^n$ , пространства прямоугольных и квадратных матриц $\mM_{m,n}(K)$ и $\mM_{n}(K)$ , пространство многочленов K[x], пространство непрерывных вещественных функций C[0,1] на отрезке [0,1] и т. д.), оправдывают введение и рассмотрение понятия линейного пространства _K V над полем K как множества V с операцией сложения ( $V\times V\to V$ , $(a,b)\mapsto a+b$ ) и операциями умножения на элементы $c\in K$ ( $V\to V$ , $v\mapsto cv$ ), удовлетворяющими следующим условиям:

I.1) ассоциативность сложения (т. е. (u+v)+w=u+(v+w) для всех $u,v,w\in V$ );

I.2) коммутативность сложения (т. е. u+v=v+u для всех $u,v\in V$ );

I.3) существование нейтрального элемента 0 для операции сложения (т. е. v+0=v для всех $v\in V$ );

I.4) существование противоположного элемента -v для всякого $v\in V$ (т. е. v+(-v)=0);

II.1) $1\cdot v=v$ для всех $v\in V$ ;

II.2) (rs)v=r(sv) для всех $r,s\in K$ , $v\in V$ ;

III.1) r(v₁+v₂)=rv₁+rv₂ для всех $r\in K$ , $v_1,v_2\in V$ ;

III.2) (r+s)v=rv+sv для всех $r,s\in K$ , $v\in V$ .

Приведем вывод ряда следствий из этих аксиом линейного пространства (хотя, конечно, в каждом конкретном случае они достаточно очевидны).

Уравнение u+x=v для $u,v\in {}_K V$ имеет, причем единственное, решение x=(-u)+v.

Действительно, прибавляя -u к левой и правой части, получаем, что x = (-u)+v. С другой стороны, u+(-u)+v=v.
Если x+x=x для $x\in {}_K V$ , то x=0.

Действительно, прибавляя к левой и правой части противоположный элемент -x, получаем, что x=(-x)+x+x=(-x)+x=0.
0v=0 для любого $v\in {}_K V$ .

Действительно, если x=0v (здесь $0\in K$ ), то x+x=0v+0v=(0+0)v=0v=x, и поэтому $x=0\in {}_K V$ .
r0=0 для $r\in K$ , $0\in V$ .

Действительно, если x=r0, то x+x=r0+r0=r(0+0)=r0=x, и поэтому x=0.
(-1)v=-v для всех $v\in V$ .

Действительно, (-1)v+v=(-1+1)v=0v=0, т. е. (-1)v=-v.
rv=0 для $r\in K$ , $v\in V$ тогда и только тогда, когда либо r=0, либо v=0.

Действительно, если $r\neq 0$ , то в поле K существует элемент $r^{-1}\in K$ , и поэтому v=1v=r^-1rv=r^-10=0.
r(u-v)=ru-rv для всех $r\in K$ , $u,v\in V$ .

Действительно, r(u-v)+rv=r(u-v+v)=ru, т. е. r(u-v)=ru-rv.
-(-v)=v для всех $v\in V$ .

Действительно, v+(-v)=0, и поэтому -(-v)=v.

Линейная зависимость в линейных пространствах

Пусть _K V — линейное пространство над полем K. Если $v_1,...,v_r\in V$ , $k_1,...,k_r\in K$ , то элемент

$k_1v_1+...+k_rv_r\in V$

называется линейной комбинацией элементов v₁,…,v_r с коэффициентами $k_1,...,k_r\in K$ .

Систему элементов $v_1,...,v_r \in {}_K V$ назовем линейно зависимой, если найдутся элементы $k_1,...,k_r\in K$ такие, что

а) не все k_i равны нулю (т. е. хотя бы один элемент k_i отличен от нуля);

б) k₁v₁+k₂v₂+…+k_rv_r=0.

Для краткости в этой ситуации мы будем говорить, что «нетривиальная» линейная комбинация элементов v₁,…,v_r равна нулю (конечно, тривиальная линейная комбинация всегда равна нулю, 0v₁+…+0 v_r=0).

Система элементов $v_1,...,v_r\in {}_K V$ называется линейно независимой, если она не является линейно зависимой, это означает, что из равенства

$k_1v_1+...+k_rv_r=0,\quad k_1,...,k_r\in K,$

следует, что k₁=k₂=…=k_r=0.

Теорема 9.2.1. Система элементов $v_1,...,v_r \in {}_K V$ линейно зависима тогда и только тогда, когда для некоторого i, $1\le i\le r$ ,

$v_i=\sum_{j\neq i}l_jv_j,\quad l_j\in K$

(т. е. элемент v_i является линейной комбинацией остальных элементов системы v₁,…,v_r).

Доказательство.

Пусть система v₁,…,v_r линейно зависима, т. е.
$k_1v_1+...+k_rv_r=0,\quad k_i\neq 0.$

Тогда

$v_i=\sum_{j\neq i}\frac{(-k_j)}{k_i}v_j.$
Если
$v_i=\sum_{j\neq i}l_jv_j,$

то

$\sum_{j\neq i} l_jv_j+(-1)v_i= v_i+(-1)v_i = 0,$

т. е. система v₁,…,v_r линейно зависима, поскольку $-1\neq 0$ .

Пример 9.2.2. Если в системе элементов $v_1,...,v_r\in {}_K V$ есть нулевой элемент, скажем, v_i=0, то система v₁…,v_r линейно зависима.

Действительно, 0 v₁+…+1 v_i+…+0 v_r=0, или, другим способом, $v_i=0=\sum\limits_{j\neq i}0 v_j$ .

Пример 9.2.3. Если v_i=v_j для $i\neq j$ , то система $v_1,...,v_r\in {}_K V$ линейно зависима.

Действительно, 0 v₁+…+1 v_i+…+(-1) v_j+…+0 v_r=0, или, иначе, $v_i=v_j+\sum\limits_{\substack{k\neq i\\ k\neq j}}0 v_k$ .

Пример 9.2.4. Система строк $\varepsilon_1,...,\varepsilon_n\in {}_K K^n$ , где

$\begin{align*} & \varepsilon_1=(1,0,...,0),\\ & \varepsilon_2=(0,1,...,0),\\ & \quad ...\\ & \varepsilon_n=(0,0,...,1), \end{align*}$

линейно независима. Кроме того, любая строка $\alpha=(k_1,...,k_n)\in {}_K K^n$ является линейной комбинацией элементов $\varepsilon_1,...,\varepsilon_n$ , а именно, $\alpha=(k_1,...,k_n)=k_1\varepsilon_1+...+k_n\varepsilon_n$

Действительно,

$k_1\varepsilon_1+...+k_n\varepsilon_n=(k_1,...,k_n),$

и поэтому если

$k_1\varepsilon_1+...+k_n\varepsilon_n=(0,...,0),$

то k₁=k₂=…=k_n=0, следовательно, система строк $\{\varepsilon_1,...,\varepsilon_n\}$ линейно независима.

Пример 9.2.5. Пусть $v_1,v_2,v_3\in {}_{ R} V$ — линейно независимая система в линейном пространстве _R V. Тогда u₁=v₁+v₂, u₂=v₁+v₃, u₃=v₂+v₃ - также линейно независимая система.

Действительно, если k₁ u₁ + k₂ u₂ + k₃ u₃ = 0, то

$\begin{mult} 0 = k_1 (v_1+v_2) + k_2 (v_1+v_3) + k_3 (v_2+v_3) ={} \\ {}=(k_1+k_2)v_1 + (k_1+k_3)v_2 + (k_2+k_3)v_3, \end{mult}$

поэтому

$\left\{ \begin{array}{@{}l@{}} k_1 + k_2 = 0,\\ k_1 + k_3 = 0,\\ k_2 + k_3 = 0. \end{array} \right.$

Следовательно, k₁ = 0, k₂ = 0, k₃ = 0, и система элементов u₁,u₂,u₃ линейно независима.

Упражнения 9.2.6.

Подсистема линейно независимой системы линейно независима.
Если подсистема линейно зависима, то линейно зависима и вся система.

Замечание 9.2.7. Для системы строк в Kⁿ

$\begin{align*} & \alpha_1 = (a_{11}, ..., a_{1n}),\\ & \quad ...\\ & \alpha_r = (a_{r1}, ..., a_{rn}) \end{align*}$

вопрос о ее линейной зависимости равносилен существованию ненулевого решения (k₁,…,k_r) следующей однородной системы линейных уравнений:

$\left\{ \begin{array}{@{}l@{}} a_{11} x_1 + ... + a_{r1} x_r = 0,\\ \dotfill\\ a_{1n} x_1 + ... + a_{rn} x_r = 0 \end{array} \right.$

с транспонированной матрицей A^*

, где

$A = \begin{pmatrix} a_{11} & ... & a_{1n}\\ \hdotsfor{3}\\ a_{r1} & ... & a_{rn} \end{pmatrix} = \begin{pmatrix} \alpha_1\\ \vdots\\ \alpha_r \end{pmatrix}.$

Таким образом, метод Гаусса дает нам в этом случае алгоритмическое решение задачи о линейной зависимости строк.

Теорема 9.2.8. Пусть $A=(a_{ij}) \in \mM_n(K)$ — квадратная матрица. Тогда следующие условия равносильны:

|A|=0 ;
система строк A₁, …, A_n матрицы A линейно зависима (в пространстве строк Kⁿ);
система столбцов $\hat A_1, ...,\hat A_n$ матрицы A линейно зависима (в пространстве столбцов $\hat K^n$ ).

Доказательство.

Если строки матрицы A линейно зависимы, скажем, i -я строка A_i является линейной комбинацией остальных, $A_i = \smash[b]{\sum\limits_{j \neq i} l_j A_j}$ , то, как мы показали, |A|=0, т. е. $2) \Longrightarrow 1)$ .
Пусть |A|=0. Тогда k₁ A₁ + … + k_n A_n = 0 в том и только в том случае, если (k₁, …, k_n) является решением однородной системы линейных уравнений с матрицей A^*. Так как |A^*| = |A| = 0, то существует ненулевое решение (k₁, …, k_n), т. е. система строк A₁, …, A_n матрицы A линейно зависима. Итак, $1) \Longrightarrow 2)$ .
Так как |A^*| = |A|, то $1) \iff 3)$ .

Задача 9.2.9. Пусть $A=(a_{ij})\in M_n(K)$ , $B=(b_{ij})\in M_n(K)$ , где b_ij=A_ji. Покажите, что если |A|=0, то |B|=0.

Теорема 9.2.10. Любая система из m строк в Kⁿ при m > n линейно зависима.

Доказательство. Если

$\begin{align*} & \alpha_1 = (a_{11}, ..., a_{1n}),\\ & \quad ...\\ & \alpha_m = (a_{m1}, ..., a_{mn}), \end{align*}$

то равенство $k_1 \alpha_1 + ... + k_m \alpha_m = 0$ равносильно тому, что (k₁, …, k_m) является решением следующей однородной системы линейных уравнений:

$\left\{ \begin{array}{@{}l@{}} a_{11} x_1 + ... + a_{m1} x_m = 0,\\ \dotfill\\ a_{1n} x_1 + ... + a_{mn} x_m = 0. \end{array} \right.$

Так как число n уравнений меньше числа m переменных, то однородная система обладает ненулевым решением, т. е. система $\alpha_1, ..., \alpha_m$ линейно зависима.

Следствие 9.2.11. Если система $\alpha_1, ..., \alpha_r \in K^n$ линейно независима, то $r \leq n$ .

Лемма 9.2.12. Если система элементов $\alpha_1,...,\alpha_r\in {}_K V$ линейного пространства _K V над полем K линейно независима, $\beta \in {}_K V$ и система $\alpha_1, ..., \alpha_r, \beta$ линейно зависима, то $\beta$ является линейной комбинацией элементов $\alpha_1,...,\alpha_r$ .

Доказательство. Пусть

$k_1 \alpha_1 + ... + k_r \alpha_r + k_{r+1} \beta = 0, \quad k_1,...,k_{r+1}\in K,$

где не все k_i, $1 \leq i \leq r+1$ , равны нулю. Если бы k_r+1=0, то нетривиальная линейная комбинация $k_1 \alpha_1 + ... + k_r \alpha_r = 0$ , равная нулю, означала бы, что система $\alpha_1, ..., \alpha_r$ линейно зависима, что противоречит предположению.

Итак, $k_{r+1} \neq 0$ , и поэтому

$\beta = \frac{-k_1}{k_{r+1}} \alpha_1 + ... + \frac{-k_r}{k_{r+1}} \alpha_r.$

Лемма 9.2.13 (единственность представления элемента линейного пространства KV в виде линейной комбинации линейно независимой системы элементов). Пусть $\{\alpha_1,...,\alpha_r\}$ — линейно независимая система элементов линейного пространства _K V и

$\beta=k_1\alpha_1+...+k_r\alpha_r=k'_1\alpha_1+...+k'_r\alpha_r,\quad k_i,k'_i\in K.$

Тогда k₁=k’₁,…,k_r=k’_r

Доказательство. Действительно,

$(k_1-k'_1)\alpha_1+...+(k_r-k'_r)\alpha_r= 0,$

и поэтому k₁ — k’₁=0,…,k_r — k’_r=0.

Системы линейных уравнений

Posted by admin on 23 Июль 2010 with Comments Closed
in Лекции по алгебре
as алгебра, лекции, обучение, уравнения, формулы

В средней школе рассматривались линейные уравнения ax=b и системы линейных уравнений

$\left\{ \begin{array}{@{}l@{}} ax+by=e,\\ cx+dy=f, \end{array} \right.$

где $a, b, c, d, e, f \in R$ — действительные числа.

В излагаемой теории систем линейных уравнений мы будем совершать с коэффициентами операции сложения и умножения, а также делить (т. е. умножать на обратный элемент) на ненулевой элемент. Таким образом, естественно рассматривать системы линейных уравнений с коэффициентами из произвольного поля K. Для понимания основных моментов теории систем линейных уравнений можно считать, что K — поле R действительных чисел.

Наша ближайшая цель — исследовать системы m линейных уравнений общего вида от n переменных x₁, x₂, x₃,…,x_n

$\begin{equation}\label{eq1.1} \left\{ \begin{array}{@{}l@{}} a_{11}x_1+a_{12}x_2+...+a_{1n}x_n=b_1,\\ a_{21}x_1+a_{22}x_2+...+a_{2n}x_n=b_2,\\ \dotfill\\ a_{m1}x_1+a_{m2}x_2+...+a_{mn}x_n=b_m, \end{array} \right. \end{equation}$

(3.1)

где $m,n \in N$ , $a_{ij},b_i \in K$

Таким образом, i-е уравнение, $1\le i \le m$ , нашей системы записывается в виде a_i1x₁+a_i2x₂+ … +a_inx_n=b_i (a_ij — коэффициент при переменной x_j в i-м уравнении, b_i — свободный член i-го уравнения), или, кратко,

$\sum_{j=1}^n a_{ij}x_j=b_i.$

Прямоугольная $(m \times n)$ — таблица коэффициентов $a_{ij} \in K$ (m строк, n столбцов)

$A= \begin{pmatrix} a_{11}& a_{12}& a_{13} &... &a_{1n}\\ a_{21}& a_{22}& a_{23} &... &a_{2n}\\ \hdotsfor{5}\\ a_{m1}& a_{m2}& a_{m3} &... &a_{mn} \end{pmatrix}$

называется матрицей коэффициентов системы линейных уравнений (3.1), а прямоугольная $(m \times (n+1))$ -матрица (m строк, n+1 столбец)

$A(a_{ij}|b_i)= \left(\left. \begin{matrix} a_{11} &a_{12} &a_{13} &... &a_{1n}\\ a_{21} &a_{22} &a_{23} &... &a_{2n}\\ \hdotsfor{5}\\ a_{m1} &a_{m2} &a_{m3} &... &a_{mn} \end{matrix} \right| \begin{matrix} b_1\\ b_2\\ ...\\ b_m \end{matrix} \right)$

называется расширенной матрицей системы линейных уравнений (3.1) (уже полностью ее определяющей).

Если m=n (число уравнений равно числу переменных), то система линейных уравнений (и матрица $A=\left( \begin{smallmatrix} a_{11}&... & a_{1n}\\ \multispan{3}{\dotfill}\\ a_{n1}&... & a_{nn} \end{smallmatrix}\right)$ ее коэффициентов при переменных) называется квадратной.

В квадратной матрице

$\begin{pmatrix} a_{11}& ... &a_{1n}\\ \hdotsfor{3}\\ a_{n1}& ... &a_{nn} \end{pmatrix}$

можно определить диагональ и побочную диагональ:

$\begin{pmatrix} a_{11}\\ &a_{22}\\ &&\ddots\\ &&&a_{nn} \end{pmatrix}; \quad \begin{pmatrix} \phantom{a_{11}}&&&a_{1n}\\ &\phantom{a_{22}}&a_{2(n-1)}\\ &\revddots&&\phantom{\ddots}\\ a_{n1}&&\phantom{a_{nn}} \end{pmatrix}.$

Если в системе линейных уравнений b₁=…=b_m=0, то система называется однородной.

Совокупность решений системы линейных уравнений

Определение 3.1.1. Решением системы линейных уравнений (3.1) называется строчка n элементов поля K (l₁,…,l_n), $l_i \in K$ , такая, что при подстановке в i-е уравнение, $1\leq i \leq m$ , l₁ вместо x₁, l₂ вместо x₂,…,l_i вместо x_i,…,l_n вместо x_n получаем b_i (свободный член i-го уравнения), т. е.

$\sum_{j=1}^{n} a_{ij}l_j=b_i.$

Таким образом, строчка (l₁, …, l_n) является решением, если значения l₁, …, l_n соответственно для x₁, …, x_n удовлетворяют всем m уравнениям системы (3.1).

Через X обозначим совокупность всех решений системы линейных уравнений (3.1).

Замечание 3.1.2.

$X \subseteq K^n$ (т. е. совокупность всех решений является подмножеством в множестве Kⁿ всех строк длины n элементов из поля K).
Возможно, что $X=\varnothing$ (т. е. система линейных уравнений не имеет решений), в этом случае система называется несовместной.
Если $X\ne\varnothing$ (т. е. система имеет решение), то система (3.1) называется совместной. Например, однородная система линейных уравнений всегда имеет нулевое решение, $(0,...,0)\in X\subseteq K^n$ .

Если система имеет только одно решение (|X|=1), то система называется определенной. Если |X| > 1, то совместная система называется неопределенной. Итак, для числа решений имеются следующие возможности:

Число решений
0	1	>1
Система несовместная, $X=\varnothing$	Система определенная, \|X\|=1	Система неопределенная, \|X\|>1
Примеры
$\left\{ \begin{array}{@{}l@{}} x_1+x_2=0,\\ x_1+x_2=1 \end{array} \right.$ $X=\varnothing$ несовместная с. л. у.	$\left\{ \begin{array}{@{}l@{}} x_1+x_2=1,\\ x_1-x_2=0 \end{array} \right.$ $X=\left\{\left(\frac{1}{2},\frac{1}{2}\right)\right\}$ $\|X\|=1$ определенная с. л. у.	$\left\{ \begin{array}{@{}l@{}} x_1+x_2=1 \end{array} \right.$ $x_2=c\in K$ , $x_1=1-c$ $X=\{ (1-c,c)\mid\allowbreak c \in K \}$ $\|X\|=\|K\|>1$ неопределенная с. л. у.

Основная задача исследования систем линейных уравнений (3.1) заключается в описании (нахождении) множества решений $X \subseteq K^n$ (в частности, определения, к какому типу принадлежит система (3.1): несовместная, определенная, неопределенная).

Решение системы линейных уравнений

Posted by admin on 23 Июль 2010 with Comments Closed
in Лекции по алгебре
as алгебра, лекции, обучение, уравнения, формулы

Чтобы выяснить имеет ли составленная система решение или нет, а, если имеет решение, то их количество, применяют следующую теорему.

Теорема 1. Если ранг матрицы системы равен рангу расширенной матрицы системы, то такая система совместна и имеет хотя бы одно не нулевое решение.

Пример. Определить совместность системы

$\left. \begin{aligned} & 3x_1+4x_2=7 \\ & 3x_1+4x_2=12 \end{aligned} \right\}.$

Решение. Составим матрицу системы $\begin{pmatrix} 3 & 4 \\ 3 & 4 \end{pmatrix}$ и определим ее ранг (т.е. число независимых строк или столбцов:

$rang \begin{pmatrix} 3 & 4 \\ 3 & 4 \end{pmatrix} =rang \begin{pmatrix} 3 & 4 \end{pmatrix} =1$

Составим расширенную матрицу системы

$\left( \begin{aligned} &3 && 4 \\ &3 && 4 \end{aligned} \right. \left| \begin{aligned} &7 \\ &12 \end{aligned} \right)$

и определим ее ранг (т.е. число независимых строк или столбцов:

$rang \left( \begin{aligned} &3 && 4 \\ &3 && 4 \end{aligned} \right. \left| \begin{aligned} &7 \\ &12 \end{aligned} \right) =2$

Как видим, ранг обычной матрицы не равен рангу расширенной, следовательно системы несовместна, т.е. не имеет ни одно решения.

Пример. Определить совместность системы

$\left. \begin{aligned} & 3x_1+4x_2=7 \\ & 3x_1+4x_2=7 \end{aligned} \right\}.$

Решение. Составим матрицу системы

$\begin{pmatrix} 3 & 4 \\ 3 & 4 \end{pmatrix}$

и определим ее ранг (т.е. число независимых строк или столбцов:

$rang \begin{pmatrix} 3 & 4 \\ 3 & 4 \end{pmatrix} =rang \begin{pmatrix} 3 & 4 \end{pmatrix} =1$

Составим расширенную матрицу системы

$rang \left( \begin{aligned} &3 && 4 \\ &3 && 4 \end{aligned} \right. \left| \begin{aligned} &7 \\ &7 \end{aligned} \right)$

и определим ее ранг (т.е. число независимых строк или столбцов:

$rang \left( \begin{aligned} &3 && 4 \\ &3 && 4 \end{aligned} \right. \left| \begin{aligned} &7 \\ &7 \end{aligned} \right) =rang \left( \begin{aligned} &3 & 4 \end{aligned} \right. \left| \begin{aligned} 7 \end{aligned} \right) =1$

Как видим, ранг обычной матрицы равен рангу расширенной, следовательно системы совместна, т.е. имеет хотя бы одно решение.

Заметим, что положительный ответ на вопрос «совместна ли система?» не гарантирует единственность возможного решения.

Виды систем линейных уравнений.

Определение 5. Если система

$\left. \begin{gathered} a_{11}x_1+a_{12}x_2 + \ldots + a_{1n}x_n = 0 \\ a_{21}x_1+a_{22}x_2 + \ldots + a_{2n}x_n = 0 \\ \ldots \\ a_{k1}x_1+a_{k2}x_2 + \ldots + a_{kn}x_n = 0 \end{gathered} \right\}$

(3.2)

совместна, то она имеет бесконечное множество ненулевых (невырожденных) решений и называется однородной системой.

Однородная система всегда совместна и всегда имеет хотя бы одно нулевое решение.

Определение 6. Если система имеет единственное нулевое решение, то такая система называется вырожденной.

Определение 7. Если система имеет количество уравнений меньшее, чем количество неизвестных, то такая система называется недоопределенной, а если количество уравнений больше, чем количество неизвестных, то – переопределенной.

Матрицы таких систем (недоопределенной и переопределенной) как правило прямоугольные. Решаются такие системы специальными методами, относящимися к разделу линейного программирования.

Системы линейных уравнений

Posted by admin on 23 Июль 2010 with Comments Closed
in Лекции по алгебре
as алгебра, лекции, обучение, уравнения, формулы

В общем случае линейная система, составленная из К линейных уравнений относительно n неизвестных примет вид:

$\left. \begin{gathered} a_{11}x_1+a_{12}x_2 + \ldots + a_{1n}x_n = b_1 \\ a_{21}x_1+a_{22}x_2 + \ldots + a_{2n}x_n = b_2 \\ \ldots \\ a_{k1}x_1+a_{k2}x_2 + \ldots + a_{kn}x_n = b_k \end{gathered} \right\}$

(3.1)

где x₁, x₂, …, x_n — неизвестные; a₁₁, a₁₂, …, a_kn — коэффициенты при неизвестных; b₁, b₂, …, b_k — свободные члены.

Определение 1. Решением системы (1) называется совокупность из n чисел (с₁, с₂, …, с_n), которые, будучи подставленными в систему (1) на место неизвестных x₁, x₂, …, x_n, обращают все уравнения системы в истинные равенства.

Не всякая система вида (1) имеет решение. Например, очевидно, что система

$\left. \begin{aligned} & 3x_1+4x_2=7 \\ & 3x_1+4x_2=12 \end{aligned} \right\}$

не имеет ни одного решения. А вот система

$\left. \begin{aligned} & 3x_1+4x_2=7 \\ & 3x_1+4x_2=7 \end{aligned} \right\}$

имеет бесконечное множество решений. Поэтому, прежде чем начать решать составленную систему, необходимо выяснить, есть ли вообще решение. Это необходимо делать хотя бы потому, что в общем случае поиск решения системы уравнения оказывается долгим и сложным делом.

Определение 2. Систему уравнений (1), имеющую хотя бы одно решение, называют совместной, систему, не имеющую решений, - несовместной.

Определение 3. Решения $\left( c_1^{(1)}, c_2^{(1)}, \ldots c_n^{(1)} \right)$ и $\left( c_1^{(2)}, c_2^{(2)}, \ldots c_n^{(2)} \right)$ считают различными, если хотя бы одно из чисел $c_i^{(1)}$ не совпадает с соответствующим числом $c_i^{(2)}$ .

Например, система

$\left. \begin{aligned} & 3x_1+4x_2=0 \\ & 6x_1+8x_2=0 \end{aligned} \right\}$

имеет различные решения $c_1^{(1)}=c_2^{(1)}=0$ и $c_1^{(2)}=4; \; c_2^{(2)}=-3$ . Системы, имеющие хотя бы 2 различных решения, имеют бесконечное количество разных решений.

Определение 4. Если совместная система имеет единственное решение, то она называется определенной; если совместная система имеет по крайней мере два различных решения, то она называется неопределенной.

Четность перестановок и подстановок

Posted by admin on 23 Июль 2010 with Comments Closed
in Лекции по алгебре
as алгебра, лекции, обучение, уравнения, формулы

Будем говорить, что числа i и j в перестановке (…,i,…,j,…) образуют инверсию, если число i расположено левее, чем j, но i>j (в противном случае будем говорить, что числа i и j расположены в правильном порядке). Ясно, что сумма числа всех инверсией и числа всех порядков в любой перестановке из n чисел 1,2,…,n равна $C_n^2=\frac{n(n-1)}{2}$ .

Пример 5.4.1. Число инверсий в перестановке (1,2,…,n) равно нулю, в перестановке (n,n-1,…,2,1) равно $\frac{n(n-1)}{2}$ .

Удобный алгоритм подсчета числа инверсий: считаем, сколько инверсий образует 1 (все числа, находящиеся левее), после чего вычеркиваем 1 и переходим к 2 и т. д.

Теорема 5.4.2. Транспозиция в перестановке меняет четность числа инверсий.

Доказательство. Рассмотрим транспозицию элементов i и j:

$(...,i,...,j,...)\mapsto (...,j,...,i,...).$

Сначала рассмотрим случай «соседей»:

$(...,i,j,...)\mapsto (...,j,i,...).$

Так как при перестановке чисел i и j их отношение с числами, расположенными левее (как и правее) не изменяется, то число инверсий изменяется на единицу (т. е. $\pm 1$ ), следовательно, четность числа инверсий изменяется.

Если же между числами i и j находится k элементов, то последовательно переставляя i с правыми соседними элементами k раз, потом с j, затем переставляяk раз элемент j с левыми соседними элементами, мы, проведя k+1+k=2k+1 транспозиций соседних элементов, осуществим транспозицию чисел i и j. Таким образом, четность изменилась.

Следствие 5.4.3. Число четных перестановок при $n \geq 2$ равно числу нечетных перестановок и равно $\frac{n!}{2}$ .

Доказательство. Расположив все n! перестановок, начиная, например, с (1,2,…,n), в список, в котором каждая следующая перестановка получается из предыдущей одной транспозицией, мы видим, что четные перестановки чередуются с нечетными, поэтому число четных перестановок равно числу нечетных и равно $\smash[b]{\frac{n!}{2}}$ .

Четность подстановки

$\begin{pmatrix} i_1 & ... & i_n\\ j_1 & ... & j_n \end{pmatrix}$

определяется как четность суммы числа инверсий в верхней строчке и числа инверсий в нижней строчке.

Предложение 5.4.4. Четность подстановки $\sigma\in S_n$ не зависит от ее записи.

Доказательство. Если

$\sigma= \begin{pmatrix} i_1 & ... & i_n\\ \sigma(i_1) & ... & \sigma(i_n) \end{pmatrix} = \begin{pmatrix} i'_1 & ... & i'_n\\ \sigma(i'_1) & ... & \sigma(i'_n) \end{pmatrix}\text{ -}$

две записи подстановки $\sigma\in S_n$ , то, переходя конечным числом транспозиций от перестановки (i_1,…,i_n) к перестановке (i’₁,…,i’_n), переставляя при этом соответствующие «столбики»

$\begin{pmatrix} i\\ \sigma(i) \end{pmatrix},$

приходим от нижней строчки $(\sigma(i_1),...,\sigma(i_n))$ к строчке $(\sigma(i'_1),...,\sigma(i'_n))$ . Перестановка двух «столбиков» является транспозицией в верхней и в нижней строчках, следовательно, меняется четность в верхней и в нижней строчках, в итоге четность суммы числа транспозиций в верхней и в нижней строчке при перестановке двух «столбиков» не изменится.

Замечание 5.4.5. Подстановка, обратная к четной подстановке, четная. Действительно, если

$\sigma = \begin{pmatrix} i_1 & i_2 & ... & i_n\\ j_1 & j_2 & ... & j_n \end{pmatrix}$

четная, то

$\sigma^{-1} = \begin{pmatrix} j_1 & ... & j_n\\ i_1 & ... & i_n \end{pmatrix}$

четная.

Четность произведения подстановок

Возможность использовать произвольную запись подстановки удобна для рассмотрения произведения:

$\begin{pmatrix} i_1 & ... & i_n\\ j_1 & ... & j_n \end{pmatrix} \begin{pmatrix} 1 & 2 & ... & n\\ i_1 & i_2 & ... & i_n \end{pmatrix} = \begin{pmatrix} 1 & 2 & ... & n\\ j_1 & j_2 & ... & j_n \end{pmatrix},$

откуда следует

Лемма 5.5.1 (о четности произведения).

$\begin{array}[b]{|c|c|c|} \sigma & \tau & \sigma\tau\\ \hline \textup{ч} & \textup{ч} & \textup{ч}\\ \hline \textup{н} & \textup{ч} & \textup{н}\\ \hline \textup{ч} & \textup{н} & \textup{н}\\ \hline \textup{н} & \textup{н} & \textup{ч}\\ \end{array}\;.$

Рассмотрим отображение

$\begin{align*} & \varepsilon\colon \mS_n \to \{1,-1\},\\ & \varepsilon(\sigma) = \begin{cases} 1, & \text{если $\sigma$"--- чётная подстановка},\\ -1, & \text{если $\sigma$"--- нечётная подстановка}. \end{cases} \end{align*}$

Замечание 5.5.2. Напомним, что {1,-1} — коммутативная группа относительно операции произведения. Действительно, произведение является операцией на {1,-1}; эта операция ассоциативна и коммутативна; 1 — нейтральный элемент; (1)^-1=1, (-1)^-1=-1.

Следствие 5.5.3. Если $\sigma,\tau\in S_n$ , то:

$\varepsilon(\sigma\tau)=\varepsilon(\sigma)\varepsilon(\tau)$

(т. е. $\sigma: S_n\to \{1,-1\}$ — гомоморфизм групп);

$\varepsilon(\sigma)=\varepsilon(\sigma^{-1}).$

Следствие 5.5.4. Если $\sigma=\tau_1...\tau_k$ — разложение подстановки $\sigma\in S_n$ в произведение транспозиций $\tau_1,...,\tau_k$ , то $\varepsilon(\sigma)=(-1)^k$ .

Доказательство. Отметим только, что если $\tau=(i\quad j)$ — транспозиция, то $\varepsilon((i\quad j))=-1$ .

Упражнение 5.5.5. $\varepsilon((i_1\quad...\quad i_r))=(-1)^{r-1}$ для цикла (i_1… i_r) длины r, $r \geq 2$ .

Теорема 5.5.6. Четные подстановки A_n являются группой (подгруппой в группе подстановок S_n) $|A_n|=\frac{n!}{2}$ при $n \geq 2$ .

Доказательство. Так как произведение $\sigma\tau$ четных подстановок $\sigma,\tau\in A_n$ является четной подстановкой, то имеем операцию произведения на множестве A_n, которая ассоциативна. Тождественная подстановка четная и является нейтральным элементом в A_n. Если $\sigma\in A_n$ , то мы уже отметили, что $\sigma^{-1}\in A_n$ .

Задача 5.5.7.Найти разбиение в классы сопряженных элементов групп A₄, A₅.

Задача 5.5.8. Группа A_n, $n \geq 3$ , порождается тройными циклами (любой элемент группы A_n является произведением тройных циклов и обратных к ним; обратный элемент к тройному циклу сам является тройным циклом).

Указание Четная подстановка может быть представлена в виде произведения четного числа транспозиций, при различных i,j, k (i k)(i j)=(i j k), при различных i, j, k, l (i j)(k l)=(j k l)(i l j).

Разложение подстановок в произведение циклов с непересекающимися орбитами

Posted by admin on 23 Июль 2010 with Comments Closed
in Лекции по алгебре
as алгебра, лекции, обучение, уравнения, формулы

Орбитой цикла (i₁ i₂ … i_r) назовем множество {i₁,…,i_r}

Если $\sigma\in S_n$ — подстановка символов {1,2,…,n} и $a\in N$ , $1 \leq a \leq n$ , то рассмотрим последовательность

$a,\sigma(a),\sigma^2(a)=\sigma(\sigma(a)),...,\sigma^r(a),...$

(орбиту элемента a). Из конечности множества {1,2,…,n} следует, что найдутся такие натуральные числа t и s, t<s, что $\sigma^ta=\sigma^sa$ . В группе S_n рассмотрим $\sigma^{-1}$ . Применяя $(\sigma^{-1})^t$ к этому равенству, получим $a=\sigma^{s-t}(a)$ , r=s-t>0. Рассмотрим самое маленькое такое натуральное число r (со свойством $a=\sigma^r(a)$ , при этом все r элементов $\{a,\sigma(a),...,\sigma^{r-1}(a)\}$ различны). Итак, получили цикл $(a\quad \sigma(a)\quad...\quad \sigma^{r-1}(a))$ длины r. Выбирая элемент b вне этого цикла (если r<n), получаем цикл $(b\quad \sigma(b)\quad...\quad \sigma^{r'-1}(b))$ длины r’, при этом орбиты этих циклов не пересекаются. Продолжим этот процесс. Заметим, что циклы с непересекающимися орбитами перестановочны. Единственность этого разложения следует из инвариантности определения орбиты. Итак, получаем следующее утверждение.

Теорема 5.3.1. Каждая подстановка $\tau\in S_n$ разлагается (и притом единственным образом) в произведение циклов с непересекающимися орбитами (поэтому эти циклы перестановочны друг с другом).

Замечание 5.3.2.

В практических задачах удобно начинать с a=1, затем число b выбирать как наименьшее число, не вошедшее в $\{a,\sigma(a),...,\sigma^{r-1}(a)\}$ ,и т. д.
Как правило, циклы длины 1 (т. е. неподвижные элементы) опускают в записи циклового разложения подстановки.

Упражнение 5.3.3.

Пусть $\sigma,\tau\in S_n$ . Подстановка $\tau\sigma\tau^{-1}$ называется подстановкой, сопряженной с подстановкой $\sigma$ (с помощью подстановки $\tau$ ). Проверьте, что отношение сопряженности является отношением эквивалентности. Соответствующее разбиение множества S_n на классы эквивалентных подстановок называется разбиением на классы сопряженных элементов.
Доказать, что подстановки $\gamma,\sigma\in S_n$ сопряжены тогда и только тогда, когда $\gamma$ и $\sigma$ имеют одинаковое цикловое разложение (т. е. одинаковое число циклов каждой длины в своих разложениях в произведение циклов с непересекающимися орбитами).
Указания

$\tau(\sigma_1\sigma_2)\tau^{-1}= (\tau\sigma_1\tau^{-1})(\tau\sigma_2\tau^{-1})$ .

Если $\sigma=(i_1,...,i_r)$ — цикл длины r, то $\tau\sigma\tau^{-1}=(\tau(i_1),...,\tau(i_r))$ .

Пример 5.3.4. Пусть

$\begin{align*} \delta &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ 9 & 8 & 1 & 2 & 4 & 7 & 5 & 3 & 6 & 10 \end{pmatrix},\\ \sigma &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ 5 & 1 & 6 & 10 & 2 & 4 & 9 & 7 & 3 & 8 \end{pmatrix}. \end{align*}$

Требуется найти $(\delta\sigma)^{100}$

Сначала находим

$\delta\sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ 4 & 9 & 7 & 10 & 8 & 2 & 6 & 5 & 1 & 3 \end{pmatrix}= (5\quad 8)(1\quad 4\quad 10\quad 3\quad 7\quad 6\quad 2\quad 9)$

(разложение в произведение циклов с непересекающимися орбитами). Поэтому

$(\delta\sigma)^{100}=(5\quad 8)^{100} (1\quad 4\quad 10\quad 3\quad 7\quad 6\quad 2\quad 9)^{100}.$

Так как (5 8)² и (1 4 10 3 7 6 2 9)⁸ — тождественные подстановки, $100=12\cdot 8 \+ 4$ , то

$\begin{mult} (\delta\sigma)^{100} = (1\quad 4\quad 10\quad 3\quad 7\quad 6\quad 2\quad 9)^4 ={} \\ {}= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ 7 & 10 & 9 & 6 & 5 & 4 & 1 & 8 & 3 & 2 \end{pmatrix}= (4\quad 6)(3\quad 9)(2\quad 10)(1\quad 7). \end{mult}$

Задача 5.3.5. Найти разбиение на классы сопряженных элементов для групп S₃, S₄, S₅.

Задача 5.3.6.

Группа S_n порождается транспозициями (1 2),(1 3),…,(1 n) (т. е. любой элемент группы S_n является произведением этих транспозиций).
Указание Если $i,j\neq 1$ , то (i j)=(1 i)(1 j)(1 i).
Группа S_n, $n \geq 3$ , порождается транспозицией (1 2) и циклом (1 2… n).

Подстановки, перестановки

Posted by admin on 23 Июль 2010 with Comments Closed
in Лекции по алгебре
as алгебра, лекции, обучение, уравнения, формулы

Теорема 5.0.4. Множество S(U) всех биекций

$f: U\to U$

с операцией произведения (композиции) отображений gf для $U\xrightarrow{f} U \xrightarrow{g} U$ , $f,g\in S(U)$ , обладает следующими свойствами:

операция произведения ассоциативна (h(gf)=(hg)f для всех $f,g,h\in S(U)$ ),
нейтральным элементом для этой операции является тождественное отображение 1_U (1_Uf=f=f1_U для всех $f\in S(U)$ ),
для всякой биекции $f: U\to U$ существует обратный элемент — биекция g=f^-1 (fg=1_U=gf).

(Другими словами, S(U) — группа относительно операции произведения отображений; S(U) — подгруппа моноида T(U) : $S(U)\subseteq \mT(U)$ .)

Доказательство. следует из теоремы 1.6.4 и леммы 1.8.4.

Биекции $f: U\to U$ множества U часто называются подстановками. Наиболее важный для нас случай U={1,2,…,n}, в этом случае группу S_n = S({1,2,…,n}) называют группой подстановок множества {1,2,…,n} из n элементов (иногда называемой симметрической группой).

Запись подстановок. Перестановки

Если $f\in S_n$ — подстановка, то рассмотрим ее каноническую запись

$\begin{pmatrix} 1 & 2 & ... & n\\ f(1) & f(2) & ... & f(n) \end{pmatrix}.$

В нижней строчке (f(1), f(2),…, f(n)), поскольку f — биекция, встречаются все элементы i, $1 \leq i \leq n$ , при этом только по одному разу. Такие строчки элементов (i₁,…,i_n), $1 \leq i_j \leq n$ , где каждый элемент i_j, $1 \leq i_j \leq n$ , встречается один и только один раз, называются перестановками элементов 1,2,…,n.

Лемма 5.1.1. Число всех перестановок (i₁,…,i_n) из n элементов равно $n!=1\cdot 2\cdot ...\cdot n$ .

Доказательство. Для i₁ имеем n возможностей. При выбранном i₁ для i₂ имеем (n-1) возможность. Таким образом, число различных перестановок равно $n\cdot (n-1)\cdot ...\cdot 2\cdot 1 = n!$ .

Лемма 5.1.2. Число различных подстановок множества {1,2,…,n} равно n! (т. е. | S_n|=n!).

Доказательство. Для $f\in S_n$ рассмотрим каноническую запись

$f=\begin{pmatrix} 1 & 2 & ... & n\\ f(1) & f(2) & ... & f(n) \end{pmatrix}.$

Таким образом, различных подстановок столько же, сколько различных перестановок n элементов, т. е. n!

Во многих случаях удобно рассматривать записи подстановки $f\in S_n$ , располагая в верхней строчке произвольную перестановку (i₁,i₂,…,i_n):

$f = \begin{pmatrix} i_1 & i_2 & ... & i_n\\ f(i_1) & f(i_2) & ... & f(i_n) \end{pmatrix}.$

Каждый столбец этой таблицы имеет вид

$\begin{pmatrix} i\\ f(i) \end{pmatrix}.$

Пример 5.1.3

Для тождественной подстановки в S₂ имеем
$f = \begin{pmatrix} 1 & 2\\ 1 & 2 \end{pmatrix} = \begin{pmatrix} 2 & 1\\ 2 & 1 \end{pmatrix}.$

Для биекции $f: \{1,2\}\to \{1,2\}$ , f(1)=2, f(2)=1, имеем

$f = \begin{pmatrix} 1 & 2\\ 2 & 1 \end{pmatrix} = \begin{pmatrix} 2 & 1\\ 1 & 2 \end{pmatrix}.$
Если
$f=\begin{pmatrix} i_1 & ... & i_n\\ j_1 & ... & j_n \end{pmatrix} \in S_n,$

то

$f^{-1}=\begin{pmatrix} j_1 & ... & j_n\\ i_1 & ... & i_n \end{pmatrix}.$
Так как $(\sigma\tau)(i)=\sigma(\tau(i))$ , то
$\begin{pmatrix} 1 & 2 & 3\\ 2 & 1 & 3 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix}.$

В частности,

$\begin{pmatrix} i_1 & i_2 & ... & i_n\\ j_1 & j_2 & ... & j_n \end{pmatrix} \begin{pmatrix} 1 & 2 & ... & n\\ i_1 & i_2 & ... & i_n \end{pmatrix} = \begin{pmatrix} 1 & 2 & ... & n\\ j_1 & j_2 & ... & j_n \end{pmatrix}.$
Обозначим через (i₁ i₂… i_r) цикл длины r в группе подстановок S_n: подстановку, переводящую i_k в i_k+1 для $1 \leq k \leq r-1$ , i_r в i₁, и оставляющую все элементы из {1,2,…,n}, отличные от i₁,…,i_r, на месте. Тогда в S₃ имеем шесть подстановок:
$\begin{alignat*}{2} e&= \begin{pmatrix} 1 & 2 & 3\\ 1 & 2 & 3 \end{pmatrix}; &\qquad (1\quad 2) &= \begin{pmatrix} 1 & 2 & 3\\ 2 & 1 & 3 \end{pmatrix}; \\ (1\quad 3) &= \begin{pmatrix} 1 & 2 & 3\\ 3 & 2 & 1 \end{pmatrix}; & (2\quad 3) &= \begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{pmatrix}; \\ (1\quad 2\quad 3)&= \begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix}; & (1\quad 3\quad 2)&= \begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix}. \end{alignat*}$

При этом в S_n для $n \geq 3$ имеем

$(1\quad 2)(1\quad 3) = (1\quad 3\quad 2) \neq (1\quad 2\quad 3) = (1\quad 3)(1\quad 2),$

следовательно, группа S₃ и любая группа S_n при $n \geq 3$ некоммутативны. Так как S₁={e} и S₂={e, (1 2)} — коммутативные группы, то получаем, что группа S_n коммутативна тогда и только тогда, когда n=1 или n=2.

Линейные преобразования линейных пространств столбцов, задаваемые (прямоугольной) матрицей

Posted by admin on 23 Июль 2010 with Comments Closed
in Лекции по алгебре
as алгебра, лекции, обучение, уравнения, формулы

Рассмотрим линейные пространства столбцов над полем K (например, над полем R действительных чисел)

$\begin{align*} & U=\hat K^n = \left\{\left.X=\begin{pmatrix}x_1\\\vdots\\x_n\end{pmatrix}\right| x_i\in K\right\},\\[3mm] & V=\hat K^m = \left\{\left.Y=\begin{pmatrix}y_1\\\vdots\\y_m\end{pmatrix}\right| y_i\in K\right\}. \end{align*}$

Каждая $(m\times n)$ -матрица F=(f_ij), $f_{ij}\in K$ , задает отображение $f: U\to V$ ,

$f(X)=Y=\begin{pmatrix}y_1\\\vdots\\y_m\end{pmatrix}$

для всех

$\begin{pmatrix}x_1\\\vdots\\x_n\end{pmatrix}=X\in U=\hat K^n,$

где

$\begin{array}{c@{}c@{}c@{}c@{}c} y_1 & {}={} & f_{11}x_1 & {}+...+{} & f_{1n}x_n,\\ \vdots & & \vdots & & \vdots\\ y_m & {}={} & f_{m1}x_1 & {}+...+{} & f_{mn}x_n. \end{array}$

Теорема 7.0.6. Отображение

$f: U=\hat K^n\to V=\hat K^m,$

задаваемое прямоугольной $(m\times n)$ -матрицей F=(f_ij), обладает следующими свойствами:

f(X+X’)=f(X)+f(X’) для всех $X,X'\in U$ \textup;
f(cX)=cf(X) для всех $c\in K$ , $X\in U$ .

Доказательство. Для

$X= \begin{pmatrix} x_1\\\vdots\\x_n \end{pmatrix},\ \ X'= \begin{pmatrix} x'_1\\\vdots\\x'_n \end{pmatrix},\quad c\in K$

имеем

$X+X'= \begin{pmatrix} x_1+x'_1\\\vdots\\x_n+x'_n \end{pmatrix},\quad cX=\begin{pmatrix}cx_1\\\vdots\\cx_n\end{pmatrix}.$

Применяя отображение f, определяемое прямоугольной матрицей F=(f_ij), к X+X’ и cX, соответственно получаем f(X+X’)=f(X)+f(X’), f(cX)=cf(X).

Замечание 7.0.7. Отображение $f: U\to V$ из одного линейного пространства U в другое линейное пространство V, удовлетворяющее свойствам

f(X+X’)=f(X)+f(X’) для всех $X,X'\in U$ ,
f(cX)=cf(X) для всех $c\in K$ , $X\in U$ ,

называется линейным отображением (преобразованием). Тем самым мы показали, что отображение, задаваемое прямоугольной $(m\times n)$ -матрицей F=(f_ij), определяет линейное преобразование соответствующих линейных пространств столбцов:

$f: U=\hat K^n\to V=\hat K^m.$

Пример 7.0.8. Если m=1, то имеем линейную функцию y=f₁x₁+…+f_mx_n из $U=\hat K^n$ в $\hat K^1=K$ .

Пример 7.0.9. Поворот плоскости вокруг точки (0,0) на угол $\alpha$ является линейным отображением $f: \hat R^2\to\hat R^2$ , задаваемым матрицей поворота

$\begin{pmatrix} \cos\alpha & -\sin\alpha\\ \sin\alpha & \phm \cos\alpha \end{pmatrix}.$

Теорема 7.0.10 (об однозначной определяемости матрицы, задающей линейное отображение столбцов). Пусть

$f: U=\hat K^n \to V=\hat K^m,\ \ g: U=\hat K^n \to V=\hat K^m \text{ -}$

два линейных отображения, задаваемых $(m\times n)$ -матрицами F=(f_ij) и G=(g_ij) соответственно. Тогда f=g в том и только в том случае, когда F=G (т. е. f_ij=g_ij для всех i, j

Доказательство.

Если F=G, то ясно, что f=g.
Пусть f=g. Рассмотрим
$e_j= \begin{pmatrix} 0\\ \vdots\\ 1\\ \vdots\\ 0 \end{pmatrix},$

где 1 стоит в j-й строке, а остальные элементы равны нулю. Тогда

$\begin{pmatrix} f_{1j}\\ \vdots\\ f_{ij}\\ \vdots\\ f_{mj} \end{pmatrix} = f(e_j) = g(e_j) = \begin{pmatrix} g_{1j}\\ \vdots\\ g_{ij}\\ \vdots\\ g_{mj} \end{pmatrix},$

поэтому для любого i имеем f_ij=g_ij, т. е. F=(f_ij)=(g_ij)=G.

Теорема 7.0.11 (о задании любого линейного отображения линейных пространств столбцов матрицей). Пусть

$f: U=\hat K^n\to V=\hat K^m \text{ -}$

линейное отображение линейных пространств столбцов, т. е.

f(X+X’)=f(X)+f(X’) для всех $X,X'\in U$ ,
f(cX)=cf(X) для всех $c\in K$ , $X\in U$ .

Тогда найдется (и единственная) $(m\times n)$ -матрица F=(f_ij) такая, что определяемое с ее помощью линейное отображение совпадает с линейным отображением f.

Доказательство. Пусть

$e_j = \begin{pmatrix} 0\\ \vdots\\ 1\\ \vdots\\ 0 \end{pmatrix} \begin{matrix} \vphantom{0}\\ \vphantom{\vdots}\\ \scriptstyle \kern-3mm -\;j\\ \vphantom{\vdots}\\ \vphantom{0} \end{matrix}\;,\quad f(e_j) = \begin{pmatrix} f_{1j}\\ \vdots\\ f_{ij}\\ \vdots\\ f_{mj} \end{pmatrix} \in V = \hat K^m,\ \ f_{ij}\in K.$

Получили $(m\times n)$ -матрицу F=(f_ij)

Для любого

$X= \begin{pmatrix} x_1\\ \vdots\\ x_n \end{pmatrix} \in U = \hat K^n$

имеем X=x_1e_1+…+x_ne_n. Тогда

$\begin{mult} \smash[b]{\begin{pmatrix} y_1\\ \vdots\\ y_m \end{pmatrix}} = f(X) = x_1f(e_1)+...+x_nf(e_n)={} \\ {}= x_1 \begin{pmatrix} f_{11}\\ \vdots\\ f_{m1} \end{pmatrix} +... + x_n \begin{pmatrix} f_{1n}\\ \vdots\\ f_{mn} \end{pmatrix}, \end{mult}$

т. е.

$\begin{array}{c@{}c@{}c@{}c@{}c} y_1 & {}={} & f_{11}x_1 & {}+...+{} & f_{1n}x_n,\\ \vdots & & \vdots & & \vdots\\ y_m & {}={} & f_{m1}x_1 & {}+...+{} & f_{mn}x_n. \end{array}$

Итак, линейное отображение f задается $(m\times n)$ -матрицей F=(f_ij).

Как мы показали, матрица F=(f_ij) определена однозначно.

Вычисление определителей

Posted by admin on 23 Июль 2010 with Comments Closed
in Лекции по алгебре
as алгебра, лекции, обучение, уравнения, формулы

Определение определителя

$|A|=\sum_{\alpha\in S_n} \varepsilon(\alpha) a_{1\alpha(n)}... a_{n\alpha(n)}$

как суммы n! слагаемых-произведений плохо пригодно для реальных вычислений при больших n. В теоретическом плане важно отметить, что определитель |A| является многочленом от n² переменных a_ij, в котором мономы входят с коэффициентами $\pm 1$ . Отметим лишь одно из следствий этого факта: если a_ij=a_ij(x) являются дифференцируемыми функциями от переменной x, то определитель |A| также является дифференцируемой функцией от x, поскольку суммы и произведения дифференцируемых функций являются дифференцируемыми функциями.

Теорема 6.6.1. Пусть от квадратной $(n\times n)$ -матрицы A=(a_ij) элементарными преобразованиями 1-го и 2-го типа ( t преобразований 2-го типа) мы пришли к треугольной матрице

$\bar A = \begin{pmatrix} \bar a_{11} & & & \raisebox{-10pt}[0pt][0pt]{\text{\hspace*{-25pt}\LARGE*}}\\ 0 & \bar a_{22}\\ \vdots & & \ddots\\ 0 & \hdotsfor{2} & \bar a_{nn} \end{pmatrix}$

(все элементы ниже диагонали равны нулю; любая ступенчатая матрица, очевидно, является треугольной). Тогда

$|A| = (-1)^t \bar a_{11}... \bar a_{nn}.$

Доказательство. Так как |A|= (-1)^t |A|, то

$|A|=(-1)^t |\bar A|= (-1)^t \bar a_{11}... \bar a_{nn}.$

Характеризация функции определителя матрицы базовыми свойствами

Теорема 6.7.1 (о единственности функции с базовыми свойствами 1—4 определителя). Пусть функция F, сопоставляющая каждой квадратной $(n\times n)$ -матрице $A\in\mM_n(K)$ «число» $F(A)\in K$ , удовлетворяет базовым свойствам {1 4} функции определителя. Тогда F(A)=|A|, т. е. функция определителя |A| однозначно определяется свойствами {1 4}.

Доказательство. Приведем $(n\times n)$ -матрицу A к треугольному виду

$\bar A = \begin{pmatrix} \bar a_{11} & & & \raisebox{-10pt}[0pt][0pt]{\text{\hspace*{-25pt}\LARGE * }}\\ 0 & \bar a_{22}\\ \vdots & & \ddots\\ 0 & \hdotsfor{2} & \bar a_{nn} \end{pmatrix}$

элементарными преобразованиями строк 1-го и 2-го типа ( t преобразований 2-го типа). Тогда

$F(\bar A)=(-1)^t F(A),$

следовательно, F(A)=(-1)^t F(A). Далее, вынося элемент $\bar a_{nn}$ из n -й строки и создавая 0 над ним, получаем

$%\begin{mult} \addtolength{\arraycolsep}{-2pt} F(\bar A) = \bar a_{nn} F \begin{pmatrix} \bar a_{11} & & & \raisebox{-10pt}[0pt][0pt]{\text{\hspace*{-45pt}\LARGE * }}\\ \vdots & \ddots\\ 0 & ... & \bar a_{n-1\,n-1}\\ 0 & ... & 0 & 1 \end{pmatrix} = %{} %\\ %{}= \bar a_{nn} F \begin{pmatrix} \bar a_{11} & & & 0\\ \vdots & \ddots & \raisebox{10pt}[0pt][0pt]{\text{\hspace*{-0pt}\LARGE * }} & \vdots\\ 0 & ... & \bar a_{n-1\,n-1} & 0\\ 0 & ... & 0 & 1 \end{pmatrix}. %\end{mult}$

Продолжая это рассуждение, получаем

$F(\bar A) = \bar a_{11}... \bar a_{nn} F \begin{pmatrix} 1 & & \lefteqn{\raisebox{-5pt}[0pt][0pt]{\text{\hspace*{-10pt}\Large 0 }}}\\ & \ddots\\ \lefteqn{\raisebox{0pt}[0pt][0pt]{\text{\hspace*{0pt}\Large 0 }}} & & 1 \end{pmatrix} = \bar a_{11} ... \bar a_{nn}.$

Итак, $F(A)=(-1)^t F(\bar A) = (-1)^t \bar a_{11}... \bar a_{nn} = |A|.$

Подстановки, перестановки

Перестановки и транспозиции

Линейные пространства

Вывод свойств линейного пространства из аксиом

Линейная зависимость в линейных пространствах

Системы линейных уравнений

Совокупность решений системы линейных уравнений

Решение системы линейных уравнений

Виды систем линейных уравнений.

Системы линейных уравнений

Четность перестановок и подстановок

Четность произведения подстановок

Разложение подстановок в произведение циклов с непересекающимися орбитами

Подстановки, перестановки

Запись подстановок. Перестановки

Линейные преобразования линейных пространств столбцов, задаваемые (прямоугольной) матрицей

Вычисление определителей

Характеризация функции определителя матрицы базовыми свойствами

Реклама

Рубрики

Свежие записи

Архивы