2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Вычислительная математика. Задача о транспонировании
Сообщение16.06.2015, 11:11 


16/06/15
13
Есть произвольная прямоугольная матрица. Можно ли транспонировать исходную матрицу умножением или сложением с матрицей, последовательностью матриц?
Если нет, то доказать это


Изначально задача была про матрицу перестановок, через нее нельзя транспонировать.
Поставили вопрос про матрицу преобразований
Рассматривал ситуацию с умножением на матрицу поворота относительно главной диагонали на 180 градусов, забраковали, так как только для квадратных матриц. В итоге пришел к выводу что нельзя, но как доказать не знаю.
Есть идеи?

 Профиль  
                  
 
 Re: Вычислительная математика. Задача о транспонировании
Сообщение16.06.2015, 15:36 


13/08/14
349
Если матрицу $m\times l$ умножить на матрицу $l\times k$ то получим матрицу $m\times k$. Если результирующая матрица есть транспонированная вторая матрица, то $m=k$ и $k=l$. Тогда все матрицы получаются квадратные. То же получается по отношению к транспонированию первой матрицы.

 Профиль  
                  
 
 Re: Вычислительная математика. Задача о транспонировании
Сообщение16.06.2015, 16:21 
Заслуженный участник
Аватара пользователя


11/03/08
9490
Москва
Умножением можно, сложением нельзя.

 Профиль  
                  
 
 Re: Вычислительная математика. Задача о транспонировании
Сообщение16.06.2015, 17:23 
Аватара пользователя


26/05/12
1534
приходит весна?
Возьмём матрицу 2 на 2. Если её умножить на такую матрицу (не важно с какой стороны):
$$\left( \begin{matrix}
   0 & 1  \\
   1 & 0  \\
\end{matrix} \right)$$то столбцы (или строки) поменяются местами. При умножении на единичную — не меняется ничего. Больше нет вариантов, когда элементы остаются прежними. А нам нужно первый элемент первой строки оставить на месте, а второй элемент первой строки сделать первым элементом второй строки. Аналогичная ситуация сохраняется и в случае большего числа строк/столбцов квадратной матрицы: можно умножением как угодно их переставить. Так что ответ на вашу задачу в рамках поставленных ограничений (использование операций над матрицами): нет, не возможно.

Однако, если выйти за пределы этих ограничений и рассматривать матрицы, как тензоры 2-го ранга, к которым применимы операции свёртки с тензорами произвольного ранга, то ответ на вашу задачу станет положительным. Для любой тензора 2-го ранга найдётся тензор 4-го ранга, который путём свёртки с исходным, все или часть элементов переставит на место любое место нового тензора 2-го ранга. Доказательство заключается просто в непосредственном выписывании этого перестановочного тензора.

 Профиль  
                  
 
 Re: Вычислительная математика. Задача о транспонировании
Сообщение16.06.2015, 19:31 
Заслуженный участник


11/05/08
32166
В неквадратном случае одним умножением (только слева или только справа) -- естественно, нельзя, попросту размеры не сойдутся. А обоими сразу -- почему бы и нет?

 Профиль  
                  
 
 Re: Вычислительная математика. Задача о транспонировании
Сообщение17.06.2015, 02:34 


16/06/15
13
Цитата:
Умножением можно, сложением нельзя.

Каким образом?

Цитата:
Возьмём матрицу 2 на 2. Если её умножить на такую матрицу (не важно с какой стороны):
$$\left( \begin{matrix}
   0 & 1  \\
   1 & 0  \\
\end{matrix} \right)$$то столбцы (или строки) поменяются местами. При умножении на единичную — не меняется ничего. Больше нет вариантов, когда элементы остаются прежними. А нам нужно первый элемент первой строки оставить на месте, а второй элемент первой строки сделать первым элементом второй строки. Аналогичная ситуация сохраняется и в случае большего числа строк/столбцов квадратной матрицы: можно умножением как угодно их переставить. Так что ответ на вашу задачу в рамках поставленных ограничений (использование операций над матрицами): нет, не возможно.

