TypiCal

Matrices represented by computer programs, also called black-box matrices,
are a popular topic in Computer Algebra. Since the seminal paper
(Wiedemann 86), algorithms to do arithmetic operations on them, as
multiplication, determinant, minimal polynomial, etc., have been intensely
studied and are now well understood.

The status of transposition of black box matrices is much less clear. It
is a (not so well known) theorem in Algebraic Complexity that black-box
matrices given by (non-uniform) arithmetic circuits can be transposed
without changing the complexity of the circuit. In the more familiar
Turing model, this translates to a principle, often known as
"transposition principle" or "Tellegen's principle" in the Computer
Algebra community, that gives a "recipe" to "transpose" an algorithm
"without changing its complexity".

In this talk I will give a formal proof of the transposition principle in
the touring model and sketch the implementation of a compiler that
transposes algorithms written in our ad-hoc algebraic language
Transalpyne. (Maybe not so) Surprisingly, we discovered some connections
with Type Systems and Categoty Theory while attacking this problem: I will
try to explain these connections and point out some possible research
directions.