$begingroup$
Consider a binary square matrix $A$ ,(that is elements are either $1$ or $0$). You are given $Sum$ of elements of $each$ $row$ and $column$ ,that is you are given $r_i$ where $r_i$ means $Sum$ of its elements in $i$ th $row$ and same for column $i$ $Sum$ is $c_i$ . Find the binary matrix.
How can i find the matrix, i mean for small matrix i could use pen and paper and for medium sized matrix i could check each random permutation but for large ones it is not possible. Is there any good algorithm for this question ?
asked Jun 5, 2020 at 15:17
$endgroup$
3
$begingroup$
In most cases the solution is far from unique. For example, both $pmatrix{1 & 0cr 0 & 1cr}$ and $pmatrix{0 & 1cr 1 & 0cr}$ have row and column sums $1$.
This can be considered as a maximum flow problem with sources $r_i$ and sinks $c_i$, and upper bounds of $1$ on each arc. Polynomial-time algorithms are available.
answered Jun 5, 2020 at 15:33
Robert IsraelRobert Israel
432k26 gold badges324 silver badges632 bronze badges
$endgroup$
You must log in to answer this question.
Not the answer you’re looking for? Browse other questions tagged
.
Not the answer you’re looking for? Browse other questions tagged
.
Двоичные матрицы
В
математике прямоугольная таблица,
составленная из чисел, называется
матрицей.
Если матрица содержит только нули и
единицы, то она называется двоичной
матрицей.
Числовая часть таблицы 4.4 представляет
собой двоичную матрицу.
Таблица
4.5 также содержит двоичную матрицу.
|
Таблица |
||||||||||||||||||||
|
В
ней приведены сведения о посещении
четырьмя учениками трех факультативов.
Вам уже должно быть понятно, что единица
обозначает посещение, ноль – непосещение.
Из этой таблицы следует, например, что
Русанов посещает геологию и танцы,
Семенов – геологию и цветоводство и т.
д.
В
таблицах, представляющих собой двоичные
матрицы, отражается качественный
характер связи между объектами
(есть дорога – нет дороги; посещает – не
посещает и т. п.). Таблица 4.3 содержит
количественные характеристики
успеваемости учеников по предметам,
выраженные оценками пятибалльной
системы.
Мы
рассмотрели только два типа таблиц:
“объект-свойство” и “объект-объект”.
На практике используются и другие,
гораздо более сложные таблицы.
При
построении некоторых типов информационных
моделей одновременно используются
система графических элементов и знаковая
система. Так, в блок-схемах
алгоритмов используются различные
геометрические фигуры для обозначения
элементов алгоритма и формальный
алгоритмический язык для записи
инструкций программы (рис. 4.10).
Важную
роль играют информационные модели,
которые отображают иерархические
системы.
В биологии весь животный мир рассматривается
как иерархическая система (тип, класс,
отряд, семейство, род, вид), в информатике
используется иерархическая файловая
система и т. д.
|
|
|
Рис. |
В
иерархической информационной модели
объекты распределяются по уровням, от
первого (верхнего) уровня до нижнего
(последнего) уровня. На первом уровне
может располагаться только один элемент.
Основное отношение между уровнями
состоит в том, что элемент более высокого
уровня может состоять из нескольких
элементов нижнего уровня, при этом
каждый элемент нижнего уровня может
входить в состав только одного элемента
верхнего уровня.
Удобным
способом наглядного представления
иерархических информационных моделей
являются графы.
Элементы иерархической модели отображаются
в графе овалами (вершинами
графа).
Элементы
каждого уровня, кроме последнего,
находятся в отношении “состоять из”
к элементам более низкого уровня. Такая
связь между элементами отображается в
форме дуги
графа
(направленной линии в форме стрелки).
Графы,
имеющие одну вершину верхнего уровня,
напоминают деревья, которые растут
сверху вниз, поэтому называются деревьями.
Дуги дерева могут связывать объекты
только соседних иерархических уровней,
причем каждый объект нижнего уровня
может быть связан дугой только с одним
объектом верхнего уровня.
Для
описания исторического процесса смены
поколений семьи используются информационные
модели в форме генеалогического
дерева.
В качестве примера можно рассмотреть
фрагмент (X-XI века) генеалогического
дерева династии Рюриковичей (рис. 4.11).
|
|
|
Рис. |
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
Содержание:
- Матрицы: основные определения и понятия
- Умножение матрицы на число
- Сложение и вычитание матриц
- Умножение матриц
- Транспонирование матрицы
- Минор и алгебраическое дополнение
- Вычисление определителя
- Нахождение обратной матрицы
- Нахождение ранга матрицы
Матрицы широко применяются в математике для
компактной записи СЛАУ или систем дифференциальных уравнений. Тогда количество
строк матрицы соответствует количеству уравнений системы, а количество столбцов равно количеству неизвестных. Матричный
аппарат позволяет свести решение громоздких СЛАУ к компактным
операциям над матрицами.
На практике, они позволяют не делать лишних операций и сократить время выполнения задач.
Поэтому, будущим специалистам очень важно понять теорию матриц и научиться решать задачи с ними.
Перед изучением примеров решения задач советуем изучить теоретический материал по матрицам, прочитать
все определения и свойства. Список тем находится в правом меню.
Примеры по темам:
- Матрицы: основные определения и понятия
- Умножение матрицы на число
- Сложение и вычитание матриц
- Умножение матриц
- Транспонирование матрицы
- Минор и алгебраическое дополнение
- Вычисление определителя
- Нахождение обратной матрицы
- Нахождение ранга матрицы
Матрицы: основные определения и понятия
Теоретический материал по теме – основные определения и понятия матриц.
Пример
Задание. Чему равен элемент $ a_{23} $
матрицы $ A=left( begin{array}{rrr}{1} & {4} & {0} \ {-1} & {3} & {7}end{array}right) $ ?
Решение. Находим элемент, который стоит на пересечении второй строки и третьего столбца:
Таким образом, $a_{23}=7$.
Ответ. $a_{23}=7$
Умножение матрицы на число
Теоретический материал по теме – умножение матрицы на число.
236
проверенных автора готовы помочь в написании работы любой сложности
Мы помогли уже 4 430 ученикам и студентам сдать работы от решения задач до дипломных на отлично! Узнай стоимость своей работы за 15 минут!
Пример
Задание. Пусть $A=left( begin{array}{r}{3} \ {-1}end{array}right)$ .
Найти матрицу 2$A$.
Решение. $2 A=2 cdot left( begin{array}{r}{3} \ {-1}end{array}right)=left( begin{array}{c}{2 cdot 3} \ {2 cdot(-1)}end{array}right)=left( begin{array}{r}{6} \ {-2}end{array}right)$
Ответ. $2 A=left( begin{array}{r}{6} \ {-2}end{array}right)$
Сложение и вычитание матриц
Теоретический материал по теме – сложение и вычитание матриц.
Пример
Задание. Найти $A+B$, если
$A=left( begin{array}{rrr}{1} & {-2} & {4} \ {2} & {0} & {-1}end{array}right)$,
$B=left( begin{array}{lll}{5} & {2} & {3} \ {4} & {6} & {2}end{array}right)$
Решение. $C=A+B=left( begin{array}{rrr}{1} & {-2} & {4} \ {2} & {0} & {-1}end{array}right)+left( begin{array}{lll}{5} & {2} & {3} \ {4} & {6} & {2}end{array}right)=$
$=left( begin{array}{rrr}{1+5} & {-2+2} & {4+3} \ {2+4} & {0+6} & {-1+2}end{array}right)=left( begin{array}{lll}{6} & {0} & {7} \ {6} & {6} & {1}end{array}right)$
Ответ. $C=left( begin{array}{lll}{6} & {0} & {7} \ {6} & {6} & {1}end{array}right)$
Пример
Задание. Найти матрицу $C=A-3 B$,
если $A=left( begin{array}{rr}{1} & {2} \ {2} & {-1} \ {3} & {0}end{array}right), B=left( begin{array}{rr}{-1} & {1} \ {1} & {2} \ {0} & {0}end{array}right)$
Решение. $C=A-3 B=left( begin{array}{rr}{1} & {2} \ {2} & {-1} \ {3} & {0}end{array}right)-3 cdot left( begin{array}{rr}{-1} & {1} \ {1} & {2} \ {0} & {0}end{array}right)=$
$left( begin{array}{rr}{1} & {2} \ {2} & {-1} \ {3} & {0}end{array}right)-left( begin{array}{rr}{-3} & {3} \ {3} & {6} \ {0} & {0}end{array}right)=left( begin{array}{cc}{1-(-3)} & {2-3} \ {2-3} & {-1-6} \ {3-0} & {0-0}end{array}right)=left( begin{array}{rr}{4} & {-1} \ {-1} & {-7} \ {3} & {0}end{array}right)$
Ответ. $C=left( begin{array}{rr}{4} & {-1} \ {-1} & {-7} \ {3} & {0}end{array}right)$
Умножение матриц
Теоретический материал по теме – умножение матриц.
Пример
Задание. Вычислить $A B$ и $B A$,
если $A=left( begin{array}{rr}{1} & {-1} \ {2} & {0} \ {3} & {0}end{array}right), B=left( begin{array}{ll}{1} & {1} \ {2} & {0}end{array}right)$
Решение. Так как $A=A_{3 times 2}$ , а
$B=B_{2 times 2}$ , то произведение возможно и результатом операции умножения будет матрица
$C=C_{3 times 2}$ , а это матрица вида $C=left( begin{array}{cc}{c_{11}} & {c_{12}} \ {c_{21}} & {c_{22}} \ {c_{31}} & {c_{32}}end{array}right)$ .
Вычисли элементы матрицы $C$ :
$ c_{11}=a_{11} cdot b_{11}+a_{12} cdot b_{21}=1 cdot 1+(-1) cdot 2=-1 $
$ c_{12}=a_{11} cdot b_{12}+a_{12} cdot b_{22}=1 cdot 1+(-1) cdot 0=1 $
$ c_{21}=a_{21} cdot b_{11}+a_{22} cdot b_{21}=2 cdot 1+0 cdot 2=2 $
$ c_{22}=a_{21} cdot b_{12}+a_{22} cdot b_{22}=2 cdot 1+0 cdot 0=2 $
$ c_{31}=a_{31} cdot b_{11}+a_{32} cdot b_{21}=3 cdot 1+0 cdot 2=3 $
$ c_{31}=a_{31} cdot b_{12}+a_{32} cdot b_{22}=3 cdot 1+0 cdot 0=3 $
Итак, $C=A B=left( begin{array}{rl}{-1} & {1} \ {2} & {2} \ {3} & {3}end{array}right)$ .
Выполним произведения в более компактном виде:
$=left( begin{array}{rrr}{1 cdot 1+(-1) cdot 2} & {1 cdot 1+(-1) cdot 0} \ {2 cdot 1+0 cdot 2} & {2 cdot 1+0 cdot 0} \ {3 cdot 1+0 cdot 2} & {3 cdot 1+0 cdot 0}end{array}right)=left( begin{array}{rr}{-1} & {1} \ {2} & {2} \ {3} & {3}end{array}right)$
Найдем теперь произведение $D=B A=B_{2 times 2} cdot A_{3 times 2}$. Так как
количество столбцов матрицы $B$ (первый сомножитель) не совпадает с
количеством строк матрицы $A$ (второй сомножитель), то данное произведение
неопределенно. Умножить матрицы в данном порядке невозможно.
Ответ. $A B=left( begin{array}{rr}{-1} & {1} \ {2} & {2} \ {3} & {3}end{array}right)$ .
В обратном порядке умножить данные матрицы невозможно, так как количество столбцов матрицы
$B$ не совпадает с
количеством строк матрицы $A$ .
Транспонирование матрицы
Теоретический материал по теме – транспонирование матрицы.
Пример
Задание. Найти матрицу $A^{T}$, если
$A=left( begin{array}{rl}{1} & {0} \ {-2} & {3}end{array}right)$
Решение. $A^{T}=left( begin{array}{rr}{1} & {0} \ {-2} & {3}end{array}right)^{T}=left( begin{array}{rr}{1} & {-2} \ {0} & {3}end{array}right)$
Ответ. $A^{T}=left( begin{array}{rr}{1} & {-2} \ {0} & {3}end{array}right)$
Минор и алгебраическое дополнение
Теоретический материал по теме – минор и алгебраическое дополнение.
Пример
Задание. Найти минор
$M_{23}$ к элементу
$a_{23}$ определителя
$left| begin{array}{rrr}{1} & {2} & {-1} \ {1} & {0} & {3} \ {7} & {8} & {4}end{array}right|$ .
Решение. Вычеркиваем в заданном определителе вторую строку и третий столбец:
тогда $M_{23}=left| begin{array}{ll}{1} & {2} \ {7} & {8}end{array}right|$
Ответ. $M_{23}=left| begin{array}{ll}{1} & {2} \ {7} & {8}end{array}right|$
Пример
Задание. Найти алгебраическое дополнение
$A_{23}$ к элементу
$a_{23}$ определителя
$left| begin{array}{rrr}{1} & {2} & {-1} \ {1} & {0} & {3} \ {7} & {8} & {4}end{array}right|$ .
Решение. $A_{23}=(-1)^{2+3} cdot M_{23}=(-1)^{5} cdot left| begin{array}{ll}{1} & {2} \ {7} & {8}end{array}right|=-left| begin{array}{ll}{1} & {2} \ {7} & {8}end{array}right|$
Ответ. $A_{23}=-left| begin{array}{ll}{1} & {2} \ {7} & {8}end{array}right|$
Вычисление определителя
Теоретический материал по теме – методы вычисления определителей.
Пример
Задание. Вычислить определитель второго порядка
$left| begin{array}{rr}{11} & {-2} \ {7} & {5}end{array}right|$
Решение. $left| begin{array}{rr}{11} & {-2} \ {7} & {5}end{array}right|=11 cdot 5-(-2) cdot 7=55+14=69$
Ответ. $left| begin{array}{rr}{11} & {-2} \ {7} & {5}end{array}right|=69$
Пример
Задание. Вычислить определитель $left| begin{array}{rrr}{3} & {3} & {-1} \ {4} & {1} & {3} \ {1} & {-2} & {-2}end{array}right|$ методом треугольников.
Решение. $left| begin{array}{rrr}{3} & {3} & {-1} \ {4} & {1} & {3} \ {1} & {-2} & {-2}end{array}right|=3 cdot 1 cdot(-2)+4 cdot(-2) cdot(-1)+$
$+3 cdot 3 cdot 1-(-1) cdot 1 cdot 1-3 cdot(-2) cdot 3-4 cdot 3 cdot(-2)=54$
Ответ. $left| begin{array}{rrr}{3} & {3} & {-1} \ {4} & {1} & {3} \ {1} & {-2} & {-2}end{array}right|=54$
Пример
Задание. Вычислить определитель $left| begin{array}{lll}{1} & {2} & {3} \ {4} & {5} & {6} \ {7} & {8} & {9}end{array}right|$
Решение. Выполним следующие преобразования над строками определителя: из второй строки отнимем четыре
первых, а из третьей первую строку, умноженную на семь, в результате, согласно свойствам определителя, получим определитель,
равный данному.
$left| begin{array}{ccc}{1} & {2} & {3} \ {4} & {5} & {6} \ {7} & {8} & {9}end{array}right|=left| begin{array}{cccc}{1} & {2} & {3} \ {4-4 cdot 1} & {5-4 cdot 2} & {6-4 cdot 3} \ {7-7 cdot 1} & {8-7 cdot 2} & {9-7 cdot 3}end{array}right|=$
$=left| begin{array}{rrr}{1} & {2} & {3} \ {0} & {-3} & {-6} \ {0} & {-6} & {-12}end{array}right|=left| begin{array}{ccc}{1} & {2} & {3} \ {0} & {-3} & {-6} \ {0} & {2 cdot(-3)} & {2 cdot(-6)}end{array}right|=0$
Определитель равен нулю, так как вторая и третья строки являются пропорциональными.
Ответ. $left| begin{array}{lll}{1} & {2} & {3} \ {4} & {5} & {6} \ {7} & {8} & {9}end{array}right|=0$
Пример
Задание. Вычислить определитель
$Delta=left| begin{array}{rrrr}{-2} & {1} & {3} & {2} \ {3} & {0} & {-1} & {2} \ {-5} & {2} & {3} & {0} \ {4} & {-1} & {2} & {-3}end{array}right|$ приведением его к треугольному виду.
Решение. Сначала делаем нули в первом столбце под главной диагональю. Все преобразования
будет выполнять проще, если элемент $a_{11}$ будет
равен 1. Для этого мы поменяем местами первый и второй столбцы определителя, что, согласно свойствам определителя,
приведет к тому, что он сменит знак на противоположный:
$Delta=left| begin{array}{rrrr}{-2} & {1} & {3} & {2} \ {3} & {0} & {-1} & {2} \ {-5} & {2} & {3} & {0} \ {4} & {-1} & {2} & {-3}end{array}right|=-left| begin{array}{rrrr}{1} & {-2} & {3} & {2} \ {0} & {3} & {-1} & {2} \ {2} & {-5} & {3} & {0} \ {-1} & {4} & {2} & {-3}end{array}right|$
Далее получим нули в первом столбце, кроме элемента $a_{11}$ ,
для этого из третьей строки вычтем две первых, а к четвертой строке прибавим первую, будем иметь:
$Delta=-left| begin{array}{rrrr}{1} & {-2} & {3} & {2} \ {0} & {3} & {-1} & {2} \ {0} & {-1} & {-3} & {-4} \ {0} & {2} & {5} & {-1}end{array}right|$
Далее получаем нули во втором столбце на месте элементов, стоящих под главной диагональю. И снова, если
диагональный элемент будет равен $pm 1$ , то
вычисления будут более простыми. Для этого меняем местами вторую и третью строки (и при этом меняется на
противоположный знак определителя):
$Delta=left| begin{array}{rrrr}{1} & {-2} & {3} & {2} \ {0} & {-1} & {-3} & {-4} \ {0} & {3} & {-1} & {2} \ {0} & {2} & {5} & {-1}end{array}right|$
Далее делаем нули во втором столбце под главной диагональю, для этого поступаем следующим образом:
к третьей строке прибавляем три вторых, а к четвертой – две вторых строки, получаем:
$Delta=left| begin{array}{rrrr}{1} & {-2} & {3} & {2} \ {0} & {-1} & {-3} & {-4} \ {0} & {0} & {-10} & {-10} \ {0} & {0} & {-1} & {-9}end{array}right|$
Далее из третьей строки выносим (-10) за определитель и делаем нули в третьем столбце под
главной диагональю, а для этого к последней строке прибавляем третью:
$Delta=-10 left| begin{array}{rrrr}{1} & {-2} & {3} & {2} \ {0} & {-1} & {-3} & {-4} \ {0} & {0} & {1} & {1} \ {0} & {0} & {-1} & {-9}end{array}right|=$
$=-10 cdot left| begin{array}{cccc}{1} & {-2} & {3} & {2} \ {0} & {-1} & {-3} & {-4} \ {0} & {0} & {1} & {1} \ {0} & {0} & {0} & {-8}end{array}right|=(-10) cdot 1 cdot(-1) cdot 1 cdot(-8)=-80$
Ответ. $Delta=-80$
Нахождение обратной матрицы
Теоретический материал по теме – нахождение обратной матрицы.
Пример
Задание. Для матрицы $A=left( begin{array}{ll}{7} & {4} \ {5} & {3}end{array}right)$
найти обратную методом присоединенной матрицы.
Решение. Приписываем к заданной матрице
$A$ справа единичную матрицу второго порядка:
$Aleft|E=left( begin{array}{ll|ll}{7} & {4} & {1} & {0} \ {5} & {3} & {0} & {1}end{array}right)right.$
От первой строки отнимаем вторую (для этого от элемента первой строки отнимаем соответствующий элемент второй строки):
$Aleft|E sim left( begin{array}{rr|rr}{2} & {1} & {1} & {-1} \ {5} & {3} & {0} & {1}end{array}right)right.$
От второй строки отнимаем две первых:
$Aleft|E sim left( begin{array}{rr|rr}{2} & {1} & {1} & {-1} \ {1} & {1} & {-2} & {3}end{array}right)right.$
Первую и вторую строки меняем местами:
$Aleft|E sim left( begin{array}{rr|r|rr}{1} & {1} & {-2} & {3} \ {2} & {1} & {1} & {-1}end{array}right)right.$
От второй строки отнимаем две первых:
$Aleft|E sim left( begin{array}{rr|rr}{1} & {1} & {-2} & {3} \ {0} & {-1} & {5} & {-7}end{array}right)right.$
Вторую строку умножаем на (-1), а к первой строке прибавляем вторую:
$Aleft|E sim left( begin{array}{rr|rr}{1} & {0} & {3} & {-4} \ {0} & {1} & {-5} & {7}end{array}right)right.$
Итак, слева получили единичную матрицу, а значит матрица, стоящая в
правой части (справа от вертикальной черты), является обратной к исходной.
Таким образом, получаем, что $A^{-1}=left( begin{array}{rr}{3} & {-4} \ {-5} & {7}end{array}right)$
Ответ. $A^{-1}=left( begin{array}{rr}{3} & {-4} \ {-5} & {7}end{array}right)$
Пример
Задание. Найти обратную матрицу для $A=left( begin{array}{ll}{1} & {1} \ {1} & {2}end{array}right)$
Решение. Шаг 1. Находим определитель: $Delta=left| begin{array}{ll}{1} & {1} \ {1} & {2}end{array}right|=2-1=1 neq 0$
Шаг 2. $A^{prime}=left( begin{array}{rr}{2} & {-1} \ {-1} & {1}end{array}right)$
Шаг 3. $A^{-1}=frac{1}{Delta} cdot A^{prime}=left( begin{array}{rr}{2} & {-1} \ {-1} & {1}end{array}right)$
Ответ. $A^{-1}=left( begin{array}{rr}{2} & {-1} \ {-1} & {1}end{array}right)$
Пример
Задание. Найти обратную матрицу к матрице $A=left( begin{array}{rrr}{1} & {0} & {2} \ {2} & {-1} & {1} \ {1} & {3} & {-1}end{array}right)$
Решение. Вычисляем определитель матрицы:
$Delta=left| begin{array}{rrr}{1} & {0} & {2} \ {2} & {-1} & {1} \ {1} & {3} & {-1}end{array}right|=1 cdot(-1) cdot(-1)+2 cdot 3 cdot 2+0 cdot 1 cdot 1-$
$-1 cdot(-1) cdot 2-3 cdot 1 cdot 1-2 cdot 0 cdot(-1)=1+12+0+2-3+0=12 neq 0$
Так как определитель не равен нулю, то матрица имеет обратную.
Обратная матрица $A^{-1}$ к матрице
$A$ находится по формуле:
$A^{-1}=frac{1}{Delta} cdot widetilde{A}^{T}$
Найдем союзную матрицу $check{A}$ , для этого вычислим алгебраические
дополнения к элементам матрицы $A$ :
$A_{11}=(-1)^{1+1} left| begin{array}{rr}{-1} & {1} \ {3} & {-1}end{array}right|=(-1) cdot(-1)-3 cdot 1=1-3=-2$
$A_{12}=(-1)^{1+2} left| begin{array}{rr}{2} & {1} \ {1} & {-1}end{array}right|=-[2 cdot(-1)-1 cdot 1]=-(-2-1)=3$
$A_{13}=(-1)^{1+3} left| begin{array}{rr}{2} & {-1} \ {1} & {3}end{array}right|=2 cdot 3-1 cdot(-1)=6+1=7$
$A_{21}=(-1)^{2+1} left| begin{array}{rr}{0} & {2} \ {3} & {-1}end{array}right|=-[0 cdot(-1)-3 cdot 2]=-(0-6)=6$
$A_{22}=(-1)^{2+2} left| begin{array}{rr}{1} & {2} \ {1} & {-1}end{array}right|=1 cdot(-1)-1 cdot 2=-1-2=-3$
$A_{23}=(-1)^{2+3} left| begin{array}{cc}{1} & {0} \ {1} & {3}end{array}right|=-[1 cdot 3-1 cdot 0]=-(3-0)=-3$
$A_{31}=(-1)^{3+1} left| begin{array}{rr}{0} & {2} \ {-1} & {1}end{array}right|=0 cdot 1-(-1) cdot 2=0+2=2$
$A_{32}=(-1)^{3+2} left| begin{array}{cc}{1} & {2} \ {2} & {1}end{array}right|=-[1 cdot 1-2 cdot 2]=-(1-4)=3$
$A_{33}=(-1)^{3+3} left| begin{array}{rr}{1} & {0} \ {2} & {-1}end{array}right|=1 cdot(-1)-2 cdot 0=-1-0=-1$
Таким образом, $tilde{A}=left( begin{array}{rrr}{-2} & {3} & {7} \ {6} & {-3} & {-3} \ {2} & {3} & {-1}end{array}right)$
Транспонируем эту матрицу (т.е. строки матрицы делаем столбцами с тем же номером):
$widetilde{A}^{T}=left( begin{array}{rrr}{-2} & {6} & {2} \ {3} & {-3} & {3} \ {7} & {-3} & {-1}end{array}right)$
Итак, $A^{-1}=frac{1}{12} left( begin{array}{rrr}{-2} & {6} & {2} \ {3} & {-3} & {3} \ {7} & {-3} & {-1}end{array}right)$
Ответ. $A^{-1}=frac{1}{12} left( begin{array}{rrr}{-2} & {6} & {2} \ {3} & {-3} & {3} \ {7} & {-3} & {-1}end{array}right)$
Нахождение ранга матрицы
Теоретический материал по теме – нахождение ранга матрицы.
Пример
Задание. Найти ранг матрицы $A=left( begin{array}{cccc}{0} & {4} & {10} & {1} \ {4} & {8} & {18} & {7} \ {10} & {18} & {40} & {17} \ {1} & {7} & {17} & {3}end{array}right)$
Решение. С помощью элементарных преобразований над ее строками приведем матрицу $A$ к
ступенчатому виду. Для этого вначале от третьей строки отнимем две вторых:
$A sim left( begin{array}{cccc}{0} & {4} & {10} & {1} \ {4} & {8} & {18} & {7} \ {2} & {2} & {4} & {3} \ {1} & {7} & {17} & {3}end{array}right)$
От второй строки отнимаем четвертую строку, умноженную на 4; от третьей – две четвертых:
$A sim left( begin{array}{rrrr}{0} & {4} & {10} & {1} \ {0} & {-20} & {-50} & {-5} \ {0} & {-12} & {-30} & {-3} \ {1} & {7} & {17} & {3}end{array}right)$
Ко второй строке прибавим пять первых, к третьей – три третьих:
$A sim left( begin{array}{cccc}{0} & {4} & {10} & {1} \ {0} & {0} & {0} & {0} \ {0} & {0} & {0} & {0} \ {1} & {7} & {17} & {3}end{array}right)$
Меняем местами первую и вторую строчки:
$A sim left( begin{array}{cccc}{0} & {0} & {0} & {0} \ {0} & {4} & {10} & {1} \ {0} & {0} & {0} & {0} \ {1} & {7} & {17} & {3}end{array}right)$
Далее четвертую и первую строки:
$A sim left( begin{array}{cccc}{1} & {7} & {17} & {3} \ {0} & {4} & {10} & {1} \ {0} & {0} & {0} & {0} \ {0} & {0} & {0} & {0}end{array}right) Rightarrow r a n g A=2$
Ответ. $operatorname{rang} A=2$
Пример
Задание. Найти ранг матрицы $A=left( begin{array}{rrrr}{1} & {2} & {-1} & {-2} \ {2} & {4} & {3} & {0} \ {-1} & {-2} & {6} & {6}end{array}right)$ ,
используя метод окаймления миноров.
Решение. Минорами минимального порядка являются миноры первого порядка, которые равны элементам
матрицы $A$ . Рассмотрим, например, минор
$M_{1}=1 neq 0$ . расположенный в первой строке и первом
столбце. Окаймляем его с помощью второй строки и второго столбца, получаем минор
$M_{2}^{1}=left| begin{array}{ll}{1} & {2} \ {2} & {4}end{array}right|=0$ ; рассмотрим еще один минор второго
порядка, для этого минор $M_{1}$ окаймляем при
помощи второй строки и третьего столбца, тогда имеем минор $M_{2}^{2}=left| begin{array}{rr}{1} & {-1} \ {2} & {3}end{array}right|=5 neq 0$ ,
то есть ранг матрицы не меньше двух. Далее рассматриваем миноры третьего порядка, которые окаймляют минор
$M_{2}^{2}$ . Таких миноров два: комбинация
третьей строки со вторым столбцом или с четвертым столбцом. Вычисляем эти миноры:
$M_{3}^{1}=left| begin{array}{rrr}{1} & {2} & {-1} \ {2} & {4} & {3} \ {-1} & {-2} & {6}end{array}right|=0$
так как содержит два пропорциональных столбца (первый и второй); второй минор
$M_{3}^{2}=left| begin{array}{rrr}{1} & {-1} & {-2} \ {2} & {3} & {0} \ {-1} & {6} & {6}end{array}right|$
преобразуем следующим образом: к первой строке прибавим третью, а ко второй две третьих:
$M_{3}^{2}=left| begin{array}{rrr}{0} & {5} & {4} \ {0} & {15} & {12} \ {-1} & {6} & {6}end{array}right|=0$
И так как первая и вторая строки пропорциональны, то минор равен нулю.
Таким образом, все окаймляющие миноры третьего порядка равны нулю. А, значит, ранг матрицы $A$
равен двум: $operatorname{rang} A=2$
Ответ. $operatorname{rang} A=2$
Читать первую тему – основные определения и понятия матриц,
раздела матрицы.
Считать так же, но по модулю 2
а если при вычислении мне надо что-то вычитать из чего-то – это нормально? Например, при попытке вычислить алгебраическое дополнение элемента получил (-1)+(-1) – надо их смело сложить по модулю 2 и получить ноль?
Если у Вас обратная матрица целочисленная, можно взять ее элементы по модулю 2, получится то, что надо, иначе – нет.
Обратную пока так и не получил. то, что выдают скрипты – не целочисленное.
Брать все четные – 0, все нечетные – 1. Но если число меньше нуля, взять его модуль?
Ручками легко 
сосчитать самому.
А каким методом посоветуете?
Методом Гаусса – не получается чего-то. Да и строки надо складывать все по тому же модулю 2? перемножать их можно?
Через союзную матрицу – это надо посчитать 64 алгебраических дополнений (не назвал бы метод быстрым 
). И определитель, если не равен нулю, то равен 1, так?
P.S. А если взять то, что выдает мне стандартный скрипт, считающий методом Гаусса, домножить матрицу настолько, чтобы она стала целочисленной и привести ее элементы к виду “по модулю два” – выгорит?
— Пт сен 17, 2010 18:20:49 —
Ручками легко сосчитать самому.
Угу. Метод Гаусса над полем 
, за полчаса легко программируется.
в том-то и проблема, что я не разу не программист. К своему стыду.
Что такое двоичная матрица в информатике?
Бинарная матрица (двоичная матрица, (0, 1)-матрица) — матрица, элементы которой принадлежат множеству
Как обозначается матрица?
Матрицы обозначаются прописными (заглавными) буквами латинского алфавита, например, A, B, C,…. … Для обозначения элементов матрицы используются строчные буквы с двойным индексом, например: aij, где i – номер строки, j – номер столбца.
Как записать матрицу?
Матрица обычно обозначаются заглавными буквами латинского алфавитв. Матрица содержащая n строк и m столбцов, называется матрицей размера n×m. При необходимости размер матрицы записывается следующим образом: An×m.
Как нумеруются элементы матрицы?
Числа – элементы матрицы. Они нумеруются двумя индексами: i обозначает номер строки, j – номер столбца, на пересечении которых находится элемент . Сокращенно матрицу изображают следующим образом: A , или A . Обычно матрицы обозначают прописными буквами латинского алфавита: А, B, С, … .
Что такое размерность матрицы?
Матрицей размерности m×n называется прямоуголь- ная таблица чисел, содержащая m строк одинаковой длины (по n чисел в каждой строке) и n столбцов одинаковой длины (по m чисел в каждом столбце).
Что такое порядок в Матрице?
Матрица размера n×n называется квадратной, число n называется порядком матрицы. … Матрица, состоящая из одной строки, называется вектор-строкой, а матрица, состоящая из одного столбца, – вектор-столбцом.
Что такое транспонирование матрицы?
Транспонирование матрицы – это операция над матрицей, когда ее строки становятся столбцами с теми же номеромами. Если матрица A – это матрица размера m×n, то матрица AT имеет размер n×m .
Какие операции можно выполнять с матрицами?
Над матрицами можно выполнять определенные действия, которые, по аналогии с числами, называются сложение, вычитание и умножение. Так же существует действие, которое определяется только для матриц – это транспонирование матриц и нахождение обратной матрицы к данной.
Какая матрица является диагональной?
Диагональная матрица — квадратная матрица, все элементы которой, стоящие вне главной диагонали, равны нулю.
Что такое матрица виды матриц?
Виды матриц Матрицей называется прямоугольная таблица из чисел с некоторым количеством m строк и с некоторым количеством n столбцов. Числа m и n называются порядками или размерами матрицы.
Какая матрица называется верхней треугольной?
Треуго́льная ма́трица — в линейной алгебре квадратная матрица, у которой все элементы, стоящие ниже (или выше) главной диагонали, равны нулю.
Какая матрица называется невырожденной?
Невырожденная матрица (иначе неособенная матрица) ― квадратная матрица, определитель которой отличен от нуля. В противном случае матрица называется вырожденной.
Какая матрица является вырожденной?
Прямоугольная матрица (например, матрица сумм квадратов и кросс-произведений чисел) называется вырожденной, если элементы столбца (или строки) матрицы линейно зависимы, с элементами других столбцов (или строк).
Какая матрица называется обратной по отношению к данной матрице?
Обратной матрицей называется матрица, которая при умножении как справа, так и слева на данную матрицу дает единичную матрицу. … Квадратная матрица называется неособенной (невырожденной), если ее определитель не равен нулю.
Какая матрица имеет обратную матрицу?
Квадратная матрица обратима тогда и только тогда, когда она невырождена, то есть её определитель не равен нулю. … Для неквадратных матриц и вырожденных матриц обратных матриц не существует. Однако возможно обобщить это понятие и ввести псевдообратные матрицы, похожие на обратные по многим свойствам.
Как найти обратную матрицу к матрице?
Обратную матрицу найдем по формуле: , где – транспонированная матрица алгебраических дополнений соответствующих элементов матрицы .
- Находим определитель матрицы. …
- Находим матрицу миноров . …
- Находим матрицу алгебраических дополнений . …
- Находим транспонированную матрицу алгебраических дополнений . …
- Ответ:
Как найти обратную матрицу через алгебраические дополнения?
Алгоритм нахождения обратной матрицы с помощью алгебраических дополнений:
- Найти определитель (детерминант) матрицы A. …
- Найти матрицу миноров M.
- Из матрицы M найти матрицу алгебраических дополнений C*.
- Транспонировать матрицу (поменяем местами строки со столбцами) C*, получить матрицу C*T.
Как найти обратную матрицу с помощью элементарных преобразований?
Алгоритм нахождения обратной матрицы с помощью элементарных преобразований:
- Найти определитель (детерминант) матрицы A. Если определитель ≠ 0, то обратная матрица существует. …
- Дописываем справа единичную матрицу
- Делаем прямой ход. …
- Делаем обратный ход. …
- Элементы главной диагонали левой матрицы, преобразуем в единицы.
Как найти обратную матрицу с помощью метода Гаусса?
Получение обратной матрицы методом Гаусса относится к одному из точных (прямых) методов. Сначала записывается матрица, от которой необходимо найти обратную, а рядом с ней через черту записывается единичная диагональная матрица того же размера, вот так: ( 1 2 1 0 3 5 0 1 ) .
