Edit detail for LinearOperator revision 18 of 63

We implement bi-graded linear operators (transformations) over n-dimensional vector spaces on a commutative ring . Members of this domain are morphisms . Products, permutations and composition (grafting) of morphisms is implemented. Operators are represented internally as tensors.

Operator composition and products can be visualized by directed graphs (read from top to bottom) such as:

      n = 3     inputs

      \  |  /         \  /   /         \              |
       \ | /           \/   /           \            / \
        \|/             \  /           / \          /   \
        / \              \/           /   \         \   /
       /   \              \          /   / \         \ /
      /     \              \        /   /   \         |

      m = 2     outputs

Lines (edges) in the graph represent vectors, nodes represent operators. Horizontal juxtaposition represents product. Vertical juxtaposition represents composition.

We try to start the right way by defining the concept of a monoidal category.

Ref: http://en.wikipedia.org/wiki/PROP_(category_theory)

(1) -> <spad>

)abbrev category MONAL Monoidal
Monoidal(R:AbelianSemiGroup):Category == Monoid with
    dom: % -> R
      ++ domain
    cod: % -> R
      ++ co-domain
    _/: (%,%) -> %
      ++ vertical composition f/g = g*f
    apply:(%,%) -> %
      ++ horizontal composition
    coerce:(x:List PositiveInteger) -> %
      ++ identity for composition and permutations of its products
    coerce:(x:List None) -> %
      ++ [] = 1
  add
    (f:% / g:%):% == apply(g,f)</spad>

Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/5155383802378491972-25px001.spad
      using system compiler.
   MONAL abbreviates category Monoidal 
------------------------------------------------------------------------
   initializing NRLIB MONAL for Monoidal 
   compiling into NRLIB MONAL 
Time: 0 SEC.

   MONAL- abbreviates domain Monoidal& 
------------------------------------------------------------------------
   initializing NRLIB MONAL- for Monoidal& 
   compiling into NRLIB MONAL- 
   compiling exported / : (S,S) -> S
Time: 0 SEC.

(time taken in buildFunctor:  0)
Time: 0 SEC.

   Cumulative Statistics for Constructor Monoidal&
      Time: 0 seconds

   finalizing NRLIB MONAL- 
   Processing Monoidal& for Browser database:
--->-->Monoidal&(constructor): Not documented!!!!
--------(dom (R %))---------
--------(cod (R %))---------
--------(/ (% % %))---------
--->-->Monoidal&((/ (% % %))): Improper first word in comments: vertical
"vertical composition \\spad{f/g} = \\spad{g*f}"
--------(apply (% % %))---------
--------(coerce (% (List (PositiveInteger))))---------
--->-->Monoidal&((coerce (% (List (PositiveInteger))))): Improper first word in comments: identity
"identity for composition and permutations of its products"
--------(coerce (% (List (None))))---------
--->-->Monoidal&((coerce (% (List (None))))): Improper first word in comments: []
"[] = 1"
--->-->Monoidal&: Missing Description
; compiling file "/var/aw/var/LatexWiki/MONAL-.NRLIB/MONAL-.lsp" (written 22 OCT 2026 11:30:39 AM):

; wrote /var/aw/var/LatexWiki/MONAL-.NRLIB/MONAL-.fasl
; compilation finished in 0:00:00.000
------------------------------------------------------------------------
   Monoidal& is now explicitly exposed in frame initial 
   Monoidal& will be automatically loaded when needed from 
      /var/aw/var/LatexWiki/MONAL-.NRLIB/MONAL-
   finalizing NRLIB MONAL 
   Processing Monoidal for Browser database:
--->-->Monoidal(constructor): Not documented!!!!
--------(dom (R %))---------
--------(cod (R %))---------
--------(/ (% % %))---------
--->-->Monoidal((/ (% % %))): Improper first word in comments: vertical
"vertical composition \\spad{f/g} = \\spad{g*f}"
--------(apply (% % %))---------
--------(coerce (% (List (PositiveInteger))))---------
--->-->Monoidal((coerce (% (List (PositiveInteger))))): Improper first word in comments: identity
"identity for composition and permutations of its products"
--------(coerce (% (List (None))))---------
--->-->Monoidal((coerce (% (List (None))))): Improper first word in comments: []
"[] = 1"
--->-->Monoidal: Missing Description
; compiling file "/var/aw/var/LatexWiki/MONAL.NRLIB/MONAL.lsp" (written 22 OCT 2026 11:30:39 AM):

