Teaching with an Executable Notation (Part 2)
Vector 12:1, page 67
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 67
A. Introduction¶
A linear function is a monad that distributes over addition. Every scalar linear function is equivalent to multiplication by a constant, but vector and higher rank linear functions prove fruitful and interesting. We begin with examples of rank 1 linear functions; before reading them, the reader might furnish examples of his own:
a=. 2 3 5 7 [ b=. 0 1 2 3
f=. |.
(f(a+b));(f a);(f b);((f a)+(f b))
┌────────┬───────┬───────┬────────┐
│10 7 4 2│7 5 3 2│3 2 1 0│10 7 4 2│
└────────┴───────┴───────┴────────┘
f=. +/
(f(a+b));(f a);(f b);((f a)+(f b))
┌──┬──┬─┬──┐
│23│17│6│23│
└──┴──┴─┴──┘
f=. +/\ NB. Prefix scan
(f(a+b));(f a);(f b);((f a)+(f b))
┌──────────┬──────────┬───────┬──────────┐
│2 6 13 23 │2 5 10 17 │0 1 3 6│2 6 13 23 │
└──────────┴──────────┴───────┴──────────┘
f=. 1 2 3 4&*
(f(a+b));(f a);(f b);((f a)+(f b))
┌─────────┬─────────┬────────┬─────────┐
│2 8 21 40│2 6 15 28│0 2 6 12│2 8 21 40│
└─────────┴─────────┴────────┴─────────┘
f=. +/@(1 2 3 4&*)
(f(a+b));(f a);(f b);((f a)+(f b))
┌──┬──┬──┬──┐
│71│51│20│71│
└──┴──┴──┴──┘
f=. +/\@(1 2 3 4&*)
(f(a+b));(f a);(f b);((f a)+(f b))
┌──────────┬─────────┬────────┬──────────┐
│2 10 31 71│2 8 23 51│0 2 8 20│2 10 31 71│
└──────────┴─────────┴────────┴──────────┘
A.1 Comment on the foregoing sentences after experimenting with arguments (such as a=. 2 3 5 7 11 and b=. 0 1 2 3 4) of a different dimension (number of elements) from the arguments used above,
A.2 Define the matrix m=. i. 3 4 and determine the dimensions of the argument a and result r of the following expression:
A.3 Experiment with the function mp=. +/ . * (matrix product) in expressions such as:
Comment on the results.
As remarked in the answer to exercise A.1, some linear vector functions are limited to arguments of a fixed dimension, and we will concentrate on such functions. More particularly, we will emphasize uniform functions that produce results of the same dimension as the argument, and are "closed" in the sense that the result of one is a suitable argument to another.
As illustrated in Exercises A.2 and A.3, the matrix product mp=. +/ . * may be used with a matrix m in the expression mp&m to yield a linear function. Conversely, any linear function of fixed dimension can be represented in this form. The matrix required to represent a specific linear function f is obtained by applying it to an identity matrix as illustrated below:
f=. |. @ (+/\) @ |. "1
b=. 1 2 3 4 5
]I=. = i. #b
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
f b
15 14 12 9 5
] m=. f I
1 0 0 0 0
1 1 0 0 0
1 1 1 0 0
1 1 1 1 0
1 1 1 1 1
mp&m b
15 14 12 9 5
A.4 What restriction on m ensures that the function mp&m is uniform?
A.5 Prove that the function mp&m is linear, that is, that it distributes over addition.
A.6 Why is a matrix such as I=. =i.n called an identity matrix?
A.7 Prove that m=. f I yields a matrix such that mp&m is equivalent to a linear function f.
A.8 If the functions mp&m and n&mp are equivalent, what is the relation between the matrices m and n? Does the relation hold for non-uniform functions?
B. Representations and Compositions¶
Since 2 #. 1 1 0 0 is twelve, the list 1 1 0 0 is said to be its base-2 representation. More generally, a list of integers i is said to be the base-b representation of the number b #. i .
Similarly, the coefficients c are said to be the polynomial representation of the function c&p., and m is said to be the (matrix) representation of the linear function mp&m. More specifically, we may call m the post-representation to distinguish it from the pre-representation in the form n&mp .
B.1 Use various integers b and integer lists c to experiment with the functions b&#. , and c&p.
B.2 Test the assertion that the functions +/\ and +/\. are linear, and write and enter expressions to yield their dimension-4 representations.
In maths, notation such as f ∘ g is used to denote the composition of functions f and g, with the definition that f ∘ g x is f g x, We will use the term more generally to refer to the use of several conjunctions (including @ and & and &.) and of forks. For example, if f and g are linear functions, then f + g is also a linear function, and its representation is the sum of the representations of f and g.
B.3 Enter m=. ? 4 4 $9 [ n=. ? 4 4 $9 and f=. mp&m and g=. mp&n to generate two random matrices of dimension 4, and experiment with the uniform linear functions f and g represented by them.
B.4 Assuming f and g linear, state which of the following compositions are linear, and write expressions for their representations in terms of the representations of f and g :
B.5 Experiment with the verbs and pronouns of Ex B.3 to test your conclusions in Ex B.4.
B.6 Is the alternating sum -/ linear?
C. Inverses¶
The functions +: and -: are said to be (mutually) inverse because +:@-: and -:@+: are identity functions. For example:
a=. i. 4
(+:a);(-:a);(+:-:a);(-:+:a)
┌───────┬───────────┬───────┬───────┐
│0 2 4 6│0 0.5 1 1.5│0 1 2 3│0 1 2 3│
└───────┴───────────┴───────┴───────┘
(*:a);(%:a);(*:%:a);(%:*:a)
┌───────┬───────────────────┬───────┬───────┐
│0 1 4 9│0 1 1.41421 1.73205│0 1 2 3│0 1 2 3│
└───────┴───────────────────┴───────┴───────┘
(^a);(^.a )
┌───────────────────────────┬──────────────────────┐
│1 2.71828 7.38906 20.0855 │__ 0 0.693147 1.09861 │
└───────────────────────────┴──────────────────────┘
(^^.a);(^.^a)
┌────────┬───────┐
│_. 1 2 3│0 1 2 3│
└────────┴───────┘
C.1 Experiment with the foregoing sentences using a=. -i.4 and comment on the results.
C.2 Experiment with the expressions f^:_1 and f^:_1 a for each of the functions used in the foregoing sentences, and state the effect of the power conjunction with the right argument _1 (or, equivalently, the effect of the adverb inv=. ^:_1).
A function that yields the same result for two different arguments cannot be invertible, For example:
0: 3 0: 4
0 0
]m=. 1 2 3,0,:4 5 6
1 2 3
0 0 0
4 5 6
mp=. +/ . *
mp&m 2 3 5
22 29 36
mp&m 2 7 5
22 29 36
Subsequent remarks are intended to apply only to invertible functions. The inverse of a linear function is also linear. For example:
f=. +/\"1
g=. f^:_1"1
a=. 4 3 2 1
b=. 2 3 5 7
(f a);(g a);(f g a);(g a+b);((g a)+(g b))
┌────────┬───────────┬───────┬───────┬───────┐
│4 7 9 10│4 _1 _1 _1 │4 3 2 1│6 0 1 1│6 0 1 1│
└────────┴───────────┴───────┴───────┴───────┘
I=. =i. 5
I;(f I);(g I);(%.f I)
┌─────────┬─────────┬──────────────┬──────────────┐
│1 0 0 0 0│1 1 1 1 1│1 _1 0 0 0 │1 _1 0 0 0 │
│0 1 0 0 0│0 1 1 1 1│0 1 _1 0 0 │0 1 _1 0 0 │
│0 0 1 0 0│0 0 1 1 1│0 0 1 _1 0 │0 0 1 _1 0 │
│0 0 0 1 0│0 0 0 1 1│0 0 0 1 _1 │0 0 0 1 _1 │
│0 0 0 0 1│0 0 0 0 1│0 0 0 0 1 │0 0 0 0 1 │
└─────────┴─────────┴──────────────┴──────────────┘
The representations of f and g given in the final result show the relation between "integration" (f) and "differencing" (g), and the result of the function %. suggests why it is called matrix inverse.
C.3 Prove that the inverse of a linear function is a linear function.
D. Scans¶
In Section A it was seen that the prefix scan adverb \ applied to the linear function +/ yielded a linear function. This suggests a further examination of it and other scan adverbs listed in the Vocabulary of the dictionary of J, including the suffix scan (\.), the infix and outfix (dyadic cases of \ and \.), and the oblique (/.) which is of interest for linear functions of rank 2.
Make your own examples to test the linearity of the various scans, and then consider the following:
a=. 2 3 5 7 11 [ b=. 0 1 2 3 4
+/\a
<\a NB. Structure of prefix scan
┌─┬───┬─────┬───────┬──────────┐
│2│2 3│2 3 5│2 3 5 7│2 3 5 7 11│
└─┴───┴─────┴───────┴──────────┘
<\.a NB. Structure of suffix scan
┌──────────┬────────┬──────┬────┬──┐
│2 3 5 7 11│3 5 7 11│5 7 11│7 11│11│
└──────────┴────────┴──────┴────┴──┘
(+/\.a);(+/\.b)
┌──────────────┬───────────┐
│28 26 23 18 11│10 10 9 7 4│
└──────────────┴───────────┘
((+/\.a)+(+/\.b));(+/\.a+b)
┌──────────────┬──────────────┐
│38 36 32 25 15│38 36 32 25 15│
└──────────────┴──────────────┘
2 <\a NB. Structure of infix
┌───┬───┬───┬────┐
│2 3│3 5│5 7│7 11│
└───┴───┴───┴────┘
((2 +/\a)+(2 +/\b));(2 +/\a+b)
┌──────────┬──────────┐
│6 11 17 25│6 11 17 25│
└──────────┴──────────┘
1 <\.a NB. Structure of outfix
┌────────┬────────┬────────┬────────┬───────┐
│3 5 7 11│2 5 7 11│2 3 7 11│2 3 5 11│2 3 5 7│
└────────┴────────┴────────┴────────┴───────┘
((1 +/\.a)+(1 +/\.b));(1 +/\.a+b)
┌──────────────┬──────────────┐
│36 34 31 28 23│36 34 31 28 23│
└──────────────┴──────────────┘
m;n=.8-2*m=.i. 3 3
┌─────┬────────┐
│0 1 2│ 8 6 4│
│3 4 5│ 2 0 _2│
│6 7 8│_4 _6 _8│
└─────┴────────┘
</.m NB. Structure of oblique
┌─┬───┬─────┬───┬─┐
│0│1 3│2 4 6│5 7│8│
└─┴───┴─────┴───┴─┘
((+//.m)+(+//.n));(+//.m+n)
┌───────────┬───────────┐
│8 12 12 4 0│8 12 12 4 0│
└───────────┴───────────┘
The outfix can be used to produce the minors of a matrix argument as shown below:
$ 1 [\. m
3 2 3
box=. <"2 NB. Box tables (2-cells)
box 1 [\. m
┌─────┬─────┬─────┐
│3 4 5│0 1 2│0 1 2│
│6 7 8│6 7 8│3 4 5│
└─────┴─────┴─────┘
f=. 1&(|:\.) NB. Transposed outfixes
box f m
┌───┬───┬───┐
│3 6│0 6│0 3│
│4 7│1 7│1 4│
│5 8│2 8│2 5│
└───┴───┴───┘
minors=.f"2^:2 NB. fOn tables (twice)
$ minors m
3 3 2 2
box minors m NB. All minors of m
┌───┬───┬───┐
│4 5│3 5│3 4│
│7 8│6 8│6 7│
├───┼───┼───┤
│1 2│0 2│0 1│
│7 8│6 8│6 7│
├───┼───┼───┤
│1 2│0 2│0 1│
│4 5│3 5│3 4│
└───┴───┴───┘
These minors of a matrix can be used to determine its adjoint. Moreover, the function minors is linear, as will be illustrated:
min=. minors
(box(min m)+(min n));<box min m+n
┌─────────────┬─────────────┐
│┌───┬───┬───┐│┌───┬───┬───┐│
││4 3│5 3│5 4│││4 3│5 3│5 4││
││1 0│2 0│2 1│││1 0│2 0│2 1││
│├───┼───┼───┤│├───┼───┼───┤│
││7 6│8 6│8 7│││7 6│8 6│8 7││
││1 0│2 0│2 1│││1 0│2 0│2 1││
│├───┼───┼───┤│├───┼───┼───┤│
││7 6│8 6│8 7│││7 6│8 6│8 7││
││4 3│5 3│5 4│││4 3│5 3│5 4││
│└───┴───┴───┘│└───┴───┴───┘│
└─────────────┴─────────────┘
References¶
[1] K. E. Iverson, J Introduction and Dictionary
[2] K. E. Iverson, Arithmetic
Answers to Chapter 2¶
A. Introduction¶
A.1 The first three examples of linear functions apply to vector arguments of any dimension. The rest are restricted to a fixed dimension (4), We are commonly concerned only with a fixed dimension, as in plane geometry (2), solid geometry (3), and space-time (4).
The dimension of the result of a function may differ from the dimension of the argument (as in +/@(1 2 3 4&*)"1 and +/" 1).
A.2 The shape of m (that is, $m) is 3 4 ; the dimension of the result is 3, and the dimension of the argument is 4 .
A.3 Note that the space before the dot in the expression mp=. +/ . * is essential (since /. would otherwise denote an adverb different from /). Also note that the final expressions are tests of linearity, and that the dot conjunction provides for other functions that are similar to the matrix product, but are based upon functions other than summation and multiplication.
A.4 The matrix m must be square, that is, =/$ m.
A.6 Because the function mp&m is an identity.
A.S One is the transpose of the other (n -: |: m). This is true even for non-uniform functions.
B.4 If fm=. f I [ gm=. g I=. = i. 4, then fm and gm are the representations of f and g. The following are the representations of f@g and f+g and f-g, respectively: