Метка: доказательство

М2010. Зв’язна клітинна фігура

Задача із журналу «Квант» (2006 рік, №4)

Умова

Для натуральних чисел $m$ і $n$ позначимо через $F(m,n)$ кількість всіх зв’язних клітинних фігур прямокутнику $m\times n$. Доведіть, що парність числа $F(m,n)$ збігається з парність числа $\frac{n(n+1)}{2}\cdot\frac{m(m+1)}{2}.$ (Зв’язна клітинна фігура – це така непорожня множина клітин, що з будь-якої клітини цієї множини можна пройти в будь-яку іншу клітину цієї множини по клітинах цієї множини, переходячи щоразу в сусідню по стороні клітину.)

А.Бадзян

Рішення

Припустимо, що $F(m,0) = 0.$ Зв’язні фігури в прямокутнику $m\times 1$ – це $m$ фігур з однієї клітини та смужки із двох або більше клітин. Кожна смужка визначається парою клітин – першою та останньою, тому $$F(m,1) = m + \frac{m(m-1)}{2} = \frac{m(m+1)}{2}.$$

Нехай у прямокутнику $m$ рядків та $n\gt 1$ стовпців. Позначимо через $l$ вертикальну вісь симетрії. Кожній зв’язній фігурі відповідає фігура, симетрична щодо $l,$ тому несиметричні щодо $l$ фігури розбиваються на пари, і парність $F(m,n)$ збігається з парністю кількості зв’язних фігур, симетричних щодо $l.$

Розглянемо деяку фігуру $T,$ симетричну щодо $l.$

Нехай $n$ непарне, $n =2k-1,$ $k\ge 2.$ Фігура $T$ містить хоча б одну клітину $k$-го стовпця, інакше з клітини фігури $T$ неможливо пройти по клітинам $T$ в симетричну відносно $l$ клітину, переходячи кожен раз в сусідню клітину. Зауважимо, що частина $T_{1}$ фігури $T,$ що розташована в $k$ найлівіших стовпцях, зв’язна. Дійсно, розглянемо дві клітини $x$ та $y$ фігури $T_{1}.$ Нехай $x’$ – клітина, що симетрична $x$ відносно $l,$ a $x’,z_{1},z_{2},\ldots,z_{t},y$ – послідовність клітин, що утворює шлях з $x’$ в $y$ по сусідніх клітинах фігури $T.$ Тоді, замінюючи в цьому шляху клітини, що лежать правіше $k$-го стовпця, на симетричні щодо $l,$ ми отримаємо шлях з $x$ в $y$ по сусідніх клітинах фігури $T_{1}$ (див. малюнок). Навпаки, якщо фігура $T_{1}$ розташована у прямокутнику, що складається з $k$ найлівіших



стовпців, зв’язна і містить хоча б одну клітину $k$-го стовпця, можна однозначно продовжити фігуру $T_{1}$ до зв’язної фігури $T,$ симетричної відносно $l$. Кількість зв’язних фігур у прямокутнику $m\times k$ дорівнює $F(m,k),$ серед них $F(m,k-1)$ фігур лежать у перших $k-1$ стовпцях (тобто не містить клітин $k$-го стовпця). Отже, кількість зв’язних симетричних щодо $l$ фігур у прямокутнику $m\times (2k-1)$ дорівнює $F(m,k)-F(m,k-1).$

Для парного $n = 2k,$ $k\ge 1,$ міркуючи аналогічно, встановимо взаємно однозначну відповідність між зв’язними симетричними щодо $l$ фігурами та зв’язними фігурами, що розташовані в перших $k$ стовпцях і що містять хоча б одну клітинку $k$-го стовпця. Звідси випливає, що кількість зв’язних симетричних щодо $l$ фігур у прямокутнику $m\times 2k$ дорівнює $F(m,k)-F(m,k-1).$

Отже, для $n = 2k-1$ и $n = 2k$ парність $F(m,n)$ збігається з парністю числа $F(m,k)-F(m,k-1).$

Доведемо індукцією по $n,$ що $F(m,n)$ непарно тоді і лише тоді, коли $m$ і $n$ дають залишок $1$ або $2$ при діленні на $4;$ звідси відразу випливає твердження задачі. Твердження вірне при $n = 0$ і $n = 1.$

Нехай $m$ дає залишок $0$ або $3$ при діленні на $4.$ Припустимо, що це твердження вірне для $F(m,0),F(m,1),\ldots,F(m,n-1),$ тобто ці числа парні. Якщо $n = 2k-1,$ $k\ge 2,$ або $n = 2k,$ $k\ge 1,$ то $n\gt k,$ тому $F(m,n)$ парне, так як $F(m,k)-F(m,k-1)$ парне. Нехай $m$ дає залишок $1$ або $2$ при діленні на $4.$ Припустимо, що твердження вірно для чисел $F(m,0),F(m,1),\ldots,F(m,n-1),$ тобто $F(m,s)$ непарне тоді і лише тоді, коли $s$ дає залишок від ділення $1$ або $2$ при діленні на $4.$ Тоді $F(m,s)-F(m,s-1)$ непарне тоді і лише тоді, коли $s$ непарне. Звідси випливає, що $F(m,n)$ непарне тоді і тільки тоді, коли $n = 2(2l + 1)-1 = 4l + 1$ або $n = 2(2l + 1) = 4l + 2.$

А.Бадзян

M613. Подобные треугольники

Задача из журнала «Квант» (1980, №3)

Условие

На сторонах треугольника $ABC$ во внешнюю сторону построены подобные между собой треугольники $ADB,$ $BEC$ и $CFA,$ где
$$\frac{|AD|}{|DB|} = \frac{|BE|}{|EC|}= \frac{|CF|}{|FA|}=k;$$ $$\widehat{ADB}=\widehat{BEC}=\widehat{CFA}=\alpha.$$ Докажите, что:

  1. середины отрезков $AC,$ $DC,$ $BC$ і $EF -$ вершины параллелограмма;
  2. у этого параллелограмма два угла имеют величину $\alpha,$ a отношение длин сторон равняется $k.$
Л. Купцов

Решение

Обозначим через $\vec a^\prime$ вектор, полученный из вектора $\vec a$ поворотом на угол $\alpha$ против часовой стрелки. (Как известно, $(k\vec a)^\prime = k\vec a ^\prime$ для любого числа $k,$ $(\vec a+\vec b)^\prime=\vec a^\prime+\vec b^\prime, $ и вообще, для любого числа слагаемых, $(\vec a+\vec b+\ldots+\vec c)^\prime=\vec a^\prime+\vec b^\prime+\ldots+\vec c^\prime). $

Введем векторы $\overrightarrow{DA} = \vec a,$ $\overrightarrow{EB} = \vec b,$ $\overrightarrow{FC}=\vec c$ (см. рис.1).

рис.1

По условию $\overrightarrow{DB}=\frac 1k \vec a^\prime,$ $\overrightarrow{EC}=\frac 1k \vec b^\prime,$ $\overrightarrow{FA}=\frac 1k \vec c^\prime.$ Так как
$$\overrightarrow{AD}+\overrightarrow{DB}+\overrightarrow{BE}+\overrightarrow{EC}+\overrightarrow{CF}+\overrightarrow{FA}=\vec 0,$$ $$-\vec a+\frac 1k \vec a^\prime-\vec b+\frac 1k \vec b^\prime-\vec c+\frac 1k \vec c^\prime=\vec
0,$$ то есть $\vec a+\vec b+\vec c=\frac{\vec a^\prime+\vec b^\prime+\vec c^\prime}{k}=\frac 1k (\vec a+\vec b+\vec c)^\prime.$
Обозначив $\vec a+\vec b+\vec c$ через $\vec u,$ получим $$\vec u-\frac 1k \vec u^\prime=0. \qquad (\ast)$$ Поскольку векторы $\vec u$ та $\vec u^\prime$ неколинеарные $(\alpha \ne 0$ и $\alpha \ne 2\pi),$ равенство $(\ast)$ возможно тогда и только тогда, когда $\vec u=\vec 0.$ Поэтому $\vec a+\vec b+\vec c=\vec 0.$

Далее: поскольку $Q \: -$ середина $[DC]$ и $P \: -$ середина $[AC]$ (см. рис.1), $\overrightarrow{QP}=\frac 12 \vec a.$ Аналогично $\overrightarrow{QR}=\frac 12 \overrightarrow{DB}.$ Так как $(PQ)\|(AD)$ и $(QR) \| (BD),$ имеем $\widehat{PQR}=\alpha.$

Наконец, $$\overrightarrow{RS}=\overrightarrow{RC}+\overrightarrow{CF}+\overrightarrow{FS}=\frac 12 \overrightarrow{BC}-\vec c+\frac 12 \overrightarrow{FE}=$$ $$=\frac 12(-\vec b+\frac 1k \vec b^\prime)-\vec c+\frac 12 (\vec c-\frac 1k \vec b^\prime)=-\frac{\vec b+\vec c}{2}=\frac{\vec a}{2}=\overrightarrow{QP}.$$

Таким образом, четырехугольник $PQRS \: -$ параллелограмм с углом $PQR,$ равным $\alpha,$ в котором отношение длин сторон имеет вид $\frac{|PQ|}{|RQ|}=\frac{|AD|}{|DB|}=k.$

Л. Купцов

Критерий совместности СЛАУ Кронекера-Капелли

