To My Many Teachers


 

Preface

Applied mathematics is largely concerned with the design and analysis of explicit procedures for calculating the exact or approximate values of various functions. Such explicit procedures are called algorithms or programs. Because an effective notation for the description of programs exhibits considerable syntactic structure, it is called a programming language.

Much of applied mathematics, particularly the more recent computer-related areas which cut across the older disciplines, suffers from the lack of an adequate programming language. It is the central thesis of this book that the descriptive and analytic power of an adequate programming language amply repays the considerable effort required for its mastery. This thesis is developed by first presenting the entire language and then applying it in later chapters to several major topics.

The areas of application are chosen primarily for their intrinsic interest and lack of previous treatment, but they are also designed to illustrate the universality and other facets of the language. For example, the microprogramming of Chapter 2 illustrates the divisibility of the language, i.e., the ability to treat a restricted area using only a small portion of the complete language. Chapter 6 (Sorting) shows its capacity to compass a relatively complex and detailed topic in a short space. Chapter 7 (The Logical Calculus) emphasizes the formal manipulability of the language and its utility in theoretical work.

The material was developed largely in a graduate course given for several years at Harvard and in a later course presented repeatedly at the IBM Systems Research Institute in New York. It should prove suitable for a two-semester course at the senior or graduate level. Although for certain audiences an initial presentation of the entire language may be appropriate, I have found it helpful to motivate the development by presenting the minimum notation required for a given topic, proceeding to its treatment (e.g., microprogramming), and then returning to further notation. The 130-odd problems not only provide the necessary finger exercises but also develop results of general interest.

Chapter 1 or some part of it is prerequisite to each of the remaining “applications” chapters, but the applications chapters are virtually independent of one another. A complete appreciation of search techniques (Chapter 4) does, however, require a knowledge of methods of representation (Chapter 3). The cross references which do occur in the applications chapters are either nonessential or are specific to a given figure, table, or program. The entire language presented in Chapter 1 is summarized for reference at the end of the book.

In any work spanning several years it is impossible to acknowledge adequately the many contributions made by others. Two major acknowledgments are in order: the first to Professor Howard Aiken, Director Emeritus of the Harvard Computation Laboratory, and the second to Dr. F.P. Brooks, Jr. now of IBM.

It was Professor Aiken who first guided me into this work and who provided support and encouragement in the early years when it mattered. The unusually large contribution by Dr. Brooks arose as follows. Several chapters of the present work were originally prepared for inclusion in a joint work which eventually passed the bounds of a single book and evolved into our joint Automatic Data Processing and the present volume. Before the split, several drafts of these chapters had received careful review at the hands of Dr. Brooks, reviews which contributed many valuable ideas on organization, presentation, and direction of investigation, as well as numerous specific suggestions.

The contributions of the 200-odd students who suffered through the development of the material must perforce be acknowledged collectively, as must the contributions of many of my colleagues at the Harvard Computation Laboratory. To Professor G.A. Salton and Dr. W.L. Eastman, I am indebted for careful reading of drafts of various sections and for comments arising from their use of some of the material in courses. Dr. Eastman, in particular, exorcised many subtle errors from the sorting programs of Chapter 6. To Professor A.G. Oettinger and his students I am indebted for many helpful discussions arising out of his early use of the notation. My debt to Professor R.L. Ashenhurst, now of the University of Chicago, is apparent from the references to his early (and unfortunately unpublished) work in sorting.

Of my colleagues at the IBM Research Center, Messrs. L.R. Johnson and A.D. Falkoff, and Dr. H. Hellerman have, through their own use of the notation, contributed many helpful suggestions. I am particularly indebted to L.R. Johnson for many fruitful discussions on the applications of trees, and for his unfailing support.

On the technical side, I have enjoyed the assistance of unusually competent typists and draughtsmen, chief among them being Mrs. Arthur Aulenback, Mrs. Philip J. Seaward, Jr., Mrs. Paul Bushek, Miss J.L. Hegeman, and Messrs. William Minty and Robert Burns. Miss Jacquelin Sanborn provided much early and continuing guidance in matters of style, format, and typography. I am indebted to my wife for assistance in preparing the final draft.

Chapter 1   The Language

1.1 Introduction

Applied mathematics is concerned with the design and analysis of algorithms or programs. The systematic treatment of complex algorithms requires a suitable programming language for their description, and such a programming language should be concise, precise, consistent over a wide area of application, mnemonic, and economical of symbols; it should exhibit clearly the constraints on the sequence in which operations are performed; and it should permit the description of a process to be independent of the particular representation chosen for the data.

Existing languages prove unsuitable for a variety of reasons. Computer coding specifies sequence constraints adequately and is also comprehensive, since the logical functions provided by the branch instructions can, in principle, be employed to synthesize any finite algorithm. However, the set of basic operations provided is not, in general, directly suited to the execution of commonly needed processes, and the numeric symbols used for variables have little mnemonic value. Moreover, the description provided by computer coding depends directly on the particular representation chosen for the data, and it therefore cannot serve as a description of the algorithm per se.

Ordinary English lacks both precision and conciseness. The widely used Goldstine-von Neumann (1947) flowcharting provides the conciseness necessary to an over-all view of the processes, only at the cost of suppressing essential detail. The so-called pseudo-English used as a basis for certain automatic programming systems suffers from the same defect. Moreover, the potential mnemonic advantage in substituting familiar English words and phrases for less familiar but more compact mathematical symbols fails to materialize because of the obvious but unwonted precision required in their use.

Most of the concepts and operations needed in a programming language have already been defined and developed in one or another branch of mathematics. Therefore, much use can and will be made of existing notations. However, since most notations are specialized to a narrow field of discourse, a consistent unification must be provided. For example, separate and conflicting notations have been developed for the treatment of sets, logical variables, vectors, matrices, and trees, all of which may, in the broad universe of discourse of data processing, occur in a single algorithm.
 

1.2 Programs

A program statement is the specification of some quantity or quantities in terms of some finite operation upon specified operands. Specification is symbolized by an arrow directed toward the specified quantity. thus “y is specified by sin x” is a statement denoted by

      y ← sin x.

A set of statements together with a specified order of execution constitutes a program. The program is finite if the number of executions is finite. The results of the program are some subset of the quantities specified by the program. The sequence or order of execution will be defined by the order of listing and otherwise by arrows connecting any statement to its successor. A cyclic sequence of statements is called a loop.

	Program 1.1  Finite Program		Program 1.2  Infinite Program

Thus Program 1.1 is a program of two statements defining the result v as the (approximate) area of a circle of radius x, whereas Program 1.2 is an infinite program in which the quantity z is specified as (2y)ⁿ on the nth execution of the two statement loop. Statements will be numbered on the left for reference.

A number of similar programs may be subsumed under a single more general program as follows. At certain branch points in the program a finite number of alternative statements are specified as possible successors. One of these successors is chosen according to criteria determined in the statement or statements preceding the branch point. These criteria are usually stated as a comparison or test of a specified relation between a specified pair of quantities. A branch is denoted by a set of arrows leading to each of the alternative successors, with each arrow labeled by the comparison condition under which the corresponding successor is chosen. The quantities compared are separated by a colon in the statement at the branch point, and a labeled branch is followed if and only if the relation indicated by the label holds when substituted for the colon. The conditions on the branches of a properly defined program must be disjoint and exhaustive.

Program 1.3 illustrates the use of a branch point. Statement α5 is a comparison which determines the branch to statements β1, δ1, or γ1, according as z > n, z = n, or z < n. The program represents a crude by effective process for determining x = n^2/3 for any positive cube n.

Program 1.3  Program for x = n^2/3

Program 1.4 shows the preceding program reorganized into a compact linear array and introduces two further conventions on the labeling of branch points. The listed successor of a branch statement is selected if none of the labeled conditions is met. Thus statement 6 follows statement 5 if neither of the arrows (to exit or to statement 8) are followed, i.e. if z < n. Moreover, any unlabeled arrow is always followed; e.g., statement 7 is invariably followed by statement 3, never by statement 8.

A program begins at a point indicated by an entry arrow (step 1) and ends at a point indicated by an exit arrow (step 5). There are two useful consequences of confining a program to the form of a linear array: the statements may be referred to by a unique serial index (statement number), and unnecessarily complex organization of the program manifests itself in crossing branch lines. The importance of the latter characteristic in developing clear and comprehensible programs is not sufficiently appreciated.

	Program 1.4  Linear arrangement of Program 1.3

	Program 1.5  Matrix multiplication

A process which is repeated a number of times is said to be iterated, and a process (such as in Program 1.4) which includes one or more iterated subprocesses is said to be iterative. Program 1.5 shows an iterative process for the matrix multiplication

      C ← AB

defined in the usual way as

Cji = Aki × Bjk ,

i = 1,2, …, μ(A), j = 1,2, …, ν(B),

where the dimensions of an m × n matrix X (of m rows and n columns) is denoted by μ(X) × ν(X).

In all examples used in this chapter, emphasis will be placed on clarity of description of the process, and considerations of efficient execution by a computer or class of computers will be subordinated. These considerations can often be introduced later by relatively routine modifications of the program. For example, since the execution of a computer operation involving an indexed variable is normally more costly than the corresponding operation upon a nonindexed variable, the substitution of a variable s for the variable C_jⁱ specified by statement 5 of Program 1.5 would accelerate the execution of the loop. The variable s would be initialized to zero before each entry to the loop and would be used to specify C_jⁱ at each termination.