Однако, если выйти за пределы этих ограничений и рассматривать матрицы, как тензоры 2-го ранга, к которым применимы операции свёртки с тензорами произвольного ранга, то ответ на вашу задачу станет положительным. Для любой тензора 2-го ранга найдётся тензор 4-го ранга, который путём свёртки с исходным, все или часть элементов переставит на место любое место нового тензора 2-го ранга. Доказательство заключается просто в непосредственном выписывании этого перестановочного тензора.


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

Цитата:
В неквадратном случае одним умножением (только слева или только справа) -- естественно, нельзя, попросту размеры не сойдутся. А обоими сразу -- почему бы и нет?

Можно хоть сколько угодно умножать слева и справа, в случае если возможно нужно выписать вид матрицы или алгоритм

 Профиль  
                  
 
 Re: Вычислительная математика. Задача о транспонировании
Сообщение17.06.2015, 03:23 
Аватара пользователя


26/05/12
1534
приходит весна?
Zloi_templar в сообщении #1028011 писал(а):
...а любую матрицу, как например в приведении к диагональному или треугольному виду...
В этом случае у вас матрица-множитель является функцией транспонируемой матрицы. Какой тогда смысл говорить об умножении? Просто взяли элементы и перемешали как хочется. Или даже так: "На какую матрицу надо умножить матрицу A, чтобы получить матрицу B?" Это совсем другая задача, не та, что вы озвучили в первом посте.

Zloi_templar в сообщении #1027698 писал(а):
Если нет, то доказать это
Умножение матрицы A на какую-либо матрицу равносильно свёртке соответствующего А тензора 2-го ранга с некоторым специального вида тензором 4-го ранга. Когда запишите перестановочный тензор, то окажется, что он не сможет быть представлен в этом специальном виде.

ewert в сообщении #1027892 писал(а):
А обоими сразу -- почему бы и нет?
Не вводите людей в заблуждение. Умножение с одной стороны переставляет строки (или перемешивает их в суперпозицию), с другой стороны — делает тоже со столбцами. Если же считаете своё утверждение верным, то приведите, пожалуйста, пример для матрицы 2 на 2. Возможно, мы о разных вещах говорим.

Zloi_templar в сообщении #1028011 писал(а):
...или алгоритм
Алгоритм транспонирования ничего общего с умножением не имеет. Матрице соответствует массив и вспомогательная информация в виде размеров матрицы и указателя на этот массив. Транспонирование заключается в создании нового массива с новой вспомогательной информацией (размеры матрицы поменяны местами) и в копировании элементов на соответствующие им новые места. Никакого умножения. Или же вас интересует алгоритм, который преобразует матрицу "на месте"?

Есть ещё формально математическое транспонирование, использующее нематематическое действие "измерение формы матрицы". Сначала матрицу (допустим размера N на M), подлежащую транспонированию "превращаем" с столбец (с числом элементов, равному число элементов исходной матрицы), просто выписывая друг под другом все столбцы исходной матрицы по очереди. Затем умножаем этот столбец на желаемую перестановочную матрицу (размера K на K, где $K=M\times N$) и снова производим эту же нематематическую операцию измерения формы матрицы. Таким образом можно переставить любой элемент на любое желаемое место.

Zloi_templar, пожалуйста, сформулируйте ещё раз, но чётко, что вам нужно.

 Профиль  
                  
 
 Re: Вычислительная математика. Задача о транспонировании
Сообщение17.06.2015, 08:37 


13/08/14
349
ewert в сообщении #1027892 писал(а):
А обоими сразу -- почему бы и нет?

Сводиться к решению уравнения $XAY=A^T$, где размеры матриц $(n\times m)(m\times n)(n\times m)=(n\times m)$. Пусть $n>m$. Размер матрицы $XA$ будет $(n\times n)$, а ранг не более $m$, т. е. меньше $n$. Тогда уравнение $(XA)Y=A^T$ относительно $Y$ далеко не всегда имеет решение.

 Профиль  
                  
 
 Re: Вычислительная математика. Задача о транспонировании
Сообщение17.06.2015, 11:08 