Теорема Кронекера-Капелли. Критерий совместности системы линейных алгебраических уравнений. СЛАУ совместна тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы. То есть, если в СЛАУ $r=\operatorname{rang}A=\operatorname{rang}\widetilde{A}$, где $\operatorname{rang}A$ — обозначает ранг матрицы системы, а $\operatorname{rang}\widetilde{A}$ — ранг расширенной матрицы, тогда данная матрица совместна, причём система имеет единственное решение, если $\operatorname{rang}A=\operatorname{rang}\widetilde{A}=n$, где $n$ — число неизвестных, и бесконечное число решений, если $\operatorname{rang}A=\operatorname{rang}\widetilde{A}<n$.

Необходимость. Пусть задана расширенная матрица $\widetilde{A}$:

$\widetilde{A}=\left\{\begin{matrix}
a_{11}x_{1} \; + \; a_{12}x_{2} \; + \; \cdots \; + \; a_{1n}x_{n} \; = \; b_{1}
\\a_{21}x_{1} \; + \; a_{22}x_{2} \; + \; \cdots \; + \; a_{2n}x_{n} \; = \; b_{2}
\\ \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots
\\a_{m1}x_{1} \; + \; a_{m2}x_{2} \; + \; \cdots \; + \; a_{mn}x_{n} \; = \; b_{m}
\end{matrix}\right.$

Скажем, что данная система совместна, в таком случае существуют числа $\left(c_{1},c_{2},\dots,c_{n}\right)$, которые являются частным решением матрицы, при подстановке их в систему. Мы получим равенство:

$\begin{Vmatrix} b_{1}\\ b_{2} \\ \vdots \\ b_{n}\\ \end{Vmatrix} =
c_{1}\begin{Vmatrix} a_{11}\\ a_{21} \\\vdots\\ a_{m1} \end{Vmatrix} +
c_{2}\begin{Vmatrix} a_{12}\\ a_{22} \\\vdots\\ a_{m2} \end{Vmatrix} + \dots+
c_{n}\begin{Vmatrix} a_{1n}\\ a_{2n} \\\vdots\\ a_{mn} \end{Vmatrix}
$

Следовательно, вектор-столбец свободных членов является линейной комбинацией столбцов $\left(a_{1},a_{2},\dots,a_{n}\right),$ матрицы $A.$ Так же, мы можем заметить, что сколько бы мы раз не приписали или не вычеркнули строку(столбец), от этого не меняется ранг системы, из этого следует, что $\operatorname{rang}A=\operatorname{rang}\widetilde{A}$.

Достаточность. Если $\operatorname{rang}A=\operatorname{rang}\widetilde{A}$, то это означает, что у них один и тот же базисный минор. Тогда, согласно теореме о базисном миноре, последний столбец свободных членов – линейная комбинация столбцов базисного минора.

Следствие:

  1. $\operatorname{rang}A=\operatorname{rang}\widetilde{A}=n$ единственное решение.
  2. $\operatorname{rang}A=\operatorname{rang}\widetilde{A}<n$ бесконечное число решений.
  3. Количество главных переменных равно рангу системы.

Примеры решения задач

Рассмотрим примеры задач, в которых используеться критерий совместности $\operatorname{rang}A=\operatorname{rang}\widetilde{A}.$

  1. $ \left\{\begin{matrix}
    2x_{1} \; — \; x_{2} \; + \; 5x_{3} \; = \; 4
    \\3x_{1} \; — \; x_{2} \; + \; 5x_{3} \; = \; 0
    \\5x_{1} \; — \; 2x_{2} \; + \; 3x_{3} \; = \; 2
    \end{matrix}\right.$

    Решение

    Сначала, приведем матрицу к треугольному виду.

    $\left(\begin{matrix} 2 & -1 & 5 & 4 \\ 3 & -1 & 5 & 0 \\ 5 & -2 & 3 & 2 \end{matrix} \right)\sim
    \left(\begin{matrix} -1 & 2 & 5 & 4\\ -1 & 3 & 5 & 0 \\ -2 & 5 & 3 & 2 \end{matrix} \right)\sim$

    $\left(\begin{matrix} -1 & 1 & 5 & 4\\ 0 & 1 & 0 & -4 \\ 0 & 1 & -7 & -7 \end{matrix} \right)\sim
    \left(\begin{matrix} -1 & 1 & 5 & 4\\ 0 & 1 & 0 & -4 \\ 0 & 0 & -7 & -3 \end{matrix} \right)$

    Элементарные преобразования не меняют ранга матриц, поэтому в результате выполненных действий, получены эквивалентные исходнной матрице системы $A=\left(\begin{matrix} -1 & 1 & 5 \\ 0 & 1 & 0 \\ 0 & 0 & -7\end{matrix}\right)$ и расширенная матрица системы $\widetilde{A}=\left(\begin{matrix} -1 & 1 & 5 & 4\\ 0 & 1 & 0 & -4 \\ 0 & 0 & -7 & -3 \end{matrix} \right)$

    $\operatorname{rang}A=\operatorname{rang}\widetilde{A}=3$ значит, по теореме Кронекера-Капелли система совместна.

  2. $\left\{\begin{matrix}
    x_{1} \; + \; x_{2} \; — \; x_{3} \; = \; 7
    \\x_{1} \; + \; 2x_{2} \; — \; 3x_{3} \; = \; 1
    \\-2x_{1} \; — \; 2x_{3} \; = \; 3
    \end{matrix}\right.$

    Решение

    Приведем матрицу к ступенчистому виду:

    $\left(\begin{matrix} 1 & 1 & -1 & -4 \\ 1 & 2 & -3 & 0 \\ -2 & 0 & -2 & 3 \end{matrix} \right)\sim \left(\begin{matrix} 1 & 1 & -1 & -4 \\ 0 & 1 & -2 & 4 \\ 0 & 2 & -4 & -5 \end{matrix} \right)\sim \left(\begin{matrix} 1 & 1 & -1 & -4 \\ 0 & 1 & -2 & 4 \\ 0 & 0 & 0 & -13 \end{matrix} \right)$

    $\Rightarrow \widetilde{A}=\left(\begin{matrix} 1 & 1 & -1 & -4 \\ 0 & 1 & -2 & 4 \\ 0 & 0 & 0 & -13 \end{matrix} \right)=\operatorname{rang}\widetilde{A}=3$

    $\Rightarrow A=\left(\begin{matrix} 1 & 1 & -1 \\ 0 & 1 & -2 \\ 0 & 0 & 0 \end{matrix} \right)=\operatorname{rang}A=2$

    $\operatorname{rang}A\neq \operatorname{rang}\widetilde{A}$. По теореме Кронекера-Капелли система линейных уравнений несовместна.

  3. $\left\{\begin{matrix}
    5x_{1} \; — \; 3x_{2} \; + \; 2x_{3} \; + \; 4x_{4} = \; 3
    \\4x_{1} \; — \; 2x_{2} \; + \; 3x_{3} \; + \; 7x_{4} = \; 1
    \\8x_{1} \; — \; 6x_{2} \; — \; x_{3} \; — \; 5x_{4} = \; 9
    \\7x_{1} \; — \; 3x_{2} \; + \; 7x_{3} \; + \; 17x_{4} = \; \lambda
    \end{matrix}\right.$

    Решение

    Очевидно, что от значения $\lambda$ зависит, будет ли матрица совместна или нет.

    Сначала приведем матрицу к треугольному ввиду:

    $\widetilde{A}=\left(\begin{matrix} 5 & -3 & 2 & 4 & 3\\ 4 & -2 & 3 & 7 & 1\\ 8 & -6 & -1 & -5 & 9 \\ 7 & -3 & 7 & 17 & \lambda \end{matrix} \right)\sim
    \left(\begin{matrix} 1 & -1 & -1 & -3 & 2\\ 4 & -2 & 3 & 7 & 1\\ 0 & -2 & -7 & -19 & 7 \\ 7 & -3 & 7 & 17 & \lambda \end{matrix} \right)\sim$

    $\left(\begin{matrix} 1 & -1 & -1 & -3 & 2\\ 0 & 2 & 7 & 19 & -7\\ 0 & -2 & -7 & -19 & 7 \\ 0 & 4 & 14 & 38 & \lambda — 14 \end{matrix} \right)\sim\left(\begin{matrix} 1 & -1 & -1 & -3 & 2\\ 0 & 2 & 7 & 19 & -7\\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \lambda \end{matrix} \right)$

    При $\lambda\neq0$: $\operatorname{rang}\widetilde{A}=3$, $\operatorname{rang}A=2$. По теореме Кронекера-Капелли система линейных уравнений несовместна.

    При $\lambda=0$: $\operatorname{rang}\widetilde{A}=2$, $\operatorname{rang}A=2$. По теореме Кронекера-Капелли система линейных уравнений совместна.

Критерий совместности СЛАУ Кронекера-Капелли

Тест на закрепление материала «Критерий совместности СЛАУ Кронекера-Капелли».

Литература

  1. Личный конспект, составленный на основе лекций Белозерова Г.С.
  2. Фадеев Д.К. Лекции по алгебре. М.: Наука, 1984.-416 с.  стр 119.
  3. Проскуряков И.В. Сборник задач по линейной алгебре. М.: Наука, 1984.-384 с.  стр 101-103.

Теорема об аддитивной группе матриц

Теорема. Пусть $ M_{m\times n} \left ( P\right )$ — множество матриц размеров $m\times n$ над полем $P,$ «$+$» — операция сложения матриц. Тогда пара $\left ( M_{m\times n} \left ( P \right ),\,+\right )$ — абелева группа.

Для доказательства теоремы необходимо проверить аксиомы группы и коммутативность операции сложения матриц.

Для записи аксиом и свойств в общем виде будем использовать следующие обозначения:

Ассоциативность

В общем виде аксиома ассоциативности группы выглядит так: $$\forall g_{1},\,g_{2},\,g_{3}\in G\;\left (g_{1}\ast g_{2}\right )\ast g_{3}=g_{1}\ast \left (g_{2}\ast g_{3}\right ).$$ Запишем ее для множества матриц размеров $m\times n:$ $$\forall A,B,C\in M_{m\times n}\left ( P \right )\;\left ( A+B \right )+C=A+\left ( B+C \right ).$$

Пусть $$A=\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right),\; B=\left(\begin{matrix}b_{11}&b_{12} & \cdots &b_{1n} \\b_{21}&b_{22} & \cdots &b_{2n}\\\cdot &\cdot &\cdot &\cdot \\b_{m1}&b_{m2}&\cdots &b_{mn} \end{matrix}\right),$$ $$C=\left(\begin{matrix}c_{11}&c_{12} & \cdots &c_{1n} \\c_{21}&c_{22} & \cdots &c_{2n}\\\cdot &\cdot &\cdot &\cdot \\c_{m1}&c_{m2}&\cdots &c_{mn} \end{matrix}\right);$$ $$\left (A+B\right )+C=\left( \left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right)+\left(\begin{matrix}b_{11}&b_{12} & \cdots &b_{1n} \\b_{21}&b_{22} & \cdots &b_{2n}\\\cdot &\cdot &\cdot &\cdot \\b_{m1}&b_{m2}&\cdots &b_{mn} \end{matrix}\right) \right) +$$ $$+\left(\begin{matrix}c_{11}&c_{12} & \cdots &c_{1n} \\c_{21}&c_{22} & \cdots &c_{2n}\\\cdot &\cdot &\cdot &\cdot \\c_{m1}&c_{m2}&\cdots &c_{mn}\end{matrix}\right)=\left(\begin{matrix}a_{11}+b_{11}&a_{12}+b_{12} & \cdots &a_{1n}+b_{1n} \\a_{21}+b_{21}&a_{22}+b_{22} & \cdots &a_{2n}+b_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}+b_{m1}&a_{m2}+b_{m2}&\cdots &a_{mn}+b_{mn}\end{matrix}\right)+$$ $$+\left(\begin{matrix}c_{11}&c_{12} & \cdots &c_{1n} \\c_{21}&c_{22} & \cdots &c_{2n}\\\cdot &\cdot &\cdot &\cdot \\c_{m1}&c_{m2}&\cdots &c_{mn} &\end{matrix}\right)=$$ $$=\left(\begin{matrix}a_{11}+b_{11}+c_{11}&a_{12}+b_{12}+c_{12} & \cdots &a_{1n}+b_{1n}+c_{1n} \\a_{21}+b_{21}+c_{21}&a_{22}+b_{22}+c_{22} & \cdots &a_{2n}+b_{2n}+c_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}+b_{m1}+c_{m1}&a_{m2}+b_{m2}+c_{m2}&\cdots &a_{mn}+b_{mn}+c_{mn} \end{matrix}\right);$$ $$A+\left ( B+C \right )=\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right)+$$ $$+\left(\left(\begin{matrix}b_{11}&b_{12} & \cdots &b_{1n} \\b_{21}&b_{22} & \cdots &b_{2n}\\\cdot &\cdot &\cdot &\cdot \\b_{m1}&b_{m2}&\cdots &b_{mn} \end{matrix}\right)+\left(\begin{matrix}c_{11}&c_{12} & \cdots &c_{1n} \\c_{21}&c_{22} & \cdots &c_{2n}\\\cdot &\cdot &\cdot &\cdot \\c_{m1}&c_{m2}&\cdots &c_{mn} \end{matrix}\right) \right)=$$ $$=\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right)+\left(\begin{matrix}b_{11}+c_{11}&b_{12}+c_{12} & \cdots &b_{1n}+c_{1n} \\b_{21}+c_{21}&b_{22}+c_{22} & \cdots &b_{2n}+c_{2n}\\\cdot &\cdot &\cdot &\cdot \\b_{m1}+c_{m1}&b_{m2}+c_{m2}&\cdots &b_{mn}+c_{mn} \end{matrix}\right)=$$ $$=\left(\begin{matrix}a_{11}+b_{11}+c_{11}&a_{12}+b_{12}+c_{12} & \cdots &a_{1n}+b_{1n}+c_{1n} \\a_{21}+b_{21}+c_{21}&a_{22}+b_{22}+c_{22} & \cdots &a_{2n}+b_{2n}+c_{2n}\\\cdot &\cdot &\cdot &\cdot\\a_{m1}+b_{m1}+c_{m1}&a_{m2}+b_{m2}+c_{m2}&\cdots &a_{mn}+b_{mn}+c_{mn} \end{matrix}\right).$$

