|
SATN-42 Abstract The operator denoted by the dot has been extended to provide a monadic function (as in -.×m ) as well as the established dyadic inner product function (as in n+.×m ). The case -.×m (on a square matrix m ) is the familiar determinant function, and the general case f.g m is defined analogously as reduction by f over a set of !n←1↑⍴m “products” produced by reduction by g over !n distinct sets of n elements chosen one from each row and column of the argument. The extension to non-square arguments allows the use of -.× on an n+1 by n argument to compute the signed volume of the simplex it represents in n-space. Introduction The determinant is an important function defined on square matrices — applied to a matrix of coefficients of a set of linear equations it determines the character of the solutions, applied to the matrix of partial derivatives of a vector function on vector arguments it yields the volume transformation effected by the function, and applied to the matrix s,1 it yields !1↓⍴s times the signed value of the simplex of n←1↑⍴s vertices in (n-1)-space. The determinant of a square matrix m is defined as the alternating sum (i.e. reduction by - ) of the !n←1↑⍴m products over n elements chosen (in each of the !n possible ways) one from each row and column. Analogous calculations in which other function pairs are substituted for - and × lead to other useful functions; examples include the pairs ⌈⌊ , ∧∨ , and +× , the last (called the permanent) being useful in combinatorics [1]. Because of the utility of cases other than
the pair -× ,
we introduce a dyadic operator instead
of a specific determinant function;
because the result of the dot operator is defined only
for the dyadic case of the resulting function
(as in a+.×b and a^.=b),
we adopt its monadic case for the “determinant” operator.
Thus -.×b is the determinant of b ,
and +.×b is the permanent.
Formal Definition of f.g b The function dop in workspace 1 satn42 models the determinant operator. For example, if m is a magic square of order 3, then:
m
6 7 2
1 5 9
8 3 4
-.×m '-×'dop m
360 360
+.×m '+×'dop m
900 900
∨.^m '∨^'dop m
2 2
dop and its supporting functions are displayed below; the subsequent comments may be helpful in grasping their details. Origin 1 is assumed throughout: dop⋄(1↑⍺)cr⍎(¯1↑⍺),'/x',0⍴x←all ⍵ all⋄((⍳k),k←⍴⍴y)⍉⍵[y←perm⍴⍵;] perm⋄(s,⍴s)⍴⍉mf 1+s⊤¯1+⍳×/s←(⌊/⍵)↑⌽⍳1↑⍵ mf⋄0≠1↑⍴⍵⋄⍵⋄⍵[,1;],[1]x+⍵[(1↑⍴x)⍴1;]≤x←mf 1 0↓⍵ cr⋄0≠⍴⍴x←⍵⋄⍵⋄⍺cr⍎⍺,'/x' The diagonal section 1 1⍉m contains one element from each row and column, and is therefore one of the sets of elements over which the reduction g/ is to be applied in evaluating f.g m . All such sets can be obtained from the expression 1 1⍉m[p;] , where p is one of the !n permutations of order n←1↑⍴m . Consequently, if ap is an array of all permutations of order n , then a suitable section of m[ap;] provides all the required sets of elements, and g/ over this section produces an array of all “products” to which reduction by f is to be applied. For example:
⎕←ap←perm ⍴m ⎕←r←all m
1 2 3 6 5 4
1 3 2 6 3 9
2 1 3 1 7 4
2 3 1 1 3 2
3 1 2 8 7 9
3 2 1 8 5 2
⍴ap
3 2 1 3
⎕←pr←×/r -/pr
120 120 162
162 28 6
504 80
28 -/-/pr
6 ¯42 22 424
-/-/-/pr
504 360
80
The permutations ap are in lexical order,
but the outer shape of the array is ⌽⍳n
rather than !n ,
and the shape of the array of products
is therefore ⌽⍳n as well.
Reduction by f is therefore carried out
over a succession of axes (beginning with the last)
as provided by the recursively-defined
function cr .
The reader may wish to verify that the pattern
of reduction provided by this argument of rank n
ensures that the function f applies over the products
in an order such that the permutations
which produced them alternate in parity.
This ordering is significant
for any non-associative function f ;
for the case -.× it ensures agreement
with the established definition of the determinant.
Non-Square Arguments Except for one important case, the extension of the determinant functions to non-square arguments may not greatly increase their utility. However, the extension is straightforward; if >/⍴m , then ×/s←(1↓⍴m)↑⌽⍳1↑⍴m distinct sets of 1↓⍴m elements can be selected without repetition of either column or row, and these are arranged in lexical order in an array of shape s . For example:
⎕←m←?4 2⍴9
6 4
5 5
4 3
1 4
⎕←ap←perm ⍴m ⎕←r←all m
1 2 6 5
1 3 6 3
1 4 6 4
2 1 5 4
2 3 5 3
2 4 5 4
3 1 4 4
3 2 4 5
3 4 4 4
4 1 1 4
4 2 1 5
4 3 1 3
⎕←pr←×/r
30 18 24
20 15 20
16 20 16
4 5 3
-/-/r
0 0 1 ¯1
-/-/pr
21
-.×m
21
For a wide matrix m , the result of f.g m is equivalent to f.g (⌊\⍴m)↑m . The case of -.× applied to an n+1
by n matrix is of special interest
because it is equivalent to -.×m,1 ,
and can therefore be used to compute the volume
of the simplex defined by m without explicit
catenation of a final column of ones.
Evaluation Methods Because of the special properties of the ordinary determinant, the function -.× on a square matrix is treated specially and is evaluated by the process used in matrix inversion; the time taken therefore varies as the cube of the order of the matrix. All other cases are treated by explicit evaluation of each of the ÷/!|-\⍴m sets of ¯1↑⍴m elements; the time therefore varies as the product of the foregoing quantities. Although the model shows the computation
of an aray a of “products”
of the form g/v followed by repeated
reductions f/…f/a ,
the processes are merged so that the reductions
are effected as early as possible.
Consequently the number of intermediate results
recorded in the reductions
does not exceed ⍴⍴a .
The scheme can be illustrated by evaluating -/-/a
for a matrix a ,
beginning at the right of the last row,
keeping the result of its reduction
while reducing the penultimate row,
and then applying reduction
(the one applied to the reduction of -/a )
to these two results before proceeding
with the reduction of another row.
Comments on Uses of f.g m Applications of the ordinary determinant ( -.× ) on square matrices will not be discussed except to remark that it may be used as a test for invertibility before applying the function ⌹ . If a , b , and c are two-element vectors, then -.×m←3 2⍴a,b,c yields twice the signed area of the triangle with vertices a , b , and c , signed because the sign of the result depends on the order of the vertices, positive if they are in counterclockwise order, and negative if in clockwise order. For example, if a←1 1 and b←1 0 and c←0 1 then:
-.×3 2⍴a,b,c
¯1
-.×3 2⍴b,a,c
1
Questions concerning the position of point a in relation to the line bc are more easily posed and answered in terms of the ordering of the points (i.e. in terms of the signed area) than in terms such as “above bc” (or should it be “left of bc” if bc is nearly vertical), or “a lies on the line bc” (for example, does it lie on the line if b and c are coincident?). The signed result of -.× is significant in higher dimensions as well; if a , b , c , and d are points in three-space (in a dextral coordinate system), then -.× 4 3⍴a,b,c,d gives (!3 times) the signed volume of the tetrahedron, the results being zero if the points are coplanar, and positive if the points b , c , and d are in counterclockwise order when viewed from a . For example:
a←1 1 1
b←1 0 0
c←0 1 0
d←0 0 1
-.×4 3⍴a,b,c,d
2
-.×4 3⍴a,c,b,d
¯2
We will illustrate the use of functions other than - and × in the context of the so-called assignment problem: one of n persons (or machines) is to be assigned to each one of n tasks in some optimal way, the cost associated with assigning person i to task j being given by element m[i;j] of the square matrix m . If we wish to minimize the sum of the costs in the assignment, then the optimal value is given by ⌊.+m , since the summation (+/) is applied to each of the !1↑⍴m possible assignments, and the minimum (⌊) is applied over them. Other useful function pairs in assignment type problems include ⌈+ , ⌊× , ⌈× , ⌊⌈ , and ⌈⌊ . A square boolean matrix b is said
to be a Latin square
if it contains exactly 1↑⍴b ones,
with one in each row and one in each column;
one boolean matrix c is said to cover
another, d ,
if ∧/,c≥d .
The expression ∨.∧c yields 1
if c covers a Latin square,
and the expression +.∧c tells
how many distinct Latin squares
are covered by c .
Acknowledgements The system programming for this extension to the
APL system was done by D.B. Allen.
I am grateful to Mr. Allen and to Mr. E.E. McDonnell
for comments on a draft of this paper.
References
Errata
First appeared as SHARP APL Technical Note 42,
Determinant-Like Functions Produced by the Dot Operator, 1982-04-01.
The text requires the APL385 Unicode font, which can be
downloaded from
http://www.vector.org.uk/resource/apl385.ttf .
To resolve (or at least explain) problems with displaying
APL characters see
http://www.vector.org.uk/archive/display.htm .
|