Toeplitz Matrix Generation from 2 MATRICES

Hello Everyone,

I know we can define a row and column vector then use the toeplitz function to generate a toeplitz matrix, but how can I do that when I have two matrices instead of vectors?

Suppose I have matrices A and B, and I want to generate a toeplitz matrix such that;

T = [B              0            0    ...  0;
     A*B            B            0    ...  0;
     A^2*B          A*B          B    ...  0;
     .              .            .    ...  .
     .              .            .    ...  .
     A^(n-1)*B      A^(n-2)*B    .    ...  B];
         

size(A) is KxK

size(B) is KxM

[Stephen23]

@Saleh Msaddi: just to be sure: each of those * is an actual matrix multiply?

So the output T will have size (n+1)*K x (n+1)*M ?

[Saleh Msaddi]

Yeah that's true, actually I did a small edit so that the size of the output is (n*K) x (n*M)

Answer 1

[Stephen23]

>> A = rand(3,3);
>> B = rand(3,5);
>> N = 4;
>> F = @(n)(A^n)*B;
>> C = arrayfun(F,0:N,'uni',0);
>> C = [{zeros(size(B))},C];
>> X = 1+tril(1+toeplitz(0:N));
>> M = cell2mat(C(X))
M =
   0.69956   0.86686   0.20666   0.46757   0.94893   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000
   0.46328   0.36229   0.56426   0.85822   0.71207   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000
   0.77021   0.83655   0.31248   0.91479   0.48724   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000
   1.04535   1.08015   0.66586   1.30393   1.19787   0.69956   0.86686   0.20666   0.46757   0.94893   0.00000   0.00000  0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000
   1.19151   1.33153   0.52492   1.24584   1.20115   0.46328   0.36229   0.56426   0.85822   0.71207   0.00000   0.00000  0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000
   1.13782   1.29286   0.44387   1.14332   1.08196   0.77021   0.83655   0.31248   0.91479   0.48724   0.00000   0.00000  0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000
   1.92239   2.11932   0.91061   2.08183   1.97011   1.04535   1.08015   0.66586   1.30393   1.19787   0.69956   0.86686  0.20666   0.46757   0.94893   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000
   1.89463   2.07432   0.92888   2.08761   1.95665   1.19151   1.33153   0.52492   1.24584   1.20115   0.46328   0.36229  0.56426   0.85822   0.71207   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000
   1.73168   1.89633   0.84706   1.90766   1.78390   1.13782   1.29286   0.44387   1.14332   1.08196   0.77021   0.83655  0.31248   0.91479   0.48724   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000
   3.13506   3.43921   1.52166   3.43777   3.22857   1.92239   2.11932   0.91061   2.08183   1.97011   1.04535   1.08015  0.66586   1.30393   1.19787   0.69956   0.86686   0.20666   0.46757   0.94893   0.00000   0.00000   0.00000   0.00000  0.00000
   3.12822   3.43513   1.51057   3.42191   3.21683   1.89463   2.07432   0.92888   2.08761   1.95665   1.19151   1.33153  0.52492   1.24584   1.20115   0.46328   0.36229   0.56426   0.85822   0.71207   0.00000   0.00000   0.00000   0.00000  0.00000
   2.85612   3.13678   1.37809   3.12326   2.93605   1.73168   1.89633   0.84706   1.90766   1.78390   1.13782   1.29286  0.44387   1.14332   1.08196   0.77021   0.83655   0.31248   0.91479   0.48724   0.00000   0.00000   0.00000   0.00000  0.00000
   5.15716   5.66180   2.49328   5.64461   5.30487   3.13506   3.43921   1.52166   3.43777   3.22857   1.92239   2.11932  0.91061   2.08183   1.97011   1.04535   1.08015   0.66586   1.30393   1.19787   0.69956   0.86686   0.20666   0.46757  0.94893
   5.13621   5.63814   2.48462   5.62330   5.28412   3.12822   3.43513   1.51057   3.42191   3.21683   1.89463   2.07432  0.92888   2.08761   1.95665   1.19151   1.33153   0.52492   1.24584   1.20115   0.46328   0.36229   0.56426   0.85822  0.71207
   4.68804   5.14614   2.26789   5.13272   4.82305   2.85612   3.13678   1.37809   3.12326   2.93605   1.73168   1.89633  0.84706   1.90766   1.78390   1.13782   1.29286   0.44387   1.14332   1.08196   0.77021   0.83655   0.31248   0.91479  0.48724

And checking:

>> B % equal to main diagonal (e.g. top left corner and bottom right corner):
B =
   0.69956   0.86686   0.20666   0.46757   0.94893
   0.46328   0.36229   0.56426   0.85822   0.71207
   0.77021   0.83655   0.31248   0.91479   0.48724
>> A^N*B % equal to bottom left corner
ans =
   5.1572   5.6618   2.4933   5.6446   5.3049
   5.1362   5.6381   2.4846   5.6233   5.2841
   4.6880   5.1461   2.2679   5.1327   4.8230