; wrote /var/aw/var/LatexWiki/MONAL.NRLIB/MONAL.fasl
; compilation finished in 0:00:00.000
------------------------------------------------------------------------
   Monoidal is now explicitly exposed in frame initial 
   Monoidal will be automatically loaded when needed from 
      /var/aw/var/LatexWiki/MONAL.NRLIB/MONAL

The initial object in this category is the domain Prop (Products and Permutations).

)abbrev domain PROP Prop
Prop(R:CommutativeRing): Join(Monoidal R, CoercibleTo OutputForm) with
    _/:(R,R) -> %
  == add
    Rep == Record(domain:R,codomain:R)
    rep(x:%):Rep == x pretend Rep
    per(x:Rep):% == x pretend %

    dom(f:%):R == rep(f).domain
    cod(f:%):R == rep(f).codomain

    coerce(f:%):OutputForm == dom(f)::OutputForm / cod(f)::OutputForm
    (f:R / g:R):% == per [f,g]
    apply(g:%, f:%):% ==
      cod(f) ~= dom(g) => error "arity"
      per [dom f,cod g]
    (f:% * g:%):% == per [dom(f)+dom(g),cod(f)+cod(g)]
    -- preserves arity
    (f:% + g:%):% ==
      dom(f)~=dom(g) or cod(g) ~= cod(g) => error "arity"
      f
    coerce(p:List PositiveInteger):% == per [#p::R,#p::R]
    coerce(p:List None):% == per [0,0]

   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/785743822053201310-25px002.spad
      using system compiler.
   PROP abbreviates domain Prop 
------------------------------------------------------------------------
   initializing NRLIB PROP for Prop 
   compiling into NRLIB PROP 
************* USER ERROR **********
available signatures for Rep: 
    NONE
NEED Rep: () -> ?
****** comp fails at level 1 with expression: ******
((DEF (|Rep|) (NIL) (|Record| (|:| |domain| R) (|:| |codomain| R))))
****** level 1  ******
x:= (DEF (Rep) (NIL) (Record (: domain R) (: codomain R)))
m:= $EmptyMode
f:=
((((~= #) (= #) (|coerce| #) (|latex| #) ...)))

   >> Apparent user error:
   unspecified error

The LinearOperator? domain is Moniodal over NonNegativeInteger?. It is the free algebra over Prop with n-generators.

)abbrev domain LIN LinearOperator
LinearOperator(n:NNI,K:CommutativeRing): Exports == Implementation where
  NNI ==> NonNegativeInteger
  T ==> CartesianTensor(1,n,K)

  Exports ==> Join(Ring, BiModule(K,K), Monoidal NNI, CoercibleTo Prop NNI) with
    inp: List K -> %
      ++ incoming vector
    inp: List % -> %
    out: List K -> %
      ++ output vector
    out: List % -> %
    coerce: K -> %
    --_*: (%,NNI) -> %
    arity: % -> Prop(NNI)
    apply: (%,%) -> %
    basisVectors: () -> List %
    basisForms: () -> List %
    pretty: % -> T

  Implementation ==> add
    import List NNI
    Rep == Record(domain:NNI, codomain:NNI, data:T)
    rep(x:%):Rep == x pretend Rep
    per(x:Rep):% == x pretend %

    dom(f:%):NNI == rep(f).domain
    cod(f:%):NNI == rep(f).codomain

    dat(f:%):T == rep(f).data

    arity(f:%):Prop NNI == dom(f)/cod(f)
    coerce(f:%):Prop NNI == arity f

    0 == per [0,0,0]

    basisVectors():List % == [per [0,1,entries(row(1,i)$SquareMatrix(n,K))::T] for i in 1..n]
    basisForms():List % == [per [1,0,entries(row(1,i)$SquareMatrix(n,K))::T] for i in 1..n]

    --
    -- f+g : A^{n+m} -> A^p = f:A^n -> A^p + g:A^m -> A^p
    --
    (f:% + g:%):% ==
      dat(f)=0 => g
      dat(g)=0 => f
      dom(f) ~= dom(g) or cod(f) ~= cod(g) => error "arity"
      per [dom(f),cod(f),dat(f)+dat(g)]

    (f:% - g:%):% ==
      dom(f) ~= dom(f) or cod(g) ~= cod(g) => error "arity"
      per [dom(f),cod(f),dat(f)-dat(g)]

    --
    -- f/g : A^n -> A^p = f:A^n -> A^m / g:A^m -> A^p
    -- g f : A^n -> A^p = g:A^m -> A^p * f:A^n -> A^m
    --
    apply(g:%,f:%):% ==
      dom(g) ~= cod(f) => error "arity"
      r:T := product(dat f, dat g)
      n:Integer:=dom(f)+1
      m:Integer:=dom(f)+cod(f)+1
      for i in 0..cod(f)-1 repeat
        r := contract(r,n,m-i)
        --(m1:=subtractIfCan(m,1)) case NNI =>m:=m1
      per [dom f,cod g,r]

    coerce(p:List PositiveInteger):% ==
      r:=per([1,1,kroneckerDelta()$T])^#p
      #p = 1 => return r
      p1:List Integer:=[i for i in 1..#p]
      p2:List Integer:=[#p+i for i in p]
      p3:=concat(p1,p2)
      per [#p,#p,reindex(dat r,p3)]
    coerce(p:List None):% == per [0,0,1]

    1:% == per [0,0,1]

    coerce(x:K):% == 1*x

    -- repeated composition
    (f:% ^ p:NNI):% ==
      cod(f) ~= dom(f) => error "arity"
      q:=subtractIfCan(p,1)
      q case NNI => f^q * f
      1

    -- repeated sum
    (p:NNI * f:%):% ==
      q:=subtractIfCan(p,1)
      q case NNI => q*f + f
      0

    (f:% * g:%):% ==
      r:T := product(dat f,dat g)
      -- dom(f) + cod(f) + dom(g) + cod(g)
      p:List Integer := concat                _
        [[i for i in 1..dom(f)],              _
        [dom(f)+cod(f)+i for i in 1..dom(g)], _
        [dom(f)+i for i in 1..cod(f)],        _
        [dom(f)+dom(g)+cod(f)+i for i in 1..cod(g)]]
      -- dom(f) + dom(g) + cod(f) + cod(g)
      per [dom(f)+dom(g),cod(f)+cod(g),reindex(r,p)]

    (x:% = y:%):Boolean ==
      dom(x) ~= dom(y) or cod(x) ~= cod(y) => error "arity"
      dat(x) = dat(y)

    (x:K * y:%):% == per [dom(y),cod(y),x*dat(y)]

    (x:% * y:K):% == per [dom(x),cod(x),dat(x)*y]

    (x:Integer * y:%):% == per [dom(y),cod(y),x*dat(y)]

    inp(x:List K):% == per [1,0,entries(x)::T]
    inp(x:List %):% ==
      #removeDuplicates([dom(y) for y in x]) ~= 1 or
        #removeDuplicates([cod(y) for y in x]) ~= 1 => error "arity"
      per [dom(first x)+1,cod(first x),[dat(y) for y in x]::T]$Rep

    out(x:List K):% == per [0,1,entries(x)::T]

    out(x:List %):% ==
      #removeDuplicates([dom(y) for y in x])~=1 or
        #removeDuplicates([cod(y) for y in x])~=1 => error "arity"
      per [dom(first x),cod(first x)+1,[dat(y) for y in x]::T]$Rep

    tensor(x:%):T == dat x

    coerce(x:%):OutputForm ==
      dom(x)=0 and cod(x)=0 => return dat(x)::OutputForm
      gens:List OutputForm:=[i::OutputForm for i in 1..n]
      -- input basis
      inps:List OutputForm := []
      for i in 1..dom(x) repeat
        empty? inps => inps:=gens
        inps:=concat [[hconcat(inps.k,gens.j) for j in 1..n] for k in 1..#inps]
      -- output basis
      outs:List OutputForm := []
      for i in 1..cod(x) repeat
        empty? outs => outs:=gens
        outs:=concat [[hconcat(outs.k,gens.j) for j in 1..n] for k in 1..#outs]
      -- term list
      --terms:List OutputForm:=[]
      bases:List OutputForm:=[]
      coeffs:=ravel dat(x)
      if #inps > 0 and #outs > 0 then
        expon:List List OutputForm:=concat([[[i,j] for j in outs] for i in inps])
        bases:=[scripts('e::OutputForm,ij) for ij in expon]
      else if #inps > 0 then
        bases:=[sub('e::OutputForm,i) for i in inps]
      else if #outs > 0 then
        bases:=[super('e::OutputForm,j) for j in outs]
      terms:=[(k=1 => base;k::OutputForm*base) for base in bases for k in coeffs | k~=0]
      empty? terms => return 0::OutputForm
      return reduce(_+,terms)

   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8227188337790643182-25px003.spad
      using system compiler.
   LIN abbreviates domain LinearOperator 
------------------------------------------------------------------------
   initializing NRLIB LIN for LinearOperator 
   compiling into NRLIB LIN 
   Semantic Errors: 
      [1] cannot form Join of: ((Ring) (BiModule K K) (Monoidal (NonNegativeInteger)) (CoercibleTo (Prop (NonNegativeInteger))) (CATEGORY domain (SIGNATURE inp (% (List K))) (SIGNATURE inp (% (List %))) (SIGNATURE out (% (List K))) (SIGNATURE out (% (List %))) (SIGNATURE coerce (% K)) (SIGNATURE arity ((Prop (NonNegativeInteger)) %)) (SIGNATURE apply (% % %)) (SIGNATURE basisVectors ((List %))) (SIGNATURE basisForms ((List %))) (SIGNATURE pretty ((CartesianTensor (1) n K) %))))

   Warnings: 
      [1]  Prop has no value

****** comp fails at level 3 with expression: ******
(|Join| (|Ring|) (|BiModule| K K) (|Monoidal| (|NonNegativeInteger|))
        (|CoercibleTo| | << | (|Prop| (|NonNegativeInteger|)) | >> |)
        (CATEGORY |domain| (SIGNATURE |inp| (% (|List| K)))
         (SIGNATURE |inp| (% (|List| %))) (SIGNATURE |out| (% (|List| K)))
         (SIGNATURE |out| (% (|List| %))) (SIGNATURE |coerce| (% K))
         (SIGNATURE |arity| ((|Prop| (|NonNegativeInteger|)) %))
         (SIGNATURE |apply| (% % %)) (SIGNATURE |basisVectors| ((|List| %)))
         (SIGNATURE |basisForms| ((|List| %)))
         (SIGNATURE |pretty| ((|CartesianTensor| 1 |n| K) %))))
****** level 3  ******
x:= (Prop (NonNegativeInteger))
m:= $EmptyMode
f:=
((((% #) (K # #) (|n| # #) (|LinearOperator| #) ...)))

   >> Apparent user error:
   cannot compile (Prop (NonNegativeInteger))

Construction operators: input and output

L:=LIN(2,FRAC POLY INT)

   LinearOperator is an unknown constructor and so is unavailable. Did 
      you mean to use -> but type something different instead?

Composition

AB2 := A2 / B2; AB2::OutputForm = A2::OutputForm / B2::OutputForm

(1)

arity(AB2)::OutputForm = arity(A2)::OutputForm / arity(B2)::OutputForm

   There are 1 exposed and 0 unexposed library operations named arity 
      having 1 argument(s) but none was determined to be applicable. 
      Use HyperDoc Browse, or issue
                              )display op arity
      to learn more about the available operations. Perhaps 
      package-calling the operation or using coercions on the arguments
      will allow you to apply the operation.

   Cannot find a definition or applicable library operation named arity
      with argument type(s) 
                        Fraction(Polynomial(Integer))

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.

Powers

AB3:=(AB1*AB1)*AB1;

arity(AB3)

   There are 1 exposed and 0 unexposed library operations named arity 
      having 1 argument(s) but none was determined to be applicable. 
      Use HyperDoc Browse, or issue
                              )display op arity
      to learn more about the available operations. Perhaps 
      package-calling the operation or using coercions on the arguments
      will allow you to apply the operation.

   Cannot find a definition or applicable library operation named arity
      with argument type(s) 
                             Polynomial(Integer)

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.

Sums

A12s := A1 + A2; A12s::OutputForm = A1::OutputForm + A2::OutputForm

(2)

arity(A12s)::OutputForm = arity(A1)::OutputForm + arity(A2)::OutputForm

   There are 1 exposed and 0 unexposed library operations named arity 
      having 1 argument(s) but none was determined to be applicable. 
      Use HyperDoc Browse, or issue
                              )display op arity
      to learn more about the available operations. Perhaps 
      package-calling the operation or using coercions on the arguments
      will allow you to apply the operation.

   Cannot find a definition or applicable library operation named arity
      with argument type(s) 
                             Polynomial(Integer)

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.

Multiplication

A3s:=(A1+A1)+A1

(3)

arity(A3s)

   There are 1 exposed and 0 unexposed library operations named arity 
      having 1 argument(s) but none was determined to be applicable. 
      Use HyperDoc Browse, or issue
                              )display op arity
      to learn more about the available operations. Perhaps 
      package-calling the operation or using coercions on the arguments
      will allow you to apply the operation.

   Cannot find a definition or applicable library operation named arity
      with argument type(s) 
                             Polynomial(Integer)

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.

B3s:=(B1+B1)+B1

(4)

arity(B3s)

   There are 1 exposed and 0 unexposed library operations named arity 
      having 1 argument(s) but none was determined to be applicable. 
      Use HyperDoc Browse, or issue
                              )display op arity
      to learn more about the available operations. Perhaps 
      package-calling the operation or using coercions on the arguments
      will allow you to apply the operation.

   Cannot find a definition or applicable library operation named arity
      with argument type(s) 
                             Polynomial(Integer)

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.

Expected error

B1A1:=B1*A1

(5)

arity(B1A1)

   There are 1 exposed and 0 unexposed library operations named arity 
      having 1 argument(s) but none was determined to be applicable. 
      Use HyperDoc Browse, or issue
                              )display op arity
      to learn more about the available operations. Perhaps 
      package-calling the operation or using coercions on the arguments
      will allow you to apply the operation.

   Cannot find a definition or applicable library operation named arity
      with argument type(s) 
                             Polynomial(Integer)

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.

Product

AB11:=A1*B1

(6)

arity(AB11)

   There are 1 exposed and 0 unexposed library operations named arity 
      having 1 argument(s) but none was determined to be applicable. 
      Use HyperDoc Browse, or issue
                              )display op arity
      to learn more about the available operations. Perhaps 
      package-calling the operation or using coercions on the arguments
      will allow you to apply the operation.

   Cannot find a definition or applicable library operation named arity
      with argument type(s) 
                             Polynomial(Integer)

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.

Multiple inputs and outputs

W:L:=out[inp[inp([script(w,[[i,j],[k]]) for j in 1..2])$L for i in 1..2] for k in 1..2]

   L is not a valid type.

Permutations and Identities

H:L:=[1,2]

   L is not a valid type.

Basis

Dx:=basisVectors()$L                    

   L is not a valid type.

Another kind of diagram:

  ___ _       _     
  ___ _)  =   _\_ _ 
  _/          ___ _)

Y:=out[inp[inp([script(y,[[i],[j,k]]) for k in 1..2])$L for j in 1..2] for i in 1..2]

   L is not a valid type.

Handle

          
 _/ _\__ 

λ:=inp[out[out([script(y,[[i],[j,k]]) for k in 1..2])$L for j in 1..2] for i in 1..2]

   L is not a valid type.

  Rep == Record(Dom:VectorSpace, Cod:VectorSpace, t:T)

But VectorSpace? is a category which would make Dom and Cod domains. The domains that currently satisfy VectorSpace? in Axiom are rather limited and seem oddly focused on number theory (finite fields). It is a good thing however that DirectProduct? is a conditional member of this cateogry.

DirectProduct(2,FRAC INT) has VectorSpace(FRAC INT)

   There are no library operations named VectorSpace 
      Use HyperDoc Browse or issue
                            )what op VectorSpace
      to learn if there is any operation containing " VectorSpace " in 
      its name.

   Cannot find a definition or applicable library operation named 
      VectorSpace with argument type(s) 
                                    Type

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.

Unfortunately:

DirectProduct(2,DirectProduct(2,FRAC INT)) has VectorSpace(FRAC INT)

   There are no library operations named VectorSpace 
      Use HyperDoc Browse or issue
                            )what op VectorSpace
      to learn if there is any operation containing " VectorSpace " in 
      its name.

   Cannot find a definition or applicable library operation named 
      VectorSpace with argument type(s) 
                                    Type

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.

The problem with VectorSpace? is that the domain [Vector]? is not a member of this category instead it satisfies VectoryCategory?.

Is it possible to treat tensors from CartesianTensor? as maps from VectorSpace? to VectorSpace?? We would like for example:

  T:DirectProduct(dim,DirectProduct(dim,FRAC INT)) -> DirectProduct(dim,FRAC INT))

To be a linear operator with two inputs and one output.

FreeModule(Fraction Integer,OrderedVariableList [e1,e1]) has VectorSpace(Fraction Integer)

   There are no library operations named VectorSpace 
      Use HyperDoc Browse or issue
                            )what op VectorSpace
      to learn if there is any operation containing " VectorSpace " in 
      its name.

   Cannot find a definition or applicable library operation named 
      VectorSpace with argument type(s) 
                                    Type

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.