$\left ( A+B \right )+C=A+\left ( B+C \right )\Rightarrow $ операция ассоциативна.

Аксиома нейтрального элемента

В общем виде аксиома нейтрального элемента группы выглядит так: $$\exists e\in G:\;\forall g\in G\;g\ast e=e\ast g=g.$$ Запишем ее для множества матриц размеров $m\times n:$ $$\exists O\in M_{m\times n}\left ( P \right ):\;\forall A\in M_{m\times n}\left ( P \right )\;A+O=O+A=A.$$ В нашем случае нейтральным элементом является нулевая матрица $O\in M_{m\times n}\left ( P \right ).$

Пусть $$A=\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right),\; O =\left(\begin{matrix}0&0 & \cdots &0 \\0&0 & \cdots &0\\\cdot &\cdot &\cdot &\cdot \\0&0&\cdots &0 \end{matrix}\right).$$$$A+O=\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right)+\left(\begin{matrix}0&0 & \cdots &0 \\0&0 & \cdots &0\\\cdot &\cdot &\cdot &\cdot \\0&0&\cdots &0 \end{matrix}\right)=$$ $$=\left(\begin{matrix}a_{11}+0&a_{12}+0 & \cdots &a_{1n}+0 \\a_{21}+0&a_{22}+0 & \cdots &a_{2n}+0\\\cdot &\cdot &\cdot &\cdot \\a_{m1}+0&a_{m2}+0&\cdots &a_{mn}+0 \end{matrix}\right)=\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right)=A.$$ $$O+A=\left(\begin{matrix}0&0 & \cdots &0 \\0&0 & \cdots &0\\\cdot &\cdot &\cdot &\cdot \\0&0&\cdots &0 \end{matrix}\right)+\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right)=$$ $$=\left(\begin{matrix}0+a_{11}&0+a_{12} & \cdots &0+a_{1n} \\0+a_{21}&0+a_{22} & \cdots &0+a_{2n}\\\cdot &\cdot &\cdot &\cdot \\0+a_{m1}&0+a_{m2}&\cdots &0+a_{mn} \end{matrix}\right)=\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right)=A.$$