The practice of first setting an index to its maximum value and then decrementing it (e.g., the index k in Program 1.5) permits the termination comparison to be made with zero. Since zero often occurs in comparisons, it is convenient to omit it. Thus, if a variable stands alone at a branch point, comparison with zero is implied. Moreover, since a comparison on an index frequently occurs immediately after it is modified, a branch at the point of modification will denote branching upon comparison of the indicated index with zero, the comparison occurring after modification. Designing programs to execute decisions immediately after modification of the controlling variable results in efficient execution as well as notational elegance, since the variable must be present in a central register for both operations.

Since the sequence of execution of statements is indicated by connecting arrows as well as by the order of listing, the latter can be chosen arbitrarily. This is illustrated by the functionally identical Programs 1.3 and 1.4. Certain principles of ordering may yield advantages such as clarity or simplicity of the pattern of connections. Even though the advantages of a particular organizing principle are not particularly marked, the uniformity resulting from its consistent application will itself be a boon. The scheme here adopted is called the method of leading decisions: the decision on each parameter is placed as early in the program as practicable, normally just before the operations indexed by the parameter. This arrangement groups at the head of each iterative segment the initialization, modification, and the termination test of the controlling parameter. Moreover, it tends to avoid program flaws occasioned by unusual values of the argument.

	Program 1.6  Matrix multiplication using leading decisions

For example, Program 1.6 (which is a reorganization of Program 1.5) behaves properly for matrices of dimension zero, whereas Program 1.5 treats every matrix as if it were of dimension one or greater.

Although the labeled arrow representation of program branches provides a complete and graphic description, it is deficient in the following respects: (1) a routine translation to another language (such as computer code) would require the tracing of arrows, and (2) it does not permit programmed modification of the branches.

The following alternative form of a branch statement will therefore be used as well:

      x : y,  r → s.

This denotes a branch to statement number s_i of the program if the relation xr _i y holds. The parameters r and s may themselves be defined and redefined in other parts of the program. The null element ∘ will be used to denote the relation which complements the remaining relations r _i; in particular, (∘)→(s), or simply →s, will denote an unconditional branch to statement s. Program 1.7 shows the use of these conventions in a reformulation of Program 1.6. More generally, two or more otherwise independent programs may interact through a statement in one program specifying a branch in a second. The statement number occurring in the branch must then be augmented by the name of the program in which the branch is effected. Thus the statement (∘) → Program 2.24 executed in Program 1 causes a branch to step 24 to occur in Program 2.

	Program 1.7  A reformulation of Program 1.6, using an algebraic statement of the branching

One statement in a program can be modified by another statement which changes certain of its parameters, usually indices. More general changes in statements can be effected by considering the program itself as a vector p whose components are the individual, serially numbered statements. All the operations to be defined on general vectors can then be applied to the statements themselves. For example, the jth statement can be respecified by the ith through the occurrence of the statement p_j ← p_i.

The interchange of two quantities y and x (that is, x specifies y and the original value of y specifies x) will be denoted by the statement y ↔ x.
 

1.3 Structure of the language

Conventions

The Summary of Notation at the end of the book summarizes the notation developed in this chapter. Although intended primarily for reference, it supplements the text in several ways. It frequently provides a more concise alternative definition of an operation discussed in the text, and it also contains important but easily grasped extensions not treated explicitly in the text. By grouping the operations into related classes it displays their family relationships.

A concise programming language must incorporate families of operations whose members are related in a systematic manner. Each family will be denoted by a specific operation symbol, and the particular member of the family will be designated by an associated controlling parameter (scalar, vector, matrix, or tree) which immediately precedes the main operation symbol. The operand is placed immediately after the main operation symbol. For example, the operation k ↑ x (left rotation of x by k places) may be viewed as the kth member of the set of rotation operators denoted by the symbol ↑.

Operations involving a single operand and no controlling parameter (such as ⌊x⌋, or ⌈x⌉) will be denoted by a pair of operation symbols which enclose the operand. Operations involving two operands and a controlling parameter (such as the mask operation /a, u, b/) will be denoted by a pair of operation symbols enclosing the entire set of variables, and the controlling parameter will appear between the two operands. In these cases the operation symbols themselves serve as grouping symbols.

In interpreting a compound operation such as k ↑ (j ↓ x) it is important to recognize that the operation symbol and its associated controlling parameter together represent an indivisible operation and must not be separated. It would, for example, be incorrect to assume that j ↑ (k ↓ x) were equivalent to k ↑ (j ↓ x), although it can be shown that the complete operations j ↓ and k ↑ do commute, that is k ↑ (j ↓ x) = j ↓ (k ↑ x).

The need for parentheses will be reduced by assuming that compound statements are, except for intervening parentheses, executed from right to left. Thus k ↑ j ↓ x is equivalent to k ↑ (j ↓ x), not to (k ↑ j) ↓ x.

Structured operands such as vectors and matrices, together with a systematic component-by-component generalization of elementary operations, provide an important subordination of detail in the description of algorithms. The use of structured operands will be facilitated by selection operations for extracting a specified portion of an operand, reduction operations for extending an operation (such as logical or arithmetic multiplication) over all components, and permutation operations for reordering components. Operations defined on vectors are extended to matrices: the extended operation is called a row operation if the underlying vector operation is applied to each row of the matrix and a column operation if it is applied to each column. A column operation is denoted by doubling the symbol employed for the corresponding row (and vector) operation.

A distinct typeface will be used for each class of operand as detailed in Table 1.8. Special quantities (such as the prefix vectors ⍺ⁱ defined in Sec. 1.7) will be denoted by Greek letters in the appropriate typeface. For mnemonic reasons, an operation closely related to such a special quantity will be denoted by the same Greek letter. For example, ⍺/u denotes the maximum prefix (Sec. 1.10) of the logical vector u. Where a Greek letter is indistinguishable from a Roman, sanserif characters will be used, e.g. E and I for the capitals of epsilon and iota.

     Table 1.8  Typographic conventions for classes of operands

Literals and variables

The power of any mathematical notation rests largely on the use of symbols to represent general quantities which, in given instances, are further specified by other quantities. Thus Program 1.4 represents a general process which determines x = n^2/3 for any suitable value of n. In a specific case, say n = 27, the quantity x is specified as the number 9.

Each operand occurring in a meaningful process must be specified ultimately in terms of commonly accepted concepts. The symbols representing such accepted concepts will be called literals. Examples of literals are the integers, the characters of the various alphabets, punctuation marks, and miscellaneous symbols such as $ and %. The literals occurring in Program 1.4 are 0, 1, 2.

It is important to distinguish clearly between general symbols and literals. In ordinary algebra this presents little difficulty, since the only literals occurring are the integers and the decimal point, and each general symbol employed includes an alphabetic character. In describing more general processes, however, alphabetic literals (such as proper names) also appear. Moreover, in a computer program, numeric symbols (register addresses) are used to represent the variables.

In general, then, alphabetic literals, alphabetic variables, numeric literals, and numeric variables may all appear in a complex process and must be clearly differentiated. The symbols used for literals will be Roman letters (enclosed in quotes when appearing in text) and standard numerals. The symbols used for variables will be italic letters, italic numerals, and boldface letters as detailed in Table 1.8. Miscellaneous signs and symbols when used as literals will be enclosed in quotes in both programs and text.

It is sometimes desirable (e.g., for mnemonic reasons) to denote a variable by a string of alphabetic or other symbols rather than by a single symbol. The monolithic interpretation of such a string will be indicated by the tie used in musical notation, thus: and may denote the variable “inventory”, a vector of inventory values, and a matrix of inventory values, respectively.

In the set of alphabetic characters, the space plays a special role. For other sets a similar role is usually played by some one element, and this element is given the special name of null element. In the set of numeric digits, the zero plays a dual role as both null element and numeric quantity. The null element will be denoted by the degree symbol ∘.

In any determinate process, each operand must be specified ultimately in terms of literals. In Program 1.4, for example, the quantity k is specified in terms of known arithmetic operations (multiplication and division) involving the literals 1 and 2. The quantity n, on the other hand, is not determined within the process and must presumably be specified within some larger process which includes Program 1.4. Such a quantity is called an argument of the process.

Domain and range

The class of arguments and the class of results of a given operator are called its domain and range, respectively. Thus the domain and range of the magnitude operation (|x|) are the real numbers and the nonnegative real numbers, respectively.

A variable is classified according to the range of values it may assume: it is logical, integral, or numerical, according as the range is the set of logical variables (that is, 0 and 1), the set of integers, or the set of real numbers. Each of the foregoing classes is clearly a subclass of each class following it, and any operation defined on a class clearly applies to any of its subclasses. A variable which is nonnumeric will be called arbitrary. In the Summary of Notation, the range and domain of each of the operators defined is specified in terms of the foregoing classes according to the conventions shown in Sec. S.1.
 

1.4 Elementary operations

The elementary operations employed include the ordinary arithmetic operations, the elementary operations of the logical calculus, and the residue and related operations arising in elementary number theory. In defining operations in the text, the symbol ↔ will be used to denote equivalence of the pair of statements between which it occurs.

Arithmetic operations

According to the usual custom in ordinary algebra, the multiplication symbol may be elided.

Logical operations

The elementary logical operations and, or, and not will be denoted by ∧, ∨ and an overbar and are defined in the usual way as follows:

