Turning matrix diagonals to columns

Question

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!

Answer 1

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.

Answer 2

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.