$A+O=O+A=A\Rightarrow $ $O$ — нейтральный элемент.

Аксиома симметричных элементов

В общем виде аксиома симметричных элементов группы выглядит так: $$\forall g\in G\;\exists{g}’\in G:\;g\ast{g}’={g}’\ast g=e.$$ Запишем ее для множества матриц размеров $m\times n:$ $$\forall A\in M_{m\times n}\left ( P \right )\;\exists\left ( -A \right )\in M_{m\times n}\left ( P \right ):\;A+\left ( -A \right )=-A+A=O.$$

Пусть $$A=\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right);$$ $$-A=-\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right)=\left(\begin{matrix}-a_{11}&-a_{12} & \cdots &-a_{1n} \\-a_{21}&-a_{22} & \cdots &-a_{2n}\\\cdot &\cdot &\cdot &\cdot \\-a_{m1}&-a_{m2}&\cdots &-a_{mn} \end{matrix}\right).$$ $$A+\left ( -A \right )=\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right)+\left(\begin{matrix}-a_{11}&-a_{12} & \cdots &-a_{1n} \\-a_{21}&-a_{22} & \cdots &-a_{2n}\\\cdot &\cdot &\cdot &\cdot \\-a_{m1}&-a_{m2}&\cdots &-a_{mn} \end{matrix}\right)=$$ $$=\left(\begin{matrix}a_{11}-a_{11}&a_{12}-a_{12} & \cdots &a_{1n}-a_{1n} \\a_{21}-a_{21}&a_{22}-a_{22} & \cdots &a_{2n}-a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}-a_{m1}&a_{m2}-a_{m2}&\cdots &a_{mn}-a_{mn} \end{matrix}\right)=\left(\begin{matrix}0&0 & \cdots &0 \\0&0 & \cdots &0\\\cdot &\cdot &\cdot &\cdot \\0&0&\cdots &0 \end{matrix}\right)=O;$$$$-A+A=\left(\begin{matrix}-a_{11}&-a_{12} & \cdots &-a_{1n} \\-a_{21}&-a_{22} & \cdots &-a_{2n}\\\cdot &\cdot &\cdot &\cdot \\-a_{m1}&-a_{m2}&\cdots &-a_{mn} \end{matrix}\right)+\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right)=$$ $$=\left(\begin{matrix} -a_{11}+a_{11}&-a_{12}+a_{12} & \cdots &-a_{1n}+a_{1n} \\-a_{21}+a_{21}&-a_{22}+a_{22} & \cdots &-a_{2n}+a_{2n}\\\cdot &\cdot &\cdot &\cdot \\-a_{m1}+a_{m1}& -a_{m2}+a_{m2}&\cdots &-a_{mn}+a_{mn} \end{matrix}\right)=\left(\begin{matrix}0&0 & \cdots &0 \\0&0 & \cdots &0\\\cdot &\cdot &\cdot &\cdot \\0&0&\cdots &0 \end{matrix}\right)=O.$$