w ← u ∧ v	↔	w = 1 if and only if u = 1 and	v = 1,
w ← u ∨ v	↔	w = 1 if and only if u = 1 or	v = 1,
w ←	↔	w = 1 if and only if u = 0.

If x and y are numerical quantities, then the expression x < y implies that the quantity x stands in the relation “less than” to the quantity y. More generally, if α and β are arbitrary entities and R is any relation defined on them, the relational statement (α R β) is a logical variable which is true (equal to 1) if and only if α stands in the relation R to β. For example, if x is any real number, then the function

     (x > 0) – (x < 0)

(commonly called the sign function or sgn x) assumes the values 1, 0, or –1 according as x is strictly positive, 0, or strictly negative. Moreover, the magnitude function |x| may be defined as |x| = x × sgn x = x × ((x > 0) – (x < 0)).

The relational statement is a useful generalization of the Kronecker delta, that is δ_jⁱ = (i = j). Moreover, it provides a convenient expression for a number of familiar logical operations. The exclusive or, for example, may be denoted by (u ≠ v), and its negation (i.e., the equivalence function) may be denoted by (u = v).

Residues and congruence

For each set of integers n, j, and b, with b > 0, there exists a unique pair of integers q and r such that

      n = bq + r,   j ≤ r < j + b.

The quantity r is called the j-residue of n modulo b and is denoted by b | _j n. For example, 3 |₀ 9 = 0, 3 |₁ 9 = 3, and 3 |₀ 10 = 1. Moreover, if n ≥ 0, then b |₀ n is the remainder obtained in dividing n by b and q is the integral part of the quotient. A number n is said to be of even parity if its 0-residue modulo 2 is zero and of odd parity if 2 |₀ n = 1.

If two numbers n and m have the same j-residue modulo b, they differ by an integral multiple of b and therefore have the same k-residue module b for any k. If b | _j n = b | _j m, then m and n are said to be congruent mod b. Congruency is transitive and reflexive and is denoted by

      m ≡ n (mod b).

In classical treatments, such as Wright (1939), only the 0-residue is considered. The use of 1-origin indexing (cf. Sec. 1.5) accounts for the interest of the 1-residue.

A number represented in a positional notation (e.g., in a base ten or a base two number system) must, in practice, employ only a finite number of digits. It is therefore often desirable to approximate a number x by an integer. For this purpose two functions are defined:

Thus

	⌈3.14⌉ = 4,		⌊3.14⌋ = 3,		⌊–3.14⌋ = –4,
	⌈3.00⌉ = 3,		⌊3.00⌋ = 3,		⌊–3.00⌋ = –3.

Clearly ⌈x⌉ = –⌊–x⌋ and ⌊x⌋ ≤ x ≤ ⌈x⌉. Moreover, n = b⌊n ÷ b⌋ + b |₀ n for all integers n. Hence the integral quotient ⌊n ÷ b⌋ is equivalent to the quantity q occurring in the definition of the j-residue for the case j = 0.
 

1.5 Structured operands

Elementary operations

Any operation defined on a single operand can be generalized to apply to each member of an array of related operands. Similarly, any binary operation (defined on two operands) can be generalized to apply to pairs of corresponding elements of two arrays. Since algorithms commonly incorporate processes which are repeated on each member of an array of operands, such generalization permits effective subordination of detail in their description. For example, the accounting process defined on the data of an individual bank account treats a number of distinct operands within the account, such as account number, name, and balance. Moreover, the over-all process is defined on a large number of similar accounts, all represented in a common format. Such structured arrays of variables will be called structured operands, and extensive use will be made of three types, called vector, matrix, and tree. As indicated in Sec. S.1 of the Summary of Notation, a structured operand is further classified as logical, integral, numerical, or arbitrary, according to the type of elements in contains.

A vector x is the ordered array of elements (x₁, x₂, x₃, …, x_ν(x)). The variable x_i is called the ith component of the vector x, and the number of components, denoted by ν(x) (or simply by ν when the determining vector is clear from context), is called the dimension of x. Vectors and their components will be represented in lower case boldface italics. A numerical vector x may be multiplied by a numerical quantity k to produce the scalar multiple k × x (or kx) defined as the vector z such that z _i = k × x_i.

All elementary operations defined on individual variables are extended consistently to vectors as component-by-component operations. For example,

Thus if x = (1, 0, 1, 1) and y = (0, 1, 1, 0) then x + y = (1, 1, 2, 1), x ∧ y = (0, 0, 1, 0), and (x < y) = (0, 1, 0, 0).

Matrices

A matrix M is the ordered two-dimensional array of variables

M11, M21, …, Mν(M)1 . M12, M22, …, Mν(M)2 . . . . M1μ(M), M2μ(M), …, Mν(M)μ(M)

The vector (M₁ⁱ, M₂ⁱ, …, M_νⁱ) is called the ith row vector of M and is denoted by M ⁱ. Its dimension ν(M) is called the row dimension of the matrix. The vector (M _j¹, M _j², …, M _j ^μ) is called the jth column vector of M and is denoted by M _j. Its dimension μ(M) is called the column dimension of the matrix.

The variable M _jⁱ is called the (i,j)th component or element of the matrix. A matrix and its elements will be represented by upper case boldface italics. Operations defined on each element of a matrix are generalized component by component to the entire matrix. Thus, if is any binary operator,

      P = M N ↔ M_jⁱ N_jⁱ.

Index systems

The subscript appended to a vector to designate a single component is called an index, and the indices are normally chosen as a set of successive integers beginning at 1, that is, x = (x₁, x₂, … x_ν). It is, however, convenient to admit more general j-origin indexing in which the set of successive integers employed as indices in any structured operand begin with a specified integer j.

The two systems of greatest interest are the common 1-origin system, which will be employed almost exclusively in this chapter, and the 0-origin system. The latter system is particularly convenient whenever the index itself must be represented in a positional number system and will therefore be employed exclusively in the treatment of computer organization in Chapter 2.
 

1.6 Rotation

The left rotation of a vector x is denoted by k ↑ x and specifies the vector obtained by cyclical left shift of the components of x by k places. Thus if a = (1, 2, 3, 4, 5, 6), and b = (c, a, n, d, y), then 2 ↑ a = (3, 4, 5, 6, 1, 2) and 3 ↑ b = 8 ↑ b = (d, y, c, a, n). Formally,^[a]

      z = k ↑ x ↔ z _i = x _j,     where j = ν|₁(i + k).

Right rotation is denoted by k ↓ x and is defined analogously. Thus

      z = k ↓ x ↔ z _i = x _j,     where j = ν|₁(i – k).

If k = 1, it may be elided. Thus ↑ b = (a, n, d, y, c).

Left rotation is extended to matrices in two ways as follows:

	A ← j ↑ B	↔	Ai = ji ↑ Bi
	C ← k B	↔	Ci = kj ↑ Bj

The first operation is an extension of the basic vector rotation to each row of the matrix and is therefore called row rotation. The second operation is the corresponding column operation and is therefore denoted by the doubled operation symbol . For example, if

      k = (0, 1, 2),

B =

a      b      c   d      e      f   g      h      i

k ↑ B =     a      b      c   e      f      d   i      g      h

and

k B =     a      e      i   d      h      c   g      b      f

.

Right rotation is extended analogously.
 

1.7 Special vectors

Certain special vectors warrant special symbols. In each of the following definitions, the parameter n will be used to specify the dimension. The interval vector ⍳^j(n) is defined as the vector of integers beginning with j. Thus ⍳⁰(4)=(0, 1, 2, 3), ⍳¹(4)=(1, 2, 3, 4), and ⍳^–7(5)= (–7, –6, –5, –4, –3). Four types of logical vectors are defined as follows. The jth unit vector ∊ ^j(n) has a one in the jth position, that is, (∊ ^j(n))_k = (k = j). The full vector ∊(n) consists of all ones. The vector consisting of all zeros is denoted both by 0 and by (n). The prefix vector of weight j is denoted by ⍺ ^j(n) and possesses ones in the first k positions, where k is the lesser of j and n. The suffix vector ⍵ ^j(n) is defined analogously. Thus ∊²(3) = (0, 1, 0), ∊(4) = (1, 1, 1, 1), ⍺³(5) = (1, 1, 1, 0, 0), ⍵³(5) = (0, 0, 1, 1, 1), and ⍺⁷(5) = ⍺⁵(5) = (1, 1, 1, 1, 1). Moreover, ⍵ ^j(n) = j ↑ ⍺ ^j(n), and ⍺ ^j(n) = j ↓ ⍵ ^j(n).

A logical vector of the form ⍺^h(n) ∧ ⍵ ^j(n) is called an infix vector. An infix vector can also be specified in the form j ↓ ⍺^k(n), which displays its weight and location more directly.

An operation such as x ∧ y is defined only for compatible vectors x and y, that is, for vectors of like dimension. Since this compatibility requirement can be assumed to specify implicitly the dimension of one of the operands, elision of the parameter n may be permitted in the notation for the special vectors. Thus, if y = (3, 4, 5, 6, 7), the expression ∊ × y and ∊ ^j × y imply that the dimensions of ∊ and ∊ ^j are both 5. Moreover, elision of j will be permitted for the interval vector ⍳ ^j(n) (or ⍳ ^j), and for the residue operator | _j when j is the index origin in use.

