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, saves = (+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) = 1Summary of all interactions.
Summary ======= Kernel dimension: 9 Codimension: 6Matlab 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.pyExample from Section 4.2 of [1]:
example1.dat (Input data)
example1.res (Output)
example1.m (Produced Matlab function)
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
- 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)