$A+\left ( -A \right )=-A+A=O \Rightarrow$ $A$ и $-A$ — симметричные элементы.

Коммутативность

Проверив все аксиомы, мы доказали, что $\left ( M_{m\times n} \left ( P \right ),\,+\right )$ — группа. Чтобы доказать, что она абелева, проверим коммутативность опреации.

Общий вид: $$\forall g_{1},g_{2}\in G\;g_{1}\ast g_{2}=g_{2}\ast g_{1}.$$ Для множества матриц размеров $m\times n:$ $$\forall A,B\in M_{m\times n}\left ( P \right )\;A+B=B+A.$$

Пусть $$A=\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right),\; B=\left(\begin{matrix}b_{11}&b_{12} & \cdots &b_{1n} \\b_{21}&b_{22} & \cdots &b_{2n}\\\cdot &\cdot &\cdot &\cdot \\b_{m1}&b_{m2}&\cdots &b_{mn} \end{matrix}\right);$$ $$A+B=\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\ \cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right)+\left(\begin{matrix}b_{11}&b_{12} & \cdots &b_{1n} \\b_{21}&b_{22} & \cdots &b_{2n}\\\cdot &\cdot &\cdot &\cdot \\b_{m1}&b_{m2}&\cdots &b_{mn} \end{matrix}\right)=$$ $$=\left(\begin{matrix}a_{11}+b_{11}&a_{12}+b_{12} & \cdots &a_{1n}+b_{1n} \\a_{21}+b_{21}&a_{22}+b_{22} & \cdots &a_{2n}+b_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}+b_{m1}&a_{m2}+b_{m2}&\cdots &a_{mn}+b_{mn}\end{matrix}\right);$$ $$B+A=\left(\begin{matrix}b_{11}&b_{12} & \cdots &b_{1n} \\b_{21}&b_{22} & \cdots &b_{2n}\\\cdot &\cdot &\cdot &\cdot \\b_{m1}&b_{m2}&\cdots &b_{mn} \end{matrix}\right)+\left(\begin{matrix}a_{11}&a_{12} & \cdots &a_{1n} \\a_{21}&a_{22} & \cdots &a_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}&a_{m2}&\cdots &a_{mn} \end{matrix}\right)=$$ $$=\left(\begin{matrix}b_{11}+a_{11}&b_{12}+a_{12} & \cdots &b_{1n}+a_{1n} \\b_{21}+a_{21}&b_{22}+a_{22} & \cdots &b_{2n}+a_{2n}\\\cdot &\cdot &\cdot &\cdot \\b_{m1}+a_{m1}&b_{m2}+a_{m2}&\cdots &b_{mn}+a_{mn} \end{matrix}\right)=$$ $$=\left(\begin{matrix}a_{11}+b_{11}&a_{12}+b_{12} & \cdots &a_{1n}+b_{1n} \\a_{21}+b_{21}&a_{22}+b_{22} & \cdots &a_{2n}+b_{2n}\\\cdot &\cdot &\cdot &\cdot \\a_{m1}+b_{m1}&a_{m2}+b_{m2}&\cdots &a_{mn}+b_{mn}\end{matrix}\right).$$

