Codimensions of Generalized Matrix Products

Codimensions of Generalized Matrix Products

This software provides a Python script codimension.py for computing the codimension of a generalized matrix product in canonical form, based on the formulas developed in [1]. The use of this software is best illustrated by an example.

Example

Assume we have a generalized matrix product of length 4 with sign tuple (+1,-1,+1,-1). The canonical form has 2 Jordan tuples of size 2 belonging to the eigenvalue 1, and 2 left singular tuples of size 1 at positions (1,3) and (1,4), respectively. To specify this structure, save
s = (+1,-1,+1,-1)
J(2,1)
J(2,1)
R(1,1,3)
R(1,1,4)
in a file called, e.g., example.dat. See the documentation of codimension.py for specifying other type of canonical tuples. Typing python codimension.py < example.dat yields the following output.

Statistics of the example.
Length of tuples:
=================
p = 4

Dimension tuple:
================
n = (6, 8, 8, 7)

Sign tuple:
===========
s = (+1, -1, +1, -1)

Canonical blocks:
=================

                 +1 -1 +1 -1
#1       J(2,1):  J  I  I  I 
#2       J(2,1):  J  I  I  I 
#3     R(1,1,3):  FT I  G  I 
#4     R(1,1,4):  FT I  I  GT
Interactions. (Application of the procedure described in Section 3 of [1] to count all possible interactions between the canonical tuples.)
Pairwise interactions
=====================

Block #1, J(2,1), interacting with block #1, J(2,1)
   [++]        Equation and variant: I:1
   [BI]        Tuple & modified tuple: JJ --> JJ
   [IC]        Interaction: min(l,m) = 2

Block #1, J(2,1), interacting with block #2, J(2,1)
   [++]        Equation and variant: I:1
   [BI]        Tuple & modified tuple: JJ --> JJ
   [IC]        Interaction: min(l,m) = 2

Block #1, J(2,1), interacting with block #3, R(1,1,3)
   [+++]        Equation and variant: I:3
   [BII]        Tuple & modified tuple: JR --> JL
   [ICC]        Interaction: 0 = 0

Block #1, J(2,1), interacting with block #4, R(1,1,4)
   [++-]        Equation and variant: II:1
   [BII]        Tuple & modified tuple: JR --> JR
   [ICC]        Interaction: l = 2

Block #2, J(2,1), interacting with block #1, J(2,1)
   [++]        Equation and variant: I:1
   [BI]        Tuple & modified tuple: JJ --> JJ
   [IC]        Interaction: min(l,m) = 2

Block #2, J(2,1), interacting with block #2, J(2,1)
   [++]        Equation and variant: I:1
   [BI]        Tuple & modified tuple: JJ --> JJ
   [IC]        Interaction: min(l,m) = 2

Block #2, J(2,1), interacting with block #3, R(1,1,3)
   [+++]        Equation and variant: I:3
   [BII]        Tuple & modified tuple: JR --> JL
   [ICC]        Interaction: 0 = 0

Block #2, J(2,1), interacting with block #4, R(1,1,4)
   [++-]        Equation and variant: II:1
   [BII]        Tuple & modified tuple: JR --> JR
   [ICC]        Interaction: l = 2

Block #3, R(1,1,3), interacting with block #1, J(2,1)
   [+++]        Equation and variant: I:1
   [BIB]        Tuple & modified tuple: RJ --> RJ
   [ICI]        Interaction: 0 = 0

Block #3, R(1,1,3), interacting with block #2, J(2,1)
   [+++]        Equation and variant: I:1
   [BIB]        Tuple & modified tuple: RJ --> RJ
   [ICI]        Interaction: 0 = 0

Block #3, R(1,1,3), interacting with block #3, R(1,1,3)
   [++++]        Equation and variant: VIII:1
   [BIBI]        Tuple & modified tuple: RR --> RR
   [ICIC]        Interaction: 1+min(l,m) = 2

