Linear Algebra project

The aim of this project is to construct all mathematical objects found in Linear Algebra without lossing generality. We use AlgebraicAmbients to keep definitions independent from the field of scalars and LinearAmbients to be able to define "abstract" linear spaces and perform operations on them as tensor product, hom, dual, direct sum, etc. and any combination of them. Also we don't want to restrict ourselves to the case where all indexes occurring in bases, coordinates and matrixes are 1, 2, ..., n. Some times these objects are canonically indexed by an arbitrary set I. That's why we have IndexedTuples and IndexedMatrixes.

Download the last change set
Linear.zip [Dec-31-1998]

We are currently considering the following problem:

If V is a linear space with scalars in a field K acting on the left (suppose that K is not commutative), then the dual V* is a right K-linear space (but not a left K-linear space). So, in order to face this "side change", each LinearSpace should have the knowledge of whether the scalar action is from the left or the right.

Algebraic Ambients

Suppose you want to implement Linear Algebra in Squeak (that's what we are doing). The first object you need is the tuple. OK. When you consider the class Tuple you want instance creation messages for the canonical vectors e_i. But when mathematicians say e_i they are assuming we all know the value of n. In other words, they are speaking about e_i,n. But, what is even more problematic, they are assuming we all know the field of scalars. So, our instance creation method should look like this

Arguments i and n are clear. But, what about scalars? We cannot use the SmallInteger objects 1 and 0 for the unit and the zero elements inside e_i, because this is not general enough. We want our Linear Albebra construction to be valid for any field K.

One could say: well, let's model the class Field. Yes, but that is not easy and goes beyond our current problem. Up to now, all we need for tuples is to speak about 1 and 0 with generality.

The solution we decided was to create the class AlgebraicAmbient. An AlgebraicAmbient is an object that can respond a unit and a zero. It represents a prime field or ring (the intersection of many rings). Since zero equals unit - unit, these object only must remember the unit as an instance variable.

Also, the class AlgebraicAmbient knows the collection of all available ambients. So, when you say

the answer is a previously created ambient with that unit, or a new created instance.

The initialization of the class creates the "default" instance withUnit: 1 (the SmallInteger). But once you create, say, IntegerMod5, you can add a new ambient

Overview

Tuple
   SimpleTuple
   IndexedTuple

Tuple
Abstract class. You could hang your particular subclass here.

SimpleTuple
The instances are normal tuples of some dimension $n$ as (-1, 2, 0), etc.

IndexedTuple
The instances are families with free indexes $(a_i)_{i \in I}$

Matrix    
   SimpleMatrix    
   IndexedMatrix

Matrix
Abstrac class. You could hang your particular subclass here.

SimpleMatrix
The instances are normal matrices of some dimension $n \times m$, as $\pmatrix{1 & -1 \cr 0 & 1\cr}$.

IndexedMatrix
Matrices with index in a Cartesian product: $(a_{ij})_{(i,j) \in I\times J}$

AlgebraicAmbient
ModularInteger

AlgebraicAmbient
Each instance is a prime field or ring. Examples: rationals, Zp, algebraic numbers, Q[i], etc. This class allows us to implement all other classes without loss of generality in the choice of the field (or ring) of scalars. Instance variables named 'scalars' as in LinearBasis, LinearAmbient, IndexedTuple or SimpleMatrix refer to AlgebraicAmbients.

ModularInteger
Abstract class. Each concrete subclass is created on demand. For example evaluating (2 mod: 5) for the first time creates the subclass IntegerMod5. You can create Zp as an AlgebraicAmbient sending the following message:

   AlgebraicAmbient withUnit: (1 mod: 5)

CartesianProduct
OrderedPair

OrderedPair
A generalization of Point. Each pair may contain any object in the x and y coordinates.

CartesianProduct
A special kind of set (or collection) whose elements are OrderedPairs.

LinearBasis
LinearAmbient
   TupleAmbient    
     MatrixAmbient  
   ProductAmbient
   DualAmbient

LinearBasis
The instances are linear base of some linear space with free indexes.

LinearAmbient
Root of a hierarchy of ambients modeling different vector spaces where all subspaces finally live. You should hang here new kinds of linear ambients. The main responsibility of a LinearAmbient is to keep a cannon basis and to respond the coordinates of any vector in that basis. LinearAmbients will free us the tedious task of worry about coordinates.

TupleAmbient
An important an very simple example of linear ambient. You can create an instance providing the dimension of the ambient and specifying scalars or indexes as desired.

MatrixAmbient
Another important and very simple example modeling spaces where the elements are matrices.

ProductAmbient
If you have two ambients, you can form the product (direct sum) using this class.

TensorAmbient [coming soon]
If you have two linear spaces, you can form the tensor product.

DualAmbient
If you have a linear space V, you can consider the dual V* as an ambient by itself.

HomAmbient [coming soon]
If you have two linear spaces V and W, the Hom(V,W) is an ambient

MatrixReducer
EuclideanReducer

MatrixReducer
The instances are algorithms reducing (triangulating) matrices with coefficients in a field. You create a MatrixReducer sending it the message

   MatrixReducer input: aMatrix

EuclideanReducer [coming soon]
This reducer is used when you have not a field but and Euclidean ring of scalars (Z, k[x], etc).

Linear Ambients

Consider an example. You have Q³ (being Q the rationals). In this space you have a subspace L, say the plane defined by

You find a basis for L, say B={(1, -1, 0), (1, 0, -1)}. Now you want to find the coordinates of a vector v=(a, b, c) in L in terms of the basis B. You can use the following algorithm:

1. Put the elements of B as columns of a Matrix new
2. Put the element v as the third column
3. Reduce the matrix using elementary operations on the rows
4. Read the coordinates in the third column

1	1	a
-1	0	b
0	-1	c

1	1	a
0	1	a+b
0	-1	c

1	0	-b
0	1	a+b
0	0	a+b+c

and since a+b+c=0, we obtain

     [v]B = (-b, a+b)      "coordinates of v in basis B"

You can use another algorithm. But no matter what algorithm you employ, the point is that all algorithms need to know a crucial information: how to write the coordinates of all involved vectors as tuples. In other words, each time we want to calculate the coordinates of a vector v in some basis B, we must first be able to express the coordinates of the elements of B and v in terms of another basis.

A similar situation arises when you want to express a number in some basis. For example, you need to express the number 14 in decimal in order to convert it to binary 2r1110.

The problem seems to be circular: to be able to find the coordinates we must first find the coordinates. Fortunately, it isn't.

In our example above, we wanted the coordinates of v in the basis {v₁, v₂}. But what we needed were the coordinates of v₁, v₂ and v in the canonical basis of Q³ (not in the basis B of L). And there is an important difference between Q³ and L: Q³ has a canonical basis (while L hasn't).

Note that the notion of 'canonical' is not mathematically definied. Still a canonical basis has an intuitive property: it makes it easy to find the coordinates of any vector.

Examples of canonical basis are:

1. Tuples: e₁=(1, 0, 0, ...), e₂=(0, 1, 0, ...), e₃=(0, 0, 1, ...), ...
2. Matrices: e₁₁, e₁₂, e₁₃, ..., e_ij. Where e_ij is the matrix having 1 at i@j and zero anywhere
3. Polynomials: 1, x, x², x³, ...
4. Polynomials: 1, x, y, z, x², xy, xz, y², yz, z², ....

When we have a canonical basis we know how to compute the coordinates of a vector. So we should capture this concept and keep it in mind because this is the clue to work with abstract linear bases.

By thinking in canonic bases we realize that they appear tied to linear ambients. By linear ambient I mean a linear space that's the mother of all subspaces in a given problem. Examples of linear ambients are

A linear ambient (feel free to suggest another name) is not a subspace, it is the space. What I'm trying to say is that we have linear spaces and subspaces, the spaces are the ambients where all vectors live.

My claim is that each linear ambient has a canonic basis. Understanding that "canonic" means that we have no problem to compute the coordinates of a given vector, no matter what the vector is.

In fact, I'm saying more. I'm saying that a linear ambient is a place where we have a canonic baisis. To put it clearer, we could define the class

where we have two instance methods:

and

These methods are inverses each other. Of course, the class LinearAmbient is abstract and the implementantion of those methods is a subclass responsibility. Filling up the code for these two methods exactly corresponds to the fact that this task is supposed to be easy when we have a canonic basis.

Thus, LinearAmbient is a framework helping us to define concrete ambients. Some examples follow.

TupleAmbient (a number n is given)
Canonic basis: e₁, e₂, ..., e_n

TupleAmbient | coordinatesOf: vector
   ^vector

TupleAmbient | verctorWithCoordiantes: aTuple
   ^aTuple

MatrixAmbient (n and m are given)
Canonic basis: e_ij, (i runing from 1 to: n; j runing from 1 to: m)

MatrixAmbient | coordiantesOf: matrix
   ^Tuple
     dim: n * m
     fromBlock: [:k | matrix at: (k - 1 // m) + 1 @ (k - 1 \\ m) + 1]

MatrixAmbient | verctorWithCoordiantes: aTuple
   ^Matrix
     dim: n * m
     fromBlock: [:ij | aTuple at: (ij x - 1) * m + ij y]

DualAmbient (a subspace V of dim n with a basis is given)
Canonic basis: the dual basis of the given basis of V

DualAmbient | coordinatesOf: form
   ^Tuple
     dim: n
     fromBlock: [:k | form at: (basis at: k)]

DualAmbient | verctorWithCoordiantes: aTuple
   sum := (self canonic: 1) * (aTuple at: 1).
   2 to: n do: [:k | sum := (self canonic: k) * (aTuple at: k) + sum].
   ^sum

Following these ideas it is easy to implement TensorAmbient, HomAmbient, ProductAmbient, PolynomialAmbient, etc. Note that with a few classes we could capture all relevant ambients to work with and combine them in any way (using tensor product, hom, direct sum, dual, etc.). Then once we have the ambients we could easily consider "abstract" subspaces living inside them. Doing that we ensure ourselves that all abstract concepts can be modeled and all algorithms will work.