$A+B=B+A\Rightarrow$ операция коммутативна.

Доказав три аксиомы группы и коммутативность, мы доказали теорему об аддитивной группе матриц.

Литература

  1. Белозеров Г.С. Конспект лекций по линейной алгебре.
  2. Воеводин В.В. Линейная алгебра. М.: Наука, 1980.-400 с., стр. 23-26
  3. Фадеев Д.К. Лекции по алгебре. М.: Наука, 1984.-416 с., стр. 242-244

М1818. Доказать неравенство с тремя параметрами

Задача из журнала «Квант» (2002 год, 3 выпуск)

Условие

Докажите неравенство $$\sqrt{\cfrac{a}{b+c}}+\sqrt{\cfrac{b}{c+a}}+\sqrt{\cfrac{c}{a+b}}>2,$$где $a>0, b>0, c>0$.

С.Нестеров

Решение

Рассмотрим функцию $$f(x,y,z)=\sqrt{\cfrac{x}{y+z}}+\sqrt{\cfrac{y}{z+x}}+\sqrt{\cfrac{z}{x+y}},$$ где $x>0, y>0, z>0$. Считая, без ограничения общности, $x\leqslant y \leqslant z$, докажем вначале неравенство $$f(x,y,z)\leqslant f(x,\cfrac{y+z}{2}, \cfrac{y+z}{2}). \tag{1}$$ Обозначив $\cfrac{z+y}{2}=\alpha, \cfrac{z-y}{2}=t$, перепишем $(1)$ в виде $$\phi (t)\geqslant \phi (0),\tag{2}$$ где $$\phi (t)=\sqrt{\cfrac{\alpha + t}{\alpha + x — t}}+\sqrt{\cfrac{\alpha — t}{\alpha + x + t}}.$$