13/08/14
349
Evgenjy в сообщении #1028033 писал(а):
Тогда уравнение $(XA)Y=A^T$ относительно $Y$ далеко не всегда имеет решение.

С другой стороны в том же уравнении, записанным по другому, $X(AY)=A^T$ матрица $(AY)$ имеет размер $m\times m$, можно подобрать матрицу $Y$, чтобы $(AY)$ имела ранг $m$, а, следовательно обратную $(AY)^{-1}$.

 Профиль  
                  
 
 Re: Вычислительная математика. Задача о транспонировании
Сообщение17.06.2015, 12:31 
Аватара пользователя


26/05/12
1534
приходит весна?
Evgenjy, вы пытаетесь подобрать матрицы $X$ и $Y$, которые будут функциями матрицы $A$. Если я правильно понял, то топик-стартеру нужны универсальные матрицы $X$ и $Y$, которые не будут зависеть от матрицы $A$, то есть будут для всех матриц $A$ одинаковыми и во всех случаях осуществлять перестановку элементов.

 Профиль  
                  
 
 Re: Вычислительная математика. Задача о транспонировании
Сообщение17.06.2015, 13:18 


13/08/14
349
B@R5uk в сообщении #1028097 писал(а):
универсальные матрицы $X$ и $Y$

Что нет универсальных, на мой взгляд,- очевидно. Если бы это было возможно многое в теории матриц было бы построено иначе и многое-многое другое в математике, что с этим связано. Кроме того я понимаю, что и нахождение матриц, как функций исходной, практического значения не имеет, поскольку, например, взятие обратной матрицы включает в себя операцию транспонирования. Эта задача - только игра.

 Профиль  
                  
 
 Re: Вычислительная математика. Задача о транспонировании
Сообщение17.06.2015, 15:51 
Заслуженный участник
Аватара пользователя


11/03/08
9490
Москва
Например, можно взять сингулярное разложение $A=S\Lambda C$ и домножить $C^TS^TAC^TS^T=C^T\Lambda S^T=A^T$
Но, разумеется, "универсальной отмычки" не получится.

 Профиль  
                  
 
 Re: Вычислительная математика. Задача о транспонировании
Сообщение17.06.2015, 17:46 


16/06/15
13
Цитата:
Evgenjy, вы пытаетесь подобрать матрицы $X$ и $Y$, которые будут функциями матрицы $A$. Если я правильно понял, то топик-стартеру нужны универсальные матрицы $X$ и $Y$, которые не будут зависеть от матрицы $A$, то есть будут для всех матриц $A$ одинаковыми и во всех случаях осуществлять перестановку элементов.

ну матрицы X и Y могут отличаться от по размерам для разных случаев, но, как вы верно подметили, они должны всегда осуществлять перестановку

Цитата:
Например, можно взять сингулярное разложение $A=S\LambdaC$ и домножить $C^TS^TAC^TS^T=C^T\Lambda S^T=A^T$
Но, разумеется, "универсальной отмычки" не получится.

вы имеете ввиду А=UsigmaV*? и на что домножать?

 Профиль  
                  
 
 Re: Вычислительная математика. Задача о транспонировании
Сообщение17.06.2015, 18:52 
Заслуженный участник


11/05/08
32166
B@R5uk в сообщении #1028097 писал(а):
топик-стартеру нужны универсальные матрицы $X$ и $Y$, которые не будут зависеть от матрицы $A$,


Неправильно понимаете: если бы так, то в параллели не предлагалось бы прибавление матриц. Которое для сочинения оператора транспонирования откровенно абсурдно, а вот при индивидуальном подборе -- отнюдь не всегда.

Да, сингулярное. А ещё лучше, наверное, просто полярное с обрубанием хвостов.

 Профиль  
                  
 
 Re: Вычислительная математика. Задача о транспонировании
Сообщение18.06.2015, 02:14 
Заслуженный участник


27/04/09
28128
Всё равно интересно, чем вызван вопрос. Транспонирование, производимое прямо или почти прямо по определению, гарантированно $O(n^2)$, где $n$ — максимум от числа строк и числа столбцов. А с умножением что сейчас достигнуто?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 25 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group