Алгоритм нахождения матрицы перестановок матрицы - PullRequest
Новая
       26

Алгоритм нахождения матрицы перестановок матрицы

0 голосов
/ 04 октября 2018

Я вижу несколько похожих вопросов:

Заданные элементы: 

elems =  [1,2,3,4] # dimensions 1x4

Если у меня есть вектор: 

M = [4,2,3,1] # dimensions 1x4

Я знаю, что есть некоторая матрица перестановок p, которую я могу умножить elems * p = M, которая в этом случае будет:

p = 
[ 
  0 0 0 1
  0 1 0 0 
  0 0 1 0 
  1 0 0 0 
] # dimensions 4x4

# eg: 
# elems * P = M
  1x4   4x4 = 1x4

Теперь, на мой вопрос, меня интересует, как бы это выглядело в случае, когда M - нековершинная, неквадратная матрица, например: 

M' = [ 
  4 2 3 1 
  4 3 2 1
  1 2 3 4
] # dimensions 3x4

Для того же 

elems' = [
 1 2 3 4
 1 2 3 4
 1 2 3 4
] # where this is now tripled to be conformant dimensions
# dimensions 3x4
#
# meaning P is still 4x4

Вы можете видеть M_prime и elems_prime в этом случае все еще только перестановки, но теперь многовариантные, а не просто один вектор, как первоначально.

Я знаю, что не могу просто сделать следующий вид вещей, потому что матрица не является квадратной и, следовательно, не обратимой: 

elems' * P = M'
         P = elems'^-1 * M'

# eg: 
# elems' * P = M'
  3x4   4x4  = 3x4

Когда я пытаюсь, по крайней мере в R, я вижу: 

> P <- ginv(elems_prime) %*% M_prime
     [,1]       [,2]       [,3]       [,4]
[1,]  0.1 0.07777778 0.08888889 0.06666667
[2,]  0.2 0.15555556 0.17777778 0.13333333
[3,]  0.3 0.23333333 0.26666667 0.20000000
[4,]  0.4 0.31111111 0.35555556 0.26666667

Это возвращает мне M '? 

> elems_prime %*% P
     [,1]     [,2]     [,3] [,4]
[1,]    3 2.333333 2.666667    2
[2,]    3 2.333333 2.666667    2
[3,]    3 2.333333 2.666667    2

!= M' # No, does not.

Так что это не правильно.

Мои вопросы:

  1. Чтоправильный P, который будет правильно переставлять матрицу элементов в матрицу M?
  2. Как называется алгоритм его поиска?(реализация в R, Haskell или псевдокоде хороша)
  3. Есть ли способ ограничить значения P целыми числами, предпочтительно 0 или 1?

для воспроизводимости R 

> dput(elems_prime)
structure(c(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4), .Dim = 3:4)
> dput(M_prime)
structure(c(4, 4, 1, 2, 3, 2, 3, 2, 3, 1, 1, 4), .Dim = 3:4)

Ответы [ 2 ]

0 голосов
/ 04 октября 2018

Обратите внимание, что пространство столбца M' имеет более высокий порядок, чем пространство столбца elem'.Это подразумевает, что не существует линейного отображения от elem' до M', потому что линейное отображение не может увеличить пространство строк или столбцов матрицы (полезно думать об этом как о преобразовании базиса).

Из этого следует, что любой M', сгенерированный elem' * P, может иметь ранг не более 1, оставляя только обычные матрицы перестановок в качестве кандидатов на P'

Это совершенно другоевопрос, если мы посмотрим на переход от M' обратно к elem, и эта асимметрия также заслуживает внимания.

0 голосов
/ 04 октября 2018

Когда М не является вектором, это невозможно.

Вот почему.В общем, если мы умножим матрицу nxm на матрицу mxp, мы получим матрицу nxp.Здесь elems - это вектор, представляющий собой матрицу 1x4, поэтому elems * P должна быть некоторой матрицей 1x?.Делая P длиннее, вы можете сделать M длиннее, но вам придется изменить elems, чтобы сделать M выше.

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

...