It is, of course, necessary to specify the index origin in use at any given time. For example, the unit vector ∊³(5) is (0, 0, 1, 0, 0) in a 1-origin system and (0, 0, 0, 1, 0) in a 0-origin system, even though the definition (that is, (∊ ^j(n))_k = (k = j)) remains unchanged. The prefix and suffix vectors are, of course, independent of the index origin. Unless otherwise specified, 1-origin indexing will be assumed.

The vector ∊(0) is a vector of dimension zero and will be called the null vector. It should not be confused with the special null element ∘.
 

1.8 Reduction

An operation (such as summation) which is applied to all components of a vector to produce a result of a simpler structure is called a reduction. The -reduction of a vector x is denoted by /x and defined as

      z ← /x  ↔  z = (… ((x₁ x₂) x₃) …) x_ν),

where is any binary operator with a suitable domain. Thus +/x is the sum, ×/x is the product, and ∨/x is the logical sum of the components of a vector x. For example, ×/⍳¹(5) = 1 × 2 × 3 × 4 × 5, ×/⍳¹(n) = n!, and +/⍳¹(n) = n(n + 1)/2.

As a further example, De Morgan’s law may be expressed as ∧/u = , where u is a logical vector of dimension two. Moreover, a simple inductive argument (Exercise 1.10) shows that the foregoing expression is the valid generalization of De Morgan’s law for a logical vector u of arbitrary dimension.

A relation R incorporated into a relational statement (xRy) becomes, in effect, an operator on the variables x and y. Consequently, the reduction R/x can be defined in a manner analogous to that of (/x), that is,

      R/x = (… ((x₁ R x₂) R x₃) R …) R x_ν).

The parentheses now imply relational statements as well as grouping. The relational reductions of practical interest are ≠/u, and =/u, the exclusive-or and the equivalence reduction, respectively.

The inductive argument of Exercise 1.10 shows that ≠/u = 2 |₀ (+/u). For example, if u = (1,0,1,1,0), then

and 2 |₀ (+/u) = 2 |₀ 3 = 1. Similarly, =/u = , and as a consequence,

      ≠/u = ,

a useful companion to De Morgan’s law.

To complete the system it is essential to define the value of /∊(0), the reduction of the null vector of dimension zero, as the identity element of the operator or relation . Thus +/∊(0) = ∨/∊(0) = 0, and ×/∊(0) = ∧/∊(0) = 1.

A reduction operation is extended to matrices in two ways. A row reduction of a matrix X by an operator is denoted by

      y ← /X

and specifies a vector y of dimension μ(X) such that y_i = /Xⁱ. A column reduction of X is denoted by z ← //X and specifies a vector z of dimension ν(X) such that z _j = //X _j.

For example, if

U  =		1   0   1   0
		0   0   1   1
		1   1   1   0

then +/U = (2, 2, 3), +//U = (2, 1, 3, 1), ∧//U = (0, 0, 1, 0), ≠/U = (0, 0, 1), =//U = (0, 1, 1, 1), and +/(=//U) = 3.
 

1.9 Selection

Compression

The effective use of structured operands depends not only on generalized operations but also on the ability to specify and select certain elements or groups of elements. The selection of single elements can be indicated by indices, as in the expressions v_i, M ⁱ, M _j, and M _i ^j. Since selection is a binary operation (i.e., to select or not to select), more general selection is conveniently specified by a logical vector, each unit component indicating selection of the corresponding component of the operand.

The selection operation defined on an arbitrary vector a and a compatible (i.e., equal in dimension) logical vector u is denoted by c ← u/a and is defined as follows: the vector c is obtained from a by suppressing from a each component a_i for which u_i = 0. The vector u is said to compress the vector a. Clearly ν(c) = +/u. For example, if u = (1, 0, 0, 0, 1, 1) and a = (M, o, n, d, a, y), then u/a = (M, a, y). Moreover, if n is even and v = (2∊) |₀ ⍳¹(n) = (1, 0, 1, 0, 1, …), then v/⍳¹(n) = (1, 3, 5, …, n–1) and +/(v/⍳¹(n)) = (n/2)².

Row compression of a matrix, denoted by u/A, compresses each row vector Aⁱ to form a matrix of dimension μ(A) × +/u. Column compression, denoted by u//A, compresses each column vector A _j to form a matrix of dimension +/u × ν(A). Compatibility conditions are ν(u) = ν(A) for row compression, and ν(u) = μ(A) for column compression. For example, if A is an arbitrary 3 × 4 matrix, u = (0, 1, 0, 1) and v = (1, 0, 1); then

u/A  =  A21   A41 , A23   A43 A22   A42

v//A  =  A11   A21   A31   A41 , A13   A23   A33   A43

u/v//A  =  v//u/A  =

A21   A41 A23   A43

.

It is clear that row compression suppresses columns corresponding to zeros of the logical vector and that column compression suppresses rows. This illustrates the type of confusion in nomenclature which is avoided by the convention adopted in Sec. 1.3: an operation is called a row operation if the underlying operation from which it is generalized is applied to the row vectors of the matrix, and a column operation if it is applied to columns.

Example 1.1. A bank makes a quarterly review of accounts to produce the following four lists: 1.   the name, account number, and balance for each account with a balance less than two dollars. 2.   the name, account number, and balance for each account with a negative balance exceeding one hundred dollars. 3.   the name and account number of each account with a balance exceeding one thousand dollars. 4.   all unassigned account numbers. The ledger may be described by a matrix       L = (L1,L2,L3)  =  L1 . . . Lm with column vectors L1, L2, and L3, representing names, account numbers, and balances, respectively, and with row vectors L1, L2, …, Lm, representing individual accounts. An unassigned account number is identified by the word “none” in the name position. The four output lists will be denoted by the matrices P, Q, R, and S, respectively. They can be produced by Program 1.9.

L   Bank ledger. Lk   kth account.  L3k   Balance of kth account.   L2k   Account number of kth    account. L1k   Name of kth account or “none” if account number L2k unused. Legend

Program 1.9  Selection on bank ledger L (Example 1.1)

Mesh, mask, and expansion

A logical vector u and the two vectors a = /c and b = u/c, obtained by compressing a vector c, collectively determine the vector c. The operation which specifies c as a function of a, b, and u is called a mesh and is defined as follows: If a and b are arbitrary vectors and if u is a logical vector such that +/ = ν(a) and +/u = ν(b), then the mesh of a and b on u is denoted by \a, u, b\ and is defined as the vector c such that /c = a and u/c = b. The mesh operation is equivalent to choosing successive components of c from a or b according as the successive components of u are 0 or 1. If, for example, a = (s, e, k), b = (t, a), and u = (0, 1, 0, 1, 0), then \a, u, b\ = (s, t, e, a, k). As a further example,

(a)		(b)
		a, b   Given vectors. c   c = (a1, b1, b2, a2, b3, b4, …)   i   Index of a. j   Index of b. k   Index of c. u   a = (0, 1, 1, 0, 1, 1, 0, …). Legend

Program 1.10  Interfiling program

Program 1.10a (which describes the merging of the vectors a and b, with the first and every third component thereafter chosen from a) can be described alternatively as shown in Program 1.10b. Since ⍳¹ = (1, 2, 3, 4, 5, 6, …), then (3∊) |₀ ⍳¹ = (1, 2, 0, 1, 2, 0, …), and consequently the vector u specified by step 1 is of the form u = (0, 1, 1, 0, 1, 1, 0, …).

Mesh operations on matrices are defined analogously, row mesh and column mesh being denoted by single and double reverse virgules, respectively.

The catenation of vectors x, y, …, z is denoted by x y … z and is defined by the relation

      x y … z  =  (x₁, x₂, …, x_ν(x), y₁, y₂, …, z_ν(z)).

Catenation is clearly associative and for two vectors x and y it is a special case of the mesh \x, u, y\ in which u is a suffix vector.

In numerical vectors (for which addition of two vectors is defined), the effect of the general mesh operation can be produced as the sum of two meshes, each involving one zero vector. Specifically,

\x, u, y\	=	\x, u, 0\ + \0, u, y\
	=	\0, , x\ + \0, u, y\.

The operation \0, u, y\ proves very useful in numerical work and will be called expansion of the vector y, denoted by u\y. Compression of u\y by u and by clearly yields y and 0, respectively. Moreover, any numerical vector x can be decomposed by a compatible vector u according to the relation

      x = \/x + u\u/x.

The two terms are vectors of the same dimension which have no nonzero components in common. Thus if u = (1, 0, 1, 0, 1), the decomposition of x appears as

      x = (0, x₂, 0, x₄, 0) + (x₁, 0, x₃, 0, x₅).

Row expansion and column expansion of matrices are defined and denoted analogously. The decomposition relations become

      X = \/X + u\u/X,
and
      X = \\//X + u\\u//X.

The mask operation is defined formally as follows:

      c ← /a, u, b/  ↔  /c = /a, and u/c = u/b.

The vectors c, a, u, and b are clearly of a common dimension and c_i = a_i or b_i according as u_i = 0 or u_i = 1. Moreover, the compress, expand, mask, and mesh operations on vectors are related as follows:

/a, u, b/	=	\/a, u, u/b\,
\a, u, b\	=	/\a, u, u\b/.

Analogous relations hold for the row mask and row mesh and for the column mask and column mesh.