[Saleh Msaddi]

Thank you Stephen that was really helpful. If we want to extend this;

Let's say that we generated that matrix M with size (n*K) x (n*M) where n=5

M = [B        0       0        0     0;
     A*B      B       0        0     0;
     A^2*B    A*B     B        0     0;
     A^3*B    A^2*B   A*B      B     0;
     A^4*B    A^3*B   A^2*B    A*B   B];

Now I want to formulate another matrix from M. The matrix R with size (n*K) x (r*M), suppose r = 3

 R = [B        0       0;
      A*B      B       0;
      A^2*B    A*B     B;
      A^3*B    A^2*B   A*B + B;
      A^4*B    A^3*B   A^2*B + A*B + B];
  

[Stephen23]

"Thank you Stephen that was really helpful."

Please remember to accept my answer, which is an easy way to show your thanks.

"Now I want to formulate another matrix from M."

Here are two approaches:

1- Reshape M and sum:

>> r = 3;
>> S = size(B);
>> X = (r-1)*S(2);
>> R = sum(reshape(M(:,1+X:end),(1+N)*S(1),S(2),[]),3);
>> R = [M(:,1:X),R]

2- Generate it directly from the cell array C:

>> G = @(c)sum(cat(4,c{:}),4);
>> R = cellfun(G,num2cell(C(X(:,r:end)),2),'uni',0);
>> R = cell2mat([C(X(:,1:r-1)),R]);
R =
   0.50803   0.17677   0.46034   0.53315   0.42568   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000   0.00000   0.00000
   0.65124   0.17361   0.79807   0.79063   0.60564   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000   0.00000   0.00000
   0.56518   0.78930   0.94494   0.78401   0.82100   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000  0.00000   0.00000   0.00000
   0.59637   0.20264   0.60473   0.65849   0.52190   0.50803   0.17677   0.46034   0.53315   0.42568   0.00000   0.00000  0.00000   0.00000   0.00000
   0.48435   0.43333   0.63425   0.59459   0.56181   0.65124   0.17361   0.79807   0.79063   0.60564   0.00000   0.00000  0.00000   0.00000   0.00000
   0.46132   0.14164   0.50890   0.53078   0.41410   0.56518   0.78930   0.94494   0.78401   0.82100   0.00000   0.00000  0.00000   0.00000   0.00000
   0.61965   0.28428   0.66840   0.70100   0.58041   0.59637   0.20264   0.60473   0.65849   0.52190   0.50803   0.17677  0.46034   0.53315   0.42568
   0.47587   0.15708   0.50209   0.53550   0.42220   0.48435   0.43333   0.63425   0.59459   0.56181   0.65124   0.17361  0.79807   0.79063   0.60564
   0.42143   0.25715   0.48832   0.49083   0.42740   0.46132   0.14164   0.50890   0.53078   0.41410   0.56518   0.78930  0.94494   0.78401   0.82100
   0.63535   0.27567   0.68280   0.71821   0.58917   0.61965   0.28428   0.66840   0.70100   0.58041   1.10439   0.37941  1.06507   1.19164   0.94758
   0.46832   0.24292   0.52017   0.53608   0.45309   0.47587   0.15708   0.50209   0.53550   0.42220   1.13559   0.60694  1.43232   1.38521   1.16744
   0.42591   0.16980   0.45486   0.48070   0.38915   0.42143   0.25715   0.48832   0.49083   0.42740   1.02650   0.93094  1.45384   1.31479   1.23510
   0.64594   0.29096   0.69878   0.73201   0.60408   0.63535   0.27567   0.68280   0.71821   0.58917   1.72404   0.66369  1.73347   1.89264   1.52799
   0.47725   0.20068   0.51175   0.53921   0.44012   0.46832   0.24292   0.52017   0.53608   0.45309   1.61146   0.76403  1.93440   1.92071   1.58965
   0.42834   0.20262   0.46747   0.48704   0.40516   0.42591   0.16980   0.45486   0.48070   0.38915   1.44793   1.18809  1.94216   1.80562   1.66251

Compare the bottom-right block:

>> A^2*B + A*B + B
ans =
   1.72404   0.66369   1.73347   1.89264   1.52799
   1.61146   0.76403   1.93440   1.92071   1.58965
   1.44793   1.18809   1.94216   1.80562   1.66251

[Saleh Msaddi]

Alright. Just to make sure, in the code you provided, the size of M is (n*K) x (n*M) and size of R is (n*k) x (r*M), right?

[Stephen23]

"...the size of M is (n*K) x (n*M) and size of R is (n*k) x (r*M), right?"

As far as I can tell those are the output sizes.

But you don't need to ask me: simply try the code on a few random input matrices of different sizes, with a few r and N values, and you can check the output sizes for yourself. Or you can reverse engineer the code and confirm that it does what you want (take it apart, figure out how it works, check the output of each line).