Здесь $0\leqslant t \leqslant \alpha, \alpha \geqslant x$.

Докажем $(2)$. Имеем $$\phi^{\prime}(t)=(x+2a)\left (\cfrac{1}{(\alpha + t)^{\frac{1}{2} }(x+\alpha-t)^{\frac{3}{2}}} — \cfrac{1}{(\alpha — t)^{\frac{1}{2}}(x+\alpha +t)^{\frac{3}{2}}}\right ).$$ Очевидно, знак $\phi^{\prime}(t)$ совпадает со знаком функции $$\psi (t)=(\alpha — t)(x + \alpha + t)^{3}-(\alpha + t)(x+\alpha -t)^{3},$$ и любой нуль функции $\phi^{\prime} (t)$ также является нулем функции $\psi (t)$. Исследуем $\psi (t)$. Имеем: $\psi (t)$ — отличный от константы нечетный многочлен, степень которого не выше $3$. Следовательно, $\psi (t)$ имеет на положительной полуоси не более одного корня.

Получили: $\phi (t)$ может иметь внутри отрезка $[0,\alpha]$ не более одного экстремума. Но и этот экстремум не может быть минимумом, поскольку $\psi (\alpha)<0$.

Итак, $\phi (t) \geqslant min\{ \phi (0), \phi(\alpha)\} $. Но, поскольку $\alpha \geqslant x$, имеем $$\phi(0)=2\sqrt{\cfrac{\alpha}{\alpha + x}}\leqslant \sqrt{\cfrac{2\alpha}{x}}=\phi (\alpha).$$ Неравенство $(1)$ доказано.

(Выше мы ограничились необходимой нам информацией о производной; легко получить и полную информацию о ней. Именно, $\psi (t)$ — многочлен третьей степени; $\psi (t) = 0$, при $t = 0$ и при $$t^{2}=\cfrac{(x+\alpha)^{2}(2\alpha — x)}{3x+2\alpha}.$$ При этом $t^{2}<\alpha^{2}$ при $x>0, \alpha>0$. Значит исследуемая функция при любом $x, x < 0 < \alpha$, имеет экстремум на интервале $(0;\alpha)$.)

Вследствие $(1)$ для решения задачи достаточно доказать, что $$f_{1}(x)=\sqrt{\cfrac{x}{2\alpha}}+2\sqrt{\cfrac{\alpha}{x+\alpha}}> 2 \tag{3}$$ при $0<x\leqslant \alpha$.

Исследуем $f_{1}(x)$ на отрезке $[0;\alpha]$. Во внутренних точках этого отрезка знак $f^{\prime}_1(x)$ совпадает со знаком многочлена $P(x)=(x+\alpha)^{3}-8\alpha^{2}x$. Кроме того, любой нуль функции $f^{\prime}_{1}(x)$ является также нулем многочлена $P(x)$. Заметим что $P(\alpha)=0;$ помимо этого, $P(x)$ имеет корень на отрицательной полуоси. Следовательно, если $P(x_0)=0$ при $0<x_0<\alpha$, то при переходе через $x_0$ многочлен $P(x)$ меняет знак с $«+»$ на $«-»$. Поэтому $x_0$ — точка максимума функции $f_1(x)$.

Получили: $$f_{1}(x)>min\{f_{1}(0),f_{1}(\alpha)\}$$ при $0<x<\alpha$. Но $$f_{1}(\alpha)=\cfrac{3}{\sqrt{2}}>2=f_{1}(0).$$ Неравенство $(3)$ доказано.

(Легко видеть, что $P(x)=0$ при $x=\alpha$ и при $x=\alpha(-2\pm \sqrt{5})$. Значит исследуемая функция имеет экстремум на интервале $(0;\alpha)$.)

А.Ковальджи, С.Нестеров, В.Сендеров