Block #3, R(1,1,3), interacting with block #4, R(1,1,4)
   [+++-]        Equation and variant: II:1
   [BIBI]        Tuple & modified tuple: RR --> RR
   [ICIC]        Interaction: l+1 = 2

Block #4, R(1,1,4), interacting with block #1, J(2,1)
   [++-]        Equation and variant: IV:1
   [BIB]        Tuple & modified tuple: RJ --> RJ
   [ICI]        Interaction: 0 = 0

Block #4, R(1,1,4), interacting with block #2, J(2,1)
   [++-]        Equation and variant: IV:1
   [BIB]        Tuple & modified tuple: RJ --> RJ
   [ICI]        Interaction: 0 = 0

Block #4, R(1,1,4), interacting with block #3, R(1,1,3)
   [+++-]        Equation and variant: IV:3
   [BIIB]        Tuple & modified tuple: RR --> RL
   [ICCI]        Interaction: 0 = 0

Block #4, R(1,1,4), interacting with block #4, R(1,1,4)
   [++--]        Equation and variant: VII:1
   [BIIB]        Tuple & modified tuple: RR --> RR
   [ICCI]        Interaction: max(0,l-m+1) = 1

Summary of all interactions.
Summary
=======
Kernel dimension:   9
Codimension:        6
Matlab function. (A Matlab function is produced that sets up the system matrix for the vectorized periodic Sylvester equation to compute the kernel dimension and codimension numerically. The numbers d and c returned by this Matlab function can be used to verify the kernel dimension and codimension obtained above symbolically with the Python code.)
MATLAB code
===========
function [c,d,Z] = compute_codimension()
% System matrix Z is 42 x 45
Z = zeros(42, 45);
A1 = blkdiag(J(1,1.000000),J(1,1.000000),F(0)',F(0)');
A2 = blkdiag(eye(1),eye(1),eye(1),eye(1));
A3 = blkdiag(eye(1),eye(1),G(0),eye(1));
A4 = blkdiag(eye(1),eye(1),eye(0),G(0)');
Z(1:8,5:20) = - kron(A1',eye(4));
Z(1:8,1:4) = kron(eye(2),A1);
Z(9:24,21:36) = kron(eye(4),A2);
Z(9:24,5:20) = - kron(A2',eye(4));
Z(25:36,37:45) = - kron(A3',eye(3));
Z(25:36,21:36) = kron(eye(4),A3);
Z(37:42,1:4) = kron(eye(2),A4);
Z(37:42,37:45) = - kron(A4',eye(3));
d = size(Z,2) - rank(Z);
c = d + (-3);

function A = J(m,x)
A = gallery('jordbloc', m, x);

function A = F(m)
A = eye(m+1);
A = A(1:m,:);

function A = G(m)
A = J(m+1,0);
A = A(1:m,:);
As to be expected, this Matlab functions yields d = 9 and c = 6, which provides a numerical verification of the symbolic computations by the Python script.

Download

Python script codimension.py

Example from Section 4.2 of [1]:

example1.dat (Input data)
example1.res (Output)
example1.m (Produced Matlab function)

Verification of Lemma 4.2 in [1]:

Shell scripts: testlr.sh, testll.sh, testrr.sh.
Obtained results: testlr.res, testll.res, testrr.res.

Author

Lars Karlsson, Department of Computing Science, Umeå University.

References

  1. B. Kågström, L. Karlsson, and D. Kressner. Computing codimensions and generic canonical forms for generalized matrix products. Electron. J. Linear Algebra, 22:277-309, 2011. (PDF, 346799 bytes)

Disclaimer

This software is delivered "as is". The author and maintainer make no representation or warranties, express or implied, with respect to the software package. In no event shall the author or maintainer be liable for loss of profits, loss of savings, or direct, indirect, special, consequential, or incidental damages. If you publish a research paper using this software, we will appreciate if you cite the paper [1] forming the basis of our implementation.