Turning matrix diagonals to columns

1
votes

I am looking for a matrix operation of the form: B = M*A*N where A is some general square matrix and M and N are the matrices I want to find. Such that the columns of B are the diagonals of A. The first column the main diagonal, the second the diagonal shifted by 1 from the main and so on.

e.g. In MATLAB syntax: 

A = [1, 2, 3 
     4, 5, 6 
     7, 8, 9]

and 

B = [1, 2, 3 
     5, 6, 4 
     9, 7, 8]

Edit: It seems a pure linear algebra solution doesn't exist. So I'll be more precise about what I was trying to do:

For some vector v of size 1 x m. Then define C = repmat(v,m,1). My matrix is A = C-C.';. Therefore, A is essentially all differences of values in v but I'm only interested in the difference up to some distance between values. Those are the diagonals of A; but m is so large that the construction of such m x m matrices causes out-of-memory issues. I'm looking for a way to extract those diagonals in a way that is as efficient as possible (in MATLAB).

Thanks!

2
matlablinear-algebraalgebramatrix-decomposition
What relationship can you assume between M and N? Is N = M^-1? That would simplify the problem – titus.andronicus
You effectively have one equation (B=M*A*N) and two unknowns (M and N), need more information to solve this! Or do you just want a function which sets up matrix B for a given A? – Wolfie
Yes. M and N have freedom but I don't know of a any relation between them. The transformation should just work for general A with M N some constant matrices. – AsaridBeck91
M N some constant matrices (non dependent on A values). Setting A the identity matrix shows that MN results in a matrix with first column of ones and all other entries 0 since the identity has ones along the main diagonal and 0 else. But I don't see how this helps. – AsaridBeck91
Is this a linear algebra homework? – Alexander Kemp

2 Answers

1
votes

If you're not actually looking for a linear algebra solution, then I would argue that constructing three additional matrices the same size as A using two matrix multiplications is very inefficient in both time and space complexity. I'm not sure it's even possible to find a matrix solution, given my limited knowledge of linear algebra, but even if it is it's sure to be messy.

Since you say you only need the values along some diagonals, I'd construct only those diagonals using diag:

A = [1 2 3;
     4 5 6;
     7 8 9];
m = size(A, 1);   % assume A is square
k = 1;            % let's get the k'th diagonal
kdiag = [diag(A, k); diag(A, k-m)];

kdiag =

   2
   6
   7

Diagonal 0 is the main diagonal, diagonal m-1 (for an mxm matrix) is the last. So if you wanted all of B you could easily loop:

B = zeros(size(A));
for k = 0:m-1
   B(:,k+1) = [diag(A, k); diag(A, k-m)];
end

B =

   1   2   3
   5   6   4
   9   7   8

From the comments:

For v some vector of size 1xm. Then B=repmat(v,m,1). My matrix is A=B-B.'; A is essentially all differences of values in v but I'm only interested in the difference up to some distance between values.

Let's say 

m = 4;
v = [1 3 7 11];

If you construct the entire matrix,

B = repmat(v, m, 1);
A = B - B.';

A =
    0    2    6   10
   -2    0    4    8
   -6   -4    0    4
  -10   -8   -4    0

The main diagonal is zeros, so that's not very interesting. The next diagonal, which I'll call k = 1 is

[2 4 4 -10].'

You can construct this diagonal without constructing A or even B by shifting the elements of v:

k = 1;
diag1 = circshift(v, m-k, 2) - v;

diag1 =

    2    4    4  -10

The main diagonal is given by k = 0, the last diagonal by k = m-1.

1
votes

You can do this using the function toeplitz to create column indices for the reshuffling, then convert those to a linear index to use for reordering A, like so:

>> A = [1 2 3; 4 5 6; 7 8 9]
A =
     1     2     3
     4     5     6
     7     8     9
>> n = size(A, 1);
>> index = repmat((1:n).', 1, n)+n*(toeplitz([1 n:-1:2], 1:n)-1);
>> B = zeros(n);
>> B(index) = A
B =
     1     2     3
     5     6     4
     9     7     8

This will generalize to any size square matrix A.