I want to build the matrix

I want to build the matrix G from a square matrix A, which has n×n dimensions.

The matrix G is defined as :

G = [ I O O O ...;

A I O O ... ;

A^2 A I O ...;

A^3 A^2 A I ...]

where:

• I is the n×n identity matrix (I=eye(n)),
• O is the n×n zero matrix (O=zeros(n)).

The resulting G has dimensions (n⋅m)×(n⋅m), where m is the number of block rows and columns in G

Can any one Help me

Thanx

[Mr. Pavl M.]

Do you need the G to contain more powers of A, like A^4, A^5 till m or just powers of A till A^3?

Do you need it in loop or loop-free solution?

Something like (approximately): G = [eye(n) zeros((m-1)*n,(m-1)*n);A eye(n) zeros((m-2)*n,(m-2)*n); A*A A eye(n) zeros((m-3)*n,(m-3)*n);A*A*A A*A A eye(n) zeros((m-4)*n,(m-4)*n) ?

[Mr. Pavl M.]

• Good question and good answer of Stephen23 and M. Agarwal, I checked both are correct, first is with no explicit loops, second is with 1 loop, I tested the running times and in 2 IDEs (both in Mt-b and Oc-e it runs, who will require it in TCE Julia, in TCE Python?), the 2 constructing methods summarized: as well,why function runs faster?:

clc
clear all
close all

m = 4;
n = 3;
A = randi(9,n)

A = 3×3

9 7 9 5 5 8 5 2 7

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

C = [{zeros(n),eye(n)},arrayfun(@(p)A^p,1:m-1,'uni',0)];

tic
t1 = cputime;
G1 = cell2mat(C(1+tril(toeplitz(1:m))))

G1 = 12×12

1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 9 7 9 1 0 0 0 0 0 0 0 0 5 5 8 0 1 0 0 0 0 0 0 0 5 2 7 0 0 1 0 0 0 0 0 0 161 116 200 9 7 9 1 0 0 0 0 0 110 76 141 5 5 8 0 1 0 0 0 0 90 59 110 5 2 7 0 0 1 0 0 0 3029 2107 3777 161 116 200 9 7 9 1 0 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

toc

Elapsed time is 0.023803 seconds.

t2 = cputime;
display(t2-t1)

    0.0400

function G = constructG(A, m)
n = size(A, 1);

% Create block diagonal of identity matrices
G = kron(eye(m), eye(n));

% Fill lower triangular blocks with powers of A
current_power = A;
for i = 1:m-1
    % Fill the i-th subdiagonal
    for j = 1:m-i
        row_idx = (i+j-1)*n + (1:n);
        col_idx = (j-1)*n + (1:n);
        G(row_idx, col_idx) = current_power;
    end
    
    if i < m - 1
        current_power = current_power * A;
    end
end
end

tic
t1 = cputime;
G2 = constructG(A, m)

G2 = 12×12

1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 9 7 9 1 0 0 0 0 0 0 0 0 5 5 8 0 1 0 0 0 0 0 0 0 5 2 7 0 0 1 0 0 0 0 0 0 161 116 200 9 7 9 1 0 0 0 0 0 110 76 141 5 5 8 0 1 0 0 0 0 90 59 110 5 2 7 0 0 1 0 0 0 3029 2107 3777 161 116 200 9 7 9 1 0 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

toc

Elapsed time is 0.032379 seconds.

t2 = cputime;
display(t2-t1)

    0.0300

[Husam]

Thank you very much and Happy New Year

Answer 1

[Malay Agarwal]

Hi @Husam,

You can build the required matrix using the following function:

function G = constructG(A, m)
    n = size(A, 1);
    
    % Create block diagonal of identity matrices
    G = kron(eye(m), eye(n));
    
    % Fill lower triangular blocks with powers of A
    current_power = A;
    for i = 1:m-1
        % Fill the i-th subdiagonal
        for j = 1:m-i
            row_idx = (i+j-1)*n + (1:n);
            col_idx = (j-1)*n + (1:n);
            G(row_idx, col_idx) = current_power;
        end
        
        if i < m - 1
            current_power = current_power * A;
        end
    end
end

You can use the function as follows:

A = randi(5, 3)

A = 3×3

1 1 5 1 4 3 2 1 3

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

G = constructG(A, 4)

G = 12×12

1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 5 1 0 0 0 0 0 0 0 0 1 4 3 0 1 0 0 0 0 0 0 0 2 1 3 0 0 1 0 0 0 0 0 0 12 10 23 1 1 5 1 0 0 0 0 0 11 20 26 1 4 3 0 1 0 0 0 0 9 9 22 2 1 3 0 0 1 0 0 0 68 75 159 12 10 23 1 1 5 1 0 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

Here are some details on the implementation:

• The kron() function is used to create a matrix where each block diagonal is the identity matrix .
• Then, the lower triangular blocks are filled with the powers of A. The powers of A are calculated incrementally to make the function more efficient.

Refer to the following resources for more information:

• eye() function - https://www.mathworks.com/help/matlab/ref/eye.html
• kron() function - https://www.mathworks.com/help/matlab/ref/kron.html

Hope this helps!

[Husam]

Thank you very much and Happy New Year

Answer 2

[Stephen23]

m = 4;
n = 3;
A = randi(9,n)

A = 3×3

7 4 2 5 3 5 9 7 7

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

C = [{zeros(n),eye(n)},arrayfun(@(p)A^p,1:m-1,'uni',0)];
G = cell2mat(C(1+tril(toeplitz(1:m))))

G = 12×12

1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 7 4 2 1 0 0 0 0 0 0 0 0 5 3 5 0 1 0 0 0 0 0 0 0 9 7 7 0 0 1 0 0 0 0 0 0 87 54 48 7 4 2 1 0 0 0 0 0 95 64 60 5 3 5 0 1 0 0 0 0 161 106 102 9 7 7 0 0 1 0 0 0 1311 846 780 87 54 48 7 4 2 1 0 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

[Husam]

Thank you very much and Happy New Year