Certain selection operations are controlled by logical matrices rather than by logical vectors. The row compression U/A selects elements of A corresponding to the nonzero elements of U. Since the nonzero elements of U may occur in an arbitrary pattern, the result must be construed as a vector rather than a matrix. More precisely, U/A denotes the catenation of the vectors U ⁱ/Aⁱ obtained by row-by-row compression of A by U. The column compression U//A denotes the catenation of the vectors U_j/A_j. If, for example

U =		0   1   0   1   1
		1   1   0   0   0
		0   1   1   0   0

then
      U/A = (A₂¹, A₄¹, A₅¹, A₁², A₂², A₂³, A₃³),
and
      U//A = (A₁², A₂¹, A₂², A₂³, A₃³, A₄¹, A₅¹).

Compression by the full matrix E (defined by = 0) produces either a row list (E/A) or a column list (E//A) of the matrix A. Moreover, a numerical matrix X can be represented jointly by the logical matrix U and the row list U/X (or the column list U//X), where U = (X ≠ 0). If the matrix X is sparse (i.e., the components are predominantly zero), this provides a compact representation which may reduce the computer storage required for X.

The compression operations controlled by matrices also generate a group of corresponding mesh and mask operations as shown in Sec. S.9.
 

1.10 Selection vectors

The logical vector u involved in selection operations may itself arise in various ways. It may be a prefix vector ⍺ ^j, a suffix ⍵ ^j, or an infix (i ↓ ⍺ ^j); the corresponding compressed vectors ⍺ ^j/x, ⍵ ^j/x, and (i ↓ ⍺ ^j)/x are called a prefix, suffix, and infix of x, respectively.

Certain selection vectors arise as functions of other vectors, e.g., the vector (x ≥ 0) can be used to select all nonnegative components of x, and (b ≠ *∊) serves to select all components of b which are not equal to the literal “*”. Two further types are important: the selection of the longest unbroken prefix (or suffix) of a given logical vector, and the selection of the set of distinct components occurring in a vector. The first is useful in left (or right) justification or in a corresponding compression intended to eliminate leading or trailing “filler components” of a vector (such as left zeros in a number or right spaces in a short name).

For any logical vector u, the maximum prefix of u is denoted by ⍺/u and defined as follows:

      u ← ⍺/u  ↔  v = ⍺ ^j

where j is the maximum value for which ∧/(⍺ ^j/u) = 1. The maximum suffix is denoted by ⍵/u and is defined analogously. If, for example, u = (1, 1, 1, 0, 1, 1, 0, 0, 1, 1), then ⍺/u = (1, 1, 1, 0, 0, 0, 0, 0, 0, 0), ⍵/u = (0, 0, 0, 0, 0, 0, 0, 0, 1, 1), +/⍺/u = 3, and +/⍵/u = 2.

The leading zeros of a numerical vector x can clearly be removed either by compression:

or by left justification (normalization):

      z ← (+/⍺/(x = 0)) ↑ x.

The extension of the maximum prefix operation to the rows of a logical matrix U is denoted by ⍺/U and defined as the compatible logical matrix V, such that V ⁱ = ⍺/U ⁱ. The corresponding maximum column prefix operation is denoted by ⍺//U. Right justification of a numerical matrix X is achieved by the rotation k ↓ X, where k = +/⍵/(X = 0), and top justification is achieved by the rotation ((+//⍺//(X = 0) X (see Sec. S.6.)

A vector whose components are all distinct will be called an ordered set. The forward set selector on b is a logical vector denoted by σ/b and defined as follows: the statement v ← σ/b implies that v_j = 1 if and only if b_j differs from all preceding components of b. Hence v/b is a set which contains all distinct components of b, and +/v/⍳ is a minimum. For example, if c = (C, a, n, a, d, a), then (σ/c)/c = (C, a, n, d) is a list of the distinct letters in c in order of occurrence. Clearly (σ/b)/b = b if and only if b is a set.

The backward set selector τ/b is defined analogously (e.g., (τ/c)/c = (C, n, d, a)). Forward and backward set selection are extended to matrices by both rows (σ/B, and τ/B) and columns (σ//B, and τ//B) in the established manner.
 

1.11 The generalized matrix product

The ordinary matrix product of matrices X and Y is commonly denoted by XY and defined as follows:

Z ← XY  ↔  Z j i = Xki × Yjk,

i = 1, 2, …, μ(X) j = 1, 2, …, ν(Y).

      (XY)_j ⁱ = +/(X ⁱ × Y_j).

This formulation emphasizes the fact that matrix multiplication incorporates two elementary operations (+, ×) and suggests that they be displayed explicitly. The ordinary matrix product will therefore be written as X Y.

More generally, if ₁ and ₂ are any two operators (whose domains include the relevant operands), then the generalized matrix product is defined as follows:

()ji  =  1/(X i 2 Yj),

i = 1, 2, …, μ(X) j = 1, 2, …, ν(Y).

A  =   1   3   2   0   2   1   0   1   4   0   0   2

and

B  =   4   1   0   3   0   2   2   0

A B  =   4   14  ,  10    5   20    4

A B  =   0   1  ,  0   0   1   0

A B  =   1   0  ,     and  1   1   0   1

(A ≠ 0) B  =   4   6  .  6   4   6   1

The generalized matrix product and the selection operations together provide an elegant formulation in several established areas of mathematics. A few examples will be chosen from two such areas, symbolic logic and matrix algebra.

In symbolic logic, De Morgan’s laws (∧/u = and =/u = ) can be applied directly to show that

      U V = .

In matrix algebra, the notion of partitioning a matrix into submatrices of contiguous rows and columns can be generalized to an arbitrary partitioning specified by a logical vector u. The following easily verifiable identities are typical of the useful relations which result:

	X Y		=		(/X) (//Y) + (u/X) (u//Y),
	u/(X Y)		=		X (u/Y),
	u//(X Y)		=		(u//X) Y.

The first identity depends on the commutativity and associativity of the operator + and can clearly be generalized to other associative commutative operators, such as ∧, ∨, and ≠.

The generalized matrix product applies directly (as does the ordinary matrix product X Y) to vectors considered as row (that is, 1 × n) or as column matrices. Thus:

	z ← X y	↔	z i	=	1/(X i 2 y),
	z ← y X	↔	z j	=	1/(y 2 Xj ),
	z ← y x	↔	z	=	1/(y 2 x).

The question of whether a vector enters a given operation as a row vector or as a column vector is normally settled by the requirement of conformability, and no special indication is required. Thus y enters as a column vector in the first of the preceding group of definitions and as a row vector in the last two. The question remains, however, in the case of the two vector operands, which may be considered with the pre-operand either as a row (as in the scalar product y x) or as a column. The latter case produces a matrix Z and will be denoted by

      Z ← y ₂ x,

where Z_jⁱ = y_{i 2} x_j, μ(Z) = ν(y), and ν(Z) = ν(x).^[b] For example, if each of the vectors indicated is of dimension three, then

	∊ y  =   y1   y2   y3  ;  y1   y2   y3   y1   y2   y3		y ∊  =   y1   y1   y1  ;  y2   y2   y2   y3   y3   y3
	⍺2(3) ⍺2(3)  =   1   1   0  .  1   1   0   0   0   0

1.12 Transpositions

Since the generalized matrix product is defined on columns of the post-operand and rows of the pre-operand, convenient description of corresponding operations on the rows of the post-operand and columns of the pre-operand demands the ability to transpose a matrix B, that is, to specify a matrix C such that C_i ^j = B_jⁱ. In ordinary matrix algebra this type of transposition suffices, but in more general work transpositions about either diagonal and about the horizontal and the vertical are also useful. Each of these transpositions of a matrix B is denoted by a superior arrow whose inclination indicates the axis of the transposition. Thus:

	C ←		Ci j = Bj i		i = 1, 2, …, μ(B) j = 1, 2, …, ν(B)
	C ←
	C ←
	C ←

For a vector x, either or will denote reversal of the order of the components. For ordinary matrix transposition (that is, ), the commonly used notation will also be employed.

Since transpositions can effect any one or more of three independent alternatives (i.e., interchange of row and column indices or reversal of order of row or of column indices), repeated transpositions can produce eight distinct configurations. There are therefore seven distinct transformations possible; all can be generated by any pair of transpositions having nonperpendicular axes.^[c]
 

1.13 Special logical matrices

Certain of the special logical vectors introduced in Sec. 1.7 have useful analogs in logical matrices. Dimensions will again be indicated in parentheses (with the column dimension first) and may be elided whenever the dimension is determined by context. If not otherwise specified, a matrix is assumed to be square.

Cases of obvious interest are the full matrix E(m × n), defined by (m × n) = 0, and the identity matrix I(m × n), defined by I_jⁱ = (i = j). More generally, superdiagonal matrices ^kI(m × n) are defined such that ^kI_jⁱ(m × n) = (j = i + k), for k ≥ 0. Clearly ⁰I = I. Moreover, for square matrices, ^hI ^kI = ^{(h + k)}I.

Four triangular matrices will be defined, the geometrical symbols employed for each indicating the (right-angled isosceles) triangular area of the m × n rectangular matrix which is occupied by ones. Thus

	C ← (m × n)	↔	C j i		= (i + j ≤ min(m, n))	for i = 1, 2, …, m and j = 1, 2, …, n.
	C ← (m × n)	↔
	C ← (m × n)	↔
	C ← (m × n)	↔

The use of the matrices E and I will be illustrated briefly. The relation u v = 2 |₀ (u v) can be extended to logical matrices as follows:

      U V = (2E) |₀ (U V);

the trace of a square numerical matrix X may be expressed as t = +/I/X. The triangular matrices are employed in the succeeding section.
 

1.14 Polynomials and positional number systems

Any positional representation of a number n in a base b number system can be considered as a numerical vector x whose base b value is the quantity n = w x, where the weighting vector w is defined by w = (b^ν(x)–1, b^ν(x)–2, … b², b¹, 1). More generally, x may represent a number in a mixed-radix system in which the successive radices (from high to low order) are the successive components of a radix vector y.

The base y value of x is a scalar denoted by y ⊥ x and defined as the scalar product y ⊥ x = w x, where w = y is the weighting vector. For example, if y = (7, 24, 60, 60) is the radix vector for the common temporal system of units, and if x = (0, 2, 1, 18) represents elapsed time in days, hours, minutes, and seconds, then

      t = w x = (86400, 3600, 60, 1) (0, 2, 1, 18) = 7278

is the elapsed time in seconds, and the weighting vector w is obtained as the product

	y   =		0   1   1   1				7		=		×/(24, 60, 60)		=		86400
			0   0   1   1				24				×/(60, 60)				3600
			0   0   0   1				60				×/(60)				60
			0   0   0   0				60				×/∊(0)				1

If b is any integer, then the value of x in the fixed base b is denoted by (b∊) ⊥ x. For example, (2∊) ⊥ ⍺²(5) = 24. More generally, if y is any real number, then (y∊) ⊥ x is clearly a polynomial in y with coefficients x₁, x₂, … x_ν, that is,

      (y∊) ⊥ x  =  x₁ y^ν(x)–1 + … + x_ν–1 y + x_ν .

Writing the definition of y ⊥ x in the form

      y ⊥ x  =  ( y) x

exhibits the fact that the operation ⊥ is of the double operator type. Its use in the generalized matrix product therefore requires no secondary scan operator. This will be indicated by a null placed over the symbol ⊥. Thus

      Z ← X Y  ↔  Z _j ⁱ = X ⁱ ⊥ Y _j.

For example, (y∊) X represents a set of polynomials in y with coefficients X₁, X₂, …, X_ν, and Y  x represents a set of evaluations of the vector x in a set of bases Y¹, Y², …, Y^μ.
 

1.15 Set operations

In conventional treatments, such as Jacobson (1951) or Birkhoff and MacLane (1941), a set is defined as an unordered collection of distinct elements. A calculus of sets is then based on such elementary relations as set membership and on such elementary operations as set intersection and set union, none of which imply or depend on an ordering among members of a set. In the present context it is more fruitful to develop a calculus of ordered sets.

A vector whose components are all distinct has been called (Sec. 1.10) an ordered set and (since no other types are to be considered) will hereafter be called a set. In order to provide a closed system, all of the “set operations” will, in fact, be defined on vectors. However, the operations will, in the special case of sets, be analogous to classical set operations. The following vectors, the first four of which are sets, will be used for illustration throughout.

A variable z is a member of a vector x if z = x_i for some i. Membership is denoted by z ε x. A vector x includes a vector y (denoted by either x ⊇ y or y ⊆ x) if each element y_i is a member of x. If both x ⊇ y and x ⊆ y, then x and y are said to be similar. Similarity of x and y is denoted by x ≡ y. For example, t ⊆ s, t ⊆ r, t ⊆ a, a ⊆ t, t ≡ a, and t ≢ r. If x ⊆ y and x ≢ y, then x is strictly included in y. Strict inclusion is denoted by x ⊂ y.

The characteristic vector of x on y is a logical vector denoted by ∊_y^x, and defined as follows:

      u = ∊_y^x  ↔  ν(u) = ν(y), and u_j = (y_j ε x).

For example, ∊_s^t = (0, 1, 1, 1, 0), ∊_t^s = (1, 1, 1), ∊_s^d = (1, 0, 0, 0, 1), ∊_d^s = (1, 0, 1, 0), and ∊_n^r = (1, 0, 1, 0, 1, 1).

The intersection of y with x is denoted by y ∩ x, and defined as follows:

      y ∩ x = ∊_y^x/y.

For example, s ∩ d = (s, d), d ∩ s = (d, s), s ∩ r = (a, t, e, d), and r ∩ s = (e, d, d, a, t). Clearly, x ∩ y ≡ y ∩ x, although x ∩ y is not, in general, equal to y ∩ x, since the components may occur in a different order and may be repeated a different number of times. The vector x ∩ y is said to be ordered on x. Thus a is ordered on s. If x and y contain no common elements (that is, (x ∩ y) = ∊(0)), they are said to be disjoint.

The set difference of y and x is denoted by y ∆ x and is defined as follows:

      y ∆ x = _y^x/y.

Hence y ∆ x is obtained from y by suppressing those components which belong to x. For example, _s^t = (1, 0, 0, 0, 1) and s ∆ t = (s, d). Moreover, _t^s = (0, 0, 0) and t ∆ s = ∊(0).

The union of y and x is denoted by y ∪ x and defined as follows:^[d] y ∪ x = y (x ∆ y). For example, s ∪ d = (s, a, t, e, d, u, k), d ∪ s = (d, u, s, k, a, t, e), s ∪ a = s ∪ t = s, and n ∪ t = (n, o, n, s, e, t, a). In general, x ∪ y ≡ y ∪ x, and x ≡ (x ∩ y) ∪ (x ∆ y). If x and y are disjoint, their union is equivalent to their catenation, that is, x ∩ y = ∊(0) implies that x ∪ y = x y.

In the foregoing development, the concepts of inclusion and similarity are equivalent to the concepts of inclusion and equality in the conventional treatment of (unordered) sets. The remaining definitions of intersection, difference, and union differ from the usual formulation in that the result of any of these operations on a pair of ordered sets is again an ordered set. With respect to similarity, these operations satisfy the same identities as do the analogous conventional set operations on unordered sets with respect to equality.

The forward selection σ/b and the backward selection τ/b defined in Sec. 1.10 can both be used to reduce any vector b to a similar set, that is,

      (σ/b)/b ≡ (τ/b)/b ≡ b.

Moreover, if f = (σ/x)/b, g = (σ/y)/y, and h = (σ/z)/z, then x = y ∩ z implies that f = g ∩ h, and x = y ∪ z implies that f = g ∪ h.

The unit vector ∊ ^j(n) will be recognized as a special case of the characteristic vector ∊_y^x in which x consists of the single component j, and y = ⍳^h(n), where h is the index origin in use. In fact, the notation ∊ ^j_i^h can be used to make explicit the index origin h assumed for ∊ ^j.

If z is any vector of dimension two such that z₁ ε x and z₂ ε y, then z is said to belong to the Cartesian product of x and y. Thus if x = (a, b, c) and y = (0, 1), the rows of the matrix

	A  =		a   0
			a   1
			b   0
			b   1
			c   0
			c   1

are a complete list of the vectors z belonging to the product set of x and y. The matrix A will be called the Cartesian product of x and y and will be denoted x y.

The foregoing definition by example will be formalized in a more general way that admits the Cartesian product of several vectors (that is, u v … y) which need not be sets, and which specifies a unique ordering of the rows of the resulting matrix. Consider a family of vectors x¹, x², …, x^s of dimensions d₁, d₂, …, d_s. Then

      A ← x¹ x² … x^s  ↔  A^{1 + d ⊥ (k – ∊)} = (x¹_k1, x²_k2, …, x^s_ks),

for all vectors k such that 1 ≤ k_i ≤ d_i. Clearly, ν(A) = s, and μ(A) = ×/d. As illustrated by Table 1.11, the rows of the Cartesian product A are not distinct if any one of the vectors xⁱ is not a set.

x1 = (a, b, a) x2 = (#, *) x3 = (0, 1) d = (3, 2, 2)

A  =  a   #   0 a   #   1 a   *   0 a   *   1 b   #   0 b   #   1 b   *   0 b   *   1 a   #   0 a   #   1 a   *   0 a   *   1

      Table 1.11  The Cartesian product A = x¹ x² x³

If the vectors xⁱ are all of the the same dimension, they may be considered as the columns of a matrix X, that is, X_i = xⁱ. The product x¹ x² … x^s = X₁ X₂ … X_s may then be defined by /X, or alternatively by //Y, where Y is the transpose of X. For example, if

X = ⍳0(2) ∊(3) =		0  0  0		,
		1  1  1

then /X is the matrix of arguments of the truth table for three variables.
 

1.16 Ranking

The rank or index of an element c ε b is called the b index of c and is defined as the smallest value of i such that c = b_i. To establish a closed system, the b index of any element a b will be defined as the null characer ∘. The b index of any element c will be denoted by b ⍳ c; if necessary, the index origin in use will be indicated by a subscript appended to the operator ⍳. Thus, if b = (a, p, e), b ⍳₀ p = 1, and b ⍳₁ p = 2.

The b index of a vector c is defined as follows:

      k ← b ⍳ c  ↔  k _i = b ⍳ c _i.

The extension to matrices may be either row by row or (as indicated by a doubled operator symbol ⍳⍳) column by column, as follows:

Use of the ranking operator in a matrix product requires no secondary scan and is therefore indicated by a superior null symbol. Moreover, since the result must be limited to a two-dimensional array (matrix), either the pre- or post-operand is required to be a vector. Hence

	J ← B c	↔	J i ← B i ⍳ c i,
	K ← b C	↔	Kj ← bj ⍳ Cj.

The first of these ranks the components of c with respect to each of a set of vectors B¹, B², …, B^μ, whereas the second ranks each of the vectors C₁, C₂, …, C_ν with respect to the fixed vector b.

The use of the ranking operation can be illustrated as follows. Consider the vector b = (a, b, c, d, e) and the set of all 3⁵ three-letter sequences (vectors) formed from its components. If the set is ordered lexically, and if x is the jth member of the set (counting from zero), then

      j = (ν(b)∊) ⊥ (b ⍳₀ x).

For example, if x = (c, a, b), then (b ⍳₀ x) = (2, 0, 1), and j = 51.
 

1.17 Mapping and permutation

Reordering operations

The selection operations employed thus far do not permit convenient reorderings of the components. This is provided by the mapping operation defined as follows:^[e]

      c ← a _k  ↔  c _i = a _ki

For example, if a = (a, b, …, z) and k = (6, 5, 4), then c = (f, e, d).

The foregoing definition is meaningful only if the components of k each lie in the range of the indices of a, and it will be extended by defining a _j as the null element ∘ if j does not belong to the index set of a. Formally,

	c ← a m  ↔  c i =			a mi		if m i ε ⍳1(ν(a))
				∘		if m i ⍳1(ν(a)).

The ability to specify an arbitrary index origin for the vector a being mapped is provided by the following alternative notation for mapping:

	c ← m ∫j a  ↔  c i =			a mi		if m i ε ⍳j(ν(a))
				∘		if m i ⍳j(ν(a)),

where j-origin indexing is assumed for the vector a. For example, if a is the alphabet and m = (5, ∘, ∘, 4, 27, ∘, 3), then c = m ∫₀ a = (f, ∘, ∘, e, ∘, ∘, d), and (c ≠ ∘∊)/c = (f, e, d). Moreover, m ∫₂ a = (d, ∘, ∘, c, z, ∘, b). Elision of j is permitted.

If a ⊆ b, and m = b ⍳_j a, then clearly m ∫_j b = a. If a b, then m ∫_j b contains (in addition to certain nulls) those components common to b and a, arranged in the order in which they occur in a. In other words,

      (m ≠ ∘∊)/(m ∫_j b) = a ∩ b.

Consequently, if p, q, …, t are vectors, each contained in b, then each can be represented jointly by the vector b and a mapping vector. If, for example, b is a glossary and p, q, etc. are texts, the total storage required for b and the mapping vectors might be considerably less than for the entire set of texts.

Mapping may be shown to be associative, that is, m¹ ∫_i (m² ∫_j a) = (m¹ ∫_i m²) ∫_j a. Mapping is not, in general, commutative.

Mapping is extended to matrices as follows:

Row and column mappings are associative. A row mapping ¹M and a column mapping ²M do not, in general, commute, but do if all rows of ¹M agree (that is, ¹M = ∊ p), and if all columns of ²M agree (that is, ²M = q ∊). The generalized matrix product is defined for the cases M A, and M a.

The alternative notation (that is, c = a_m), which does not incorporate specification of the index origin, is particularly convenient for matrices and is extended as follows:

Permutations

A vector k of dimension n is called a j-origin permutation vector if k ≡ ⍳^j(n). A permutation vector used to map any set of the same dimension produces a reordering of the set without either repetition or suppression of elements, that is, k ∫_j a ≡ a for any set a of dimension ν(k). For example, if a = (f, 4, *, 6, z), and k = (4, 2, 5, 1, 3), then k ∫₁ a = (6, 4, z, f, *).

If p is an h-origin permutation vector and q is any j-origin permutation vector of the same dimension, then q ∫_j p is an h-origin permutation vector.

Since

      ⍳^j(ν(a)) ∫_j a = a,

the interval vector ⍳^j(n) will also be called the j-origin identity permutation vector. If p and q are two j-origin permutation vectors of the same dimension n and if q ∫_j p = ⍳^j(n), then p ∫_j q = ⍳^j(n) also and p and q are said to be inverse permutations. If p is any j-origin permutation vector, then q = p ⍳_j ⍳^j is inverse to p.

The rotation operation k ↑ x is a special case of permutation.

Function mapping

A function f which defines for each element b_i of a set b a unique correspondent a_k in a set a is called a mapping from b to a. If f(b_i) = a_k, the element b_i is said to map into the element a_k. If the elements f(b_i) exhaust the set a, the function f is set to map b onto a. If b maps onto a and the elements f(b_i) are all distinct, the mapping is said to be one-to-one or biunique. In this case, ν(a) = ν(b), and there exists an inverse mapping from a to b with the same correspondences.

A program for performing the mapping f from b to a must therefore determine for any given element b ε b, the correspondent a ε a, such that a = f(b). Because of the convenience of operating upon integers (e.g., upon register addresses or other numeric symbols) in the automatic execution of programs, the mapping is frequently performed in three successive phases, determining in turn the following quantities:

The three phases are shown in detail in Program 1.12a. The ranking is performed (steps 1-3) by scanning the set b in order and comparing each element with the argument b. The second phase is a permutation of the integers 1, 2, …, ν(b), which may be described by a permutation vector j, such that j_i = k. The selection of j_i (step 4) then defines k, which, in turn, determines the selection of a_k on step 5.

If k is a permutation vector inverse to j, then Program 1.12b describes a mapping inverse to that of Program 1.12a. If j = (1, 3, 5, 2, 4), then k = (1, 4, 2, 5, 3). The inverse mapping can also be described in terms of j, as is done in Program 1.12c. The selection of the ith component of the permutation vector is then necessarily replaced by a scan of its components. Programs 1.12d and 1.12e show alternative formulations of Program 1.12a.

(a) bi ↔ aji		(b) ai ↔ bki
(c) ai ↔ bki		(d) bi ↔ aji
		(e) bi ↔ aji

Legend

Program 1.12  Mapping defined by a permutation vector j

Ordering vector

If x is a numeric vector and k is a j-origin permutation vector such that the components of y = k ∫_j x are in ascending order, then k is said to order x. The vector k can be determined by an ordering operation defined as follows:

      k ← θ_j/x

implies that k is a j-origin permutation vector, and that if y = k ∫_j x, then either y_i < y_i+1 or y_i = y_i+1 and k_i < k_i+1. The resulting vector k is unique and preserves the original relative order among equal components. For example, if x = (7, 3, 5, 3), then θ₁/x = (2, 4, 3, 1).

The ordering operation is extended to arbitrary vectors by treating all nonnumeric quantities as equal and as greater than any numeric quantity. For example, if a = (7, ∘, 3,∘, 5, 3), then θ₁/a = (3, 6, 5, 1, 2, 4), and if b is any vector with no numerical components, then θ_j/b = ⍳^j(ν(b)).

Ordering of a vector a with respect to a vector b is achieved by ordering the b-index of a. For example, if a = (e, a, s, t, 4, 7, t, h), and b is the alphabet, then m = b ⍳₁ a = (5, 1, 19, 20, ∘, ∘, 20, 8) and θ₁/m = (2, 1, 8, 3, 4, 7, 5, 6).

The ordering operation is extended to matrices by the usual convention. If K = θ_j//A, then each column of the matrix B = K ∫∫_j A is in ascending order.
 

1.18 Maximization

In determining the maximum m over components of a numerical vector x, it is often necessary to determine the indices of the maximum components as well. The maximization operator is therefore defined so as to determine a logical vector v such that v/x = m∊.

Maximization over the entire vector x is denoted by ∊⌈x, and is defined as follows: if v = ∊⌈x, then there exists a quantity m such that v/x = m∊ and such that all components of /x are strictly less than m. The maximization is assumed by a single component of x if and only if +/v = 1. The actual value of the maximum is given by the first (or any) component of v/x. Moreover, the j-origin indices of the maximum components are the components of the vector v/⍳^j.

More generally, the maximization operation v ← u⌈x will be defined so as to determine the maximum over the subvector u/x only, but to express the result v with respect to the entire vector x. More precisely,

      v ← u⌈x  ↔  v = u\(∊⌈(u/x)).

The operation may be visualized as follows — a horizontal plane punched at points corresponding to the zeros of u is lowered over a plot of the components of x, and the positions at which the plane first touches them are the positions of the unit components of v. For example, maximization over the negative components of x is denoted by

      v ← (x < 0)⌈x

and if x = (2, –3, 7, –5, 4, –3, 6), then (x < 0) = (0, 1, 0, 1, 0, 1, 0), v = (0, 1, 0, 0, 0, 1, 0), v/x = (–3, –3), (v/x)₁ = –3, and v/⍳¹ = (2, 6). Minimization is defined analogously and is denoted by u⌊x.

The extension of maximization and minimization to arbitrary vectors is the same as for the ordering operation, i.e., all nonnumeric quantities are treated as equal and as exceeding all numeric quantities. The extensions to matrices are denoted and defined as follows:

	V ← U ⌈ X	↔	V i	=	U i ⌈ X i,
	V ← U ⌈⌈ X	↔	Vj	=	Uj ⌈ Xj,
	V ← U x	↔	V i	=	U i ⌈ x,
	V ← u X	↔	Vj	=	u ⌈ Xj.

As in the case of the ordering operation, maximization in a vector a with respect to order in a set b is achieved by maximizing over the b-index of a. Thus if

H	=		d c h d h s h d c h c h d
			a 6 k q 4 3 5 k 8 2 j 9 2

represents a hand of thirteen playing cards, and if

B	=		c d h s ∘ ∘ ∘ ∘ ∘  ∘ ∘ ∘ ∘		,
			2 3 4 5 6 7 8 9 10 j q k a

B ⍳0 H	=		1 0  2  1 2 3 2  1 0 2 0 2 1		,
			12 4 11 10 2 1 3 11 6 0 9 7 0

      (4, 13) (B ⍳₀ H)   =   (25, 4, 37, 23, 28, 40, 29, 24, 6, 26, 9, 33, 13),

      (∊⌈((4, 13) (B ⍳₀ H)))/H   =   (s, 3)

is the highest ranking card in the hand.
 

1.19 Inverse functions

To every biunique^[f] function f there corresponds an inverse function g such that g(f(x)) = x for each argument x in the domain of the function f. It is common practice either to introduce a distinct symbolism for the inverse function, as for the inverse functions of logarithm (log_b x) and exponentiation (b³), or to use a superscript –1, as in sin^–1x or f ^–1(x).

The first alternative doubles the number of distinct operator symbols required and obscures the relation between pairs of inverse functions; the second raises other difficulties. The solution adopted here is that of implicit specification; i.e. a statement is permitted to specify not only a variable but also any function of that variable. Functions may therefore appear on both sides of the specification arrow in a statement. For example,

      (2∊) ⊥ x ← z

specifies the variable x as the vector whose base two value is the number z.

Certain ambiguities remain in the foregoing statement. First, the dimension of x is not specified. For example, if z = 12, x = (1, 1, 0, 0) is an admissible solution, but so are (0, 1, 1, 0, 0) and (0, 0, 0, 1, 1, 0, 0). This could be clarified by compatibility with a specified dimension of ∊. Thus the statement

      (2∊(5)) ⊥ x ← z

specifies x unambiguously as (0, 1, 1, 0, 0). More generally, however, any previously specified auxiliary variables will be listed to the right of the main statement, with a semicolon serving as a separation symbol. The current example could therefore be written as

      ν(x) ← 5
      (2∊) ⊥ x ← z;   ν(x)

The second ambiguity concerns the permissible range of the individual components of x. For example, the base two value of x = (5, 2) is also twelve. For certain functions it is therefore necessary to adopt some obvious conventions concerning the range of the result. The assumption implicit in the preceding paragraph is that each component of x is limited to the range of the residues modulo the corresponding radix. This convention will be adopted. Hence the pair of statements

      y ← (7, 24, 60, 60)
      y ⊥ x ← 7278; y

determines x unambiguously as the vector (0, 2, 1, 18).

it is also convenient, though not essential, to use selection operations on the left of a statement. Thus the statement

      u/b ← a

is understood to respecify only the selected components of b and to leave all others unchanged. It is therefore equivalent to the statement

      b ← \/b, u, a\.

Similarly,

      u/b ← u/a

is equivalent to

      b ← /b, u, a/.
 

1.20 Levels of structure

Vectors and matrices are arrays which exhibit one level and two levels of structure, respectively. Although in certain fields, such as tensor analysis, it is convenient to define more general arrays whose rank specifies the number of levels of structure (i.e., zero for a scalar, one for a vector of scalars, two for a vector of vectors (matrix), three for a vector of matrices, etc.), the notation will here be limited to the two levels provided by the matrix.^[g] The present section will, however, indicate methods for removing this limitation.

The only essential particularization to two levels occurs in the provision of single and double symbols (e.g. “/” and “//”, “⊥” and “”) for row and column operations, respectively, and in the use of superscripts and subscripts for denoting rows and columns, respectively. In applications requiring multiple levels, the former can be generalized by adjoining to the single symbol an index which specifies the coordinate (e.g. “/₁” and “/₂”, for row and for column compression, and, in general, “/_j”.) The latter can be generalized by using a vector index subscript possessing one component index for each coordinate.

The generalized notation can be made compatible with the present notation for vectors and matrices by adopting the name tensor and a symbol class (such as capital letters) for the general array of arbitrary rank.
 

1.21 Subroutines

Detail can be subordinated in a more general manner by the use of subroutines. The name of one program appearing as a single statement in a second program implies execution of the named program at that point; the named program is called a subroutine of the second program. If, for example, “Cos” is the name of a program which specifies z as the cosine of the angle between the vectors x and y, then Program 1.13a uses the program “Cos” as a subroutine to determine r as the cosine of the angle between the vectors p and q.

(a)		(b)		(c)

Program 1.13  Modes of subroutine reference

It is sometimes convenient to include the names of the arguments or results or both in the name of the subroutine as dummy variables. Thus if “Cos(x, y)” is the name of a subroutine which determines z as the cosine of the angle between x and y, then Program 1.13b uses Cos(x, y) as a subroutine to determine r as the cosine of the angle between p and q. Similarly, the program “z ← Cos(x, y)” can be used as in Program 1.13c to produce the same result.
 

1.22 Files

Many devices used for the storage of information impose certain restrictions upon its insertion or withdrawal. The items recorded on a magnetic tape, for example, may be read from the tape much more quickly in the order in which they appear physically on the tape than in some other prescribed order.

Certain storage devices are also self-indexing in the sense that the item selected in the next read from the device will be determined by the current state or position of the device. The next item read from a magnetic tape, for example, is determined by the position in which the tape was left by the last preceding read operation.

To allow the convenient description of algorithms constrained by the characteristics of storage devices, the following notation will be adopted. A file is a representation of a vector x arranged as follows:

      p₁, x₁, p₂, x₂, …, x_ν(x), p_{ν(x) + 1}, ∘, p_{ν(x) + 2}, ∘, …, p_ν(p).

The null elements denote “unused” portion of the file not employed in representing x. Each partition p_j determines a position (position j) in the file. If a file Φ is in position j, then a forward read, denoted by

      x, p ← ₀Φ,

specifies x by the component x_j, the auxiliary variable p by the succeeding partition p_j+1, and stops the file in the position j + 1.

The position of a file Φ will be denoted by π(Φ). Thus the statement j ← π(Φ) specifies j as the position of Φ, whereas π(Φ) ← j positions the file to j. In particular, π(Φ) ← 1 denotes the rewinding of the file and π(Φ) ← ν denotes winding, i.e. positioning to the extreme end of the file. Any file for which the general positioning operation π(Φ) ← j is to be avoided as impossible or inefficient is called a serial or serial-access file.

Each terminal partition (that is, p₁ and p_ν(p)) assumes a single fixed value denoted by λ. Each nonterminal partition p_j may assume one of several values denoted by λ₁, λ₂, …, λ_ν(λ), the partitions with larger indices normally demarking larger subgroups of components within the file. Thus if x were the row list of a matrix, the last component might be followed by the partition λ₃, the last component of each of the preceding rows by λ₂, and the remaining components by λ₁. The auxiliary variable p specified by the partition symbol during the read of a file is normally used to control a subsequent branch.

A file may be produced by a sequence of forward record statements:

      ₀Φ ← x_i, p       for i ε ⍳¹(ν(x)),

where p is the partition symbol recorded after the component x_i. As in reading, each forward record operation increments the position of the file by one. A file which is only recorded during a process is called an output file of the process; a file which is only read is called an input file.

Different files occurring in a process will be distinguished by righthand subscripts and superscripts, the latter being usually employed to denote major classes of files, such as input and output.

		Φi1     Input files for i ε ⍳1(m). Φ12   Output file. u   File Φi1 is exhausted if and only if ui = 1. b   Item to be recorded. Legend
Program 1.14   Program for Example 1.3

It is sometimes convenient to suppress explicit reference to the partition symbol read from a file by using a statement of the form

,

where the indicated branches depend on the value of the partition p_j+1 which terminates the read. Thus the left or the right branch is taken according to whether p_j+1 = λ₁ or p_j+1 = λ₂. Certain files (such as the IBM 7090 tape files) permit only such “immediate” branching and do not permit the partition symbol to be stored for use in later operations, as was done in Program 1.14.

In recording, the lowest level partition λ₁ may be elided. Thus statement 13 of Program 1.14 may be written as

      Φ₁² ← b.

A file may be read or recorded backward as well as forward. A backward read is denoted by

      x, p ← ₁Φ,

and if Φ is initially in position j + 1, then x = x _j, p = p _j, and the final position becomes j. Backward recording is defined analogously. The zero prescript may be omitted from the symbol ₀Φ for both forward reading and recording.

The conventions used for matrices can be applied in an obvious way to an array of files Φ _jⁱ. For example, the statement

      π(Φ ⁱ) ← ∊

denotes the rewinding of the row of files Φ _j ⁱ,  j ε ⍳¹(ν(Φ)); the statement

      π(Φ _j) ← ∊

denotes the rewinding of the column of files Φ _j ⁱ,  i ε ⍳¹(μ(Φ)); and the statement

      u/Φ ⁱ ← u/x, u/p

denotes the recording of the vector components x _j on the file Φ _j ⁱ together with partition p _j for all j such that u _j = 1.

As for vectors and matrices, j-origin indexing may be used and will apply to the indexing of the file positions and the partition vector λ as well as to the array indices. However, the prescripts (denoting direction of read and record) are independent of index origin. 0-origin indexing is used in the following example.