Linear Relations

A package to work with linear relations

Irina Kurbatoba
la_soleil@bk.ru
Department of Applied Mathematics and Mechanics
Voronezh State University
August 2006

Abstract

This text describes the package LinearRelations that performs some usual operations with linear relations in (R^n).

Introduction

Linear relations is a language [1, 2, 3, 4] that allows one to talk about infinitely large linear operators. For example, such operators may arise as inverses to not-invertible operators. The main applications of linear relations are connected with differential equations of the form F\(x\& . \)=Gx+f with non-invertible F.
To install the package one should copy the file LinearRelations.m into the Mathematica's folder AddOns\StandardPackages. After that the following command will load the package.

<< LinearRelations`

Matrix representation of a relation

We call a matrix of a linear relation A any basis in the subspacee A in X×Y. We represent such a basis in the form like this

Here columns form a basis in the subspace A. The upper part of the column lies in X, the lower part of the column lies in Y. We keep the matrix of a relation in the form {a1,a2}, where a1 and a2 are upper and lower parts of the complete matrix A. For example, the above matrix A was created by the follown\ing commands.

nA = nB = 5; m = 4; 
    k = 7;
a1 = 
        Table[Random[Integer, {1, 2}], {i, m}, {j, 
            nA}];
a2 = 
        Table[Random[Integer, {0, 2}], {i, k}, {j, 
            nA}];
a = {a1, 
          a2};
Print["A=",MatrixFormRelation[a]];

Here MatrixFormRelation is a command from the package that represents the matrix of a relation in a regular way similar to that performed by the standard command MatrixForm.

The matrix representation is not unique. One of possible unified forms is the ColomnReduced form similar to that performed by the standard command RowReduce. For example,  this creates the ColomnReduced form of the above matrix.

Print["A=",MatrixFormRelation[ColomnReduceRelation[a]]]

The ColomnReduced form is the most close to the usual matrix representation of a linear operator. Namely, if the upper part of the matrix of a relation is the identity matrix, then the relation is a linear operator and the lower part of the matrix is the usual matrix of the operator. If the lower part of the matrix of a relation is the identity matrix, then the inverse relation (see the definition below) is a linear operator and the upper part of the matrix is the matrix of the inverse operator. 

The command MatrixToRelation represents a linear operator defined by a matrix A as a linear relation defined by the pair of matrices {I,A}, where I is the identity matrix.

Some general relations

The identity relation corresponds to the identity operator. The identity relation is calculated by the command IdentityRelation. 
 The zero relation is X×{0}. The zero relation is calculated by the command ZeroRelation. 
 The infinite relation is {0}×Y. The infinite relation is calculated by the command InfiniteRelation. 
 The empty relation is {0}×{0}. The empty relation is calculated by the command EmptyRelation. 
 The total relation is X×Y. The total relation is calculated by the command TotalRelation. 
 Here is an example of usage.

m = Random[Integer, {1, 9}]; 
    k = Random[Integer, {1, 9}];
Print["Identity Relation=",MatrixFormRelation[IdentityRelation[m]]];
Print["Zero Relation=",MatrixFormRelation[ZeroRelation[m, k]],";   Infinite Relation=",MatrixFormRelation[InfiniteRelation[m, k]]];
Print["Empty Relation=",MatrixFormRelation[EmptyRelation[m, k]],";   Total Relation=",MatrixFormRelation[TotalRelation[m, k]]];

Basic definitions

Let X and Y be linear spases. A linear relation is a linear subspace Γ in X×Y. A linear relation induces a mutivalued operator A:X->Y. Namely, they say that yϵAx or y=Ax iff (x,y)∈Γ. Usualy, they do not distiguish between Γ and A and write (x,y)∈A instead of (x,y)∈Γ.  Any linear operator can be considered as a linear relation if one identifies the operator with its graph.

The image of the relation A is the set of all y∈Y such that (x,y)∈ A for some x∈X.
The domain of the relation A is the set of all x∈X such that (x,y)∈ A for some y∈Y.
The kernel of the relation A is the set of xϵX such that (x,0)∈A. The  kernel is calculated by the command NullSpaceRelation from the package.
The image of zero of the relation A is the set of yϵY such that (0,y)∈A. The image of zero is calculated by the command ImageOfZeroRelation from the package.
The section of the relation A is a linear operator that defined on the domain of A and maps x into one of yϵAx. Clearly, the section is not uniquely defined. The section is calculated by the command Section from the package.
 Here is an example of usage.

nA = Random[Integer, {1, 9}]; m = Random[Integer, {1, 9}]; 
    k = Random[Integer, {1, 9}];
a1 = 
        Table[Random[Integer, {-9, 9}], {i, m}, {j, 
            nA}];
a2 = 
        Table[Random[Integer, {-9, 9}], {i, k}, {j, 
            nA}];
a = {a1, 
          a2};
Print["A:" (R^m) -> 
        (R^k), ";  nA=", 
      nA]
Print["A=", 
        MatrixFormRelation[a], " = ", 
        MatrixFormRelation[
          ColomnReduceRelation[a]]];
nullspace=NullSpaceRelation[a];
sect=Section[a];
imz=ImageOfZeroRelation[a];
Print["Section of A=", 
        MatrixFormRelation[sect], ";   Image of Zero of A=", 
        MatrixFormRelation[
          imz]];
Print["NullSpace of A=", 
        MatrixFormRelation[nullspace]];

The inverse relation

The inverse of the relation A in X×Y is the relation (A^(-1)) in Y×X consisting of all paires (y,x) such that (x,y)∈A. The  inverse relation is calculated by the command InverseRelation.
 Here is an example of usage.

nA = Random[Integer, {1, 9}]; m = Random[Integer, {1, 9}]; 
    k = Random[Integer, {1, 9}];
a1 = 
        Table[Random[Integer, {-9, 9}], {i, m}, {j, 
            nA}];
a2 = 
        Table[Random[Integer, {-9, 9}], {i, k}, {j, 
            nA}];
a = {a1, 
          a2};
Print["A:" (R^m) -> 
        (R^k), ";  nA=", nA]
inv=InverseRelation[a];
Print["A=", MatrixFormRelation[a], " = ", 
        MatrixFormRelation[
          ColomnReduceRelation[
            a]]];
\(Print[\*""(A^(-1))="", MatrixFormRelation[inv], " = ", 
        MatrixFormRelation[ColomnReduceRelation[inv]]];\)

The conjugate relation

The conjugate of a relation A is the relation (A^(* ))that consists of pairs (\(\(y\^*\), \(x\^*\)\))∈\(\(Y\^*\)×\(X\^*\)\)such that <x, \(\(x\^*\)\)> = <y,\(\(\(\ \)\(y\^*\)\)\)> for all pairs (x,y)∈A. The conjugate relation is calculated by the command ConjugateRelation.
 Here is an example of usage.

nA = Random[Integer, {1, 9}]; m = Random[Integer, {1, 9}]; 
    k = Random[Integer, {1, 9}];
a1 = 
        Table[Random[Integer, {-9, 9}], {i, m}, {j, 
            nA}];
a2 = 
        Table[Random[Integer, {-9, 9}], {i, k}, {j, 
            nA}];
a = {a1, 
          a2};
Print["A:" (R^m) -> 
        (R^k), ";  nA=", nA]
conj=ConjugateRelation[a];
Print["A=", MatrixFormRelation[a], " = ", 
        MatrixFormRelation[
          ColomnReduceRelation[
            a]]];
Print["Conjugate of A=", 
        MatrixFormRelation[conj], " = ", 
        MatrixFormRelation[ColomnReduceRelation[conj]]];

The sum and harmonic sum of relations

The sum of the realations (Subscript[A, 1]) and  (Subscript[A, 2]) consists of all paires (x, (Subscript[y, 1])+(Subscript[y, 2])), where (x,(Subscript[y, 1]))∈(Subscript[A, 1]) and (x,(Subscript[y, 2]))∈(Subscript[A, 2]). The sum is calculated by the command Addition.

The harmonic sum of the realations  (Subscript[A, 1]) and (Subscript[A, 2]) consists of all paires ((Subscript[x, 1])+(Subscript[x, 2]), y), where ((Subscript[x, 1]),y)∈(Subscript[A, 1]) and ((Subscript[x, 2]),y)∈ (Subscript[A, 2]). The harmonic sum is calculated by the command HarmonicAddition.
Here are examples.

lengthOfColumn = Random[Integer, {1, 9}]; 
    m = Random[Integer, {1, 9}]; 
    k = Random[Integer, {1, 9}];
nA = 
        lengthOfColumn;
nB = 
        lengthOfColumn;
a1 = 
        Table[Random[Integer, {-9, 9}], {i, m}, {j, 
            nA}];
a2 = 
        Table[Random[Integer, {-9, 9}], {i, k}, {j, 
            nA}];
b1 = 
        Table[Random[Integer, {-9, 9}], {i, m}, {j, 
            nB}];
b2 = 
        Table[Random[Integer, {-9, 9}], {i, k}, {j, 
            nB}];
a = {a1, a2}; 
    b = {b1, b2};
Print["A,B:", 
      (R^m) -> (R^k), ";  nA=", nA, ";  nB=", nB]; 
    Print["B=", MatrixFormRelation[b], ";  A=", 
      MatrixFormRelation[a]];
fin=Addition[a, b];
Print["A+B=", 
      MatrixFormRelation[fin], " = ", 
      MatrixFormRelation[ColomnReduceRelation[fin] // N]]

lengthOfColumn = Random[Integer, {1, 9}]; 
    m = Random[Integer, {1, 9}]; 
    k = Random[Integer, {1, 9}];
nA = 
        lengthOfColumn;
nB = 
        lengthOfColumn;
a1 = 
        Table[Random[Integer, {-9, 9}], {i, m}, {j, 
            nA}];
a2 = 
        Table[Random[Integer, {-9, 9}], {i, k}, {j, 
            nA}];
b1 = 
        Table[Random[Integer, {-9, 9}], {i, m}, {j, 
            nB}];
b2 = 
        Table[Random[Integer, {-9, 9}], {i, k}, {j, 
            nB}];
a = {a1, a2}; 
    b = {b1, b2};
Print["A,B:", 
      (R^m) -> (R^k), ";  nA=", nA, ";  nB=", 
      nB]
Print["B=", 
        MatrixFormRelation[b], ";  A=", 
        MatrixFormRelation[a]];
fin=HarmonicAddition[a, b];
Print["AωB=", 
      MatrixFormRelation[fin], " = ", 
      MatrixFormRelation[ColomnReduceRelation[fin] // N]]

lengthOfColumn = Random[Integer, {1, 9}]; 
    m = Random[Integer, {1, 9}]; 
    k = Random[Integer, {1, 9}];
nA = 
        lengthOfColumn;
nB = 
        lengthOfColumn;
a1 = 
        Table[Random[Integer, {-9, 9}], {i, m}, {j, 
            nA}];
a2 = 
        Table[Random[Integer, {-9, 9}], {i, k}, {j, 
            nA}];
b1 = 
        Table[Random[Integer, {-9, 9}], {i, m}, {j, 
            nB}];
b2 = 
        Table[Random[Integer, {-9, 9}], {i, k}, {j, 
            nB}];
Do[b1[[i, 1]] = a1[[i, 1]] + a1[[i, 2]], {i, m}]
a = {a1, a2}; 
    b = {b1, b2};
Print["A,B:" (R^m) -> 
        (R^k), ";  nA=", nA, ";  nB=", 
      nB]
Print["B=", 
        MatrixFormRelation[b], " = ", 
        MatrixFormRelation[ColomnReduceRelation[b]], ";  A=", 
        MatrixFormRelation[a], " = ", 
        MatrixFormRelation[
          ColomnReduceRelation[a]]];
fin=Addition[a, b];
Print["A+B=", 
      MatrixFormRelation[fin], " = ", 
      MatrixFormRelation[ColomnReduceRelation[fin] // N]]

The product of relations

The product of relations A and B consisnts of all pairs (x,z) such that (x,y)∈B and (y,z)∈A for some y.The product is calculated by the command Multiplication.
Here is an example.

nA = Random[Integer, {1, 9}]; nB = Random[Integer, {1, 9}]; 
    l = Random[Integer, {1, 9}]; m = Random[Integer, {1, 9}]; 
    k = Random[Integer, {1, 9}];
a1 = 
        Table[Random[Integer, {-9, 9}], {i, m}, {j, 
            nA}];
a2 = 
        Table[Random[Integer, {-9, 9}], {i, k}, {j, 
            nA}];
b2 = 
        Table[Random[Integer, {-9, 9}], {i, m}, {j, 
            nB}];
b1 = 
        Table[Random[Integer, {-9, 9}], {i, l}, {j, 
            nB}];
a = {a1, a2}; 
    b = {b1, b2};
Print["B:" (R^l) -> 
        (R^m), ";  A:" (R^m) -> (R^k), ";  nA=", nA, ";  nB=", 
      nB]
Print["B=", 
        MatrixFormRelation[b], ";  A=", 
        MatrixFormRelation[a]];
fin=Multiplication[a, b];
Print["AB=", 
        MatrixFormRelation[fin], " = ", 
        MatrixFormRelation[ColomnReduceRelation[fin]]];

References

[1]   Arendt W. Approximation of degenerate semigroups. Tubinger Berichte fur Funktionalanalysis. Helf Basel: Birkhauser--Verlag, 2001.
  [2]   Baskakov A. G. and Chernyshov K. I. Spectral theory of linear relations and degenerate semigroups of operators. Mathemat. Sbornik, 2002. Vol. 371, No~11. pp. 3--42 (in Russian).
  [3]   Cross R. Multivalued linear operators. New York: M. Dekker, 1998.
  [4]   Favini A., Yagi A. Degenerate evolution equations in Banach spaces. New York: M. Dekker, 1998.