Вычислительная математика. Задача о транспонировании

[Zloi_templar]

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


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

[Evgenjy]

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

[Евгений Машеров]

Умножением можно, сложением нельзя.

[B@R5uk]

Возьмём матрицу 2 на 2. Если её умножить на такую матрицу (не важно с какой стороны):

$$\left( \begin{matrix} 0 & 1 \\ 1 & 0 \\ \end{matrix} \right)$$

то столбцы (или строки) поменяются местами. При умножении на единичную — не меняется ничего. Больше нет вариантов, когда элементы остаются прежними. А нам нужно первый элемент первой строки оставить на месте, а второй элемент первой строки сделать первым элементом второй строки. Аналогичная ситуация сохраняется и в случае большего числа строк/столбцов квадратной матрицы: можно умножением как угодно их переставить. Так что ответ на вашу задачу в рамках поставленных ограничений (использование операций над матрицами): нет, не возможно.

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

[ewert]

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

[Zloi_templar]

Цитата:

Умножением можно, сложением нельзя.

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

Цитата:

Возьмём матрицу 2 на 2. Если её умножить на такую матрицу (не важно с какой стороны):

$$\left( \begin{matrix} 0 & 1 \\ 1 & 0 \\ \end{matrix} \right)$$

то столбцы (или строки) поменяются местами. При умножении на единичную — не меняется ничего. Больше нет вариантов, когда элементы остаются прежними. А нам нужно первый элемент первой строки оставить на месте, а второй элемент первой строки сделать первым элементом второй строки. Аналогичная ситуация сохраняется и в случае большего числа строк/столбцов квадратной матрицы: можно умножением как угодно их переставить. Так что ответ на вашу задачу в рамках поставленных ограничений (использование операций над матрицами): нет, не возможно.

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

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

Цитата:

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

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

[B@R5uk]

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, пожалуйста, сформулируйте ещё раз, но чётко, что вам нужно.

[Evgenjy]

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$ далеко не всегда имеет решение.

[Evgenjy]

Evgenjy в сообщении #1028033 писал(а):

Тогда уравнение $(XA)Y=A^T$ относительно $Y$ далеко не всегда имеет решение.

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

[B@R5uk]

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

[Evgenjy]

B@R5uk в сообщении #1028097 писал(а):

универсальные матрицы $X$ и $Y$

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

[Евгений Машеров]

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

[Zloi_templar]

Цитата:

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*? и на что домножать?

[ewert]

B@R5uk в сообщении #1028097 писал(а):

топик-стартеру нужны универсальные матрицы $X$ и $Y$, которые не будут зависеть от матрицы $A$,

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

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

[arseniiv]

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