J Labs

A J Introduction

(1 of 95) J - Introduction

J is executable mathematical notation.

The fourteen chapters of this lab illustrate its use in experimenting with mathematical ideas in a variety of topics.

To clarify ideas, enter your own experiments (which you may do at any point).

(2 of 95) Functions

There is a rich set of primitives.

(3 of 95) Arrays

Functions apply to arrays.

(4 of 95) Arrays (ctd)

Some functions make arrays.

i.n is a list of the first n integers.

s $ v makes an array of shape s using the elements v

(5 of 95) Assignment

An array or function can be assigned a name by using =: (the copula).

(6 of 95) Monadic or Dyadic

A function can be monadic or dyadic, depending on whether it applies to one argument (on the right) or to two (on the left and right).

(7 of 95) More Primitives

The primitive functions include + - * % as well as ^ (power), ^. (log), > (greater than), >. (greater-of, or maximum), +. (or/GCD), *. (and/LCM), | (residue or modulo), etc.

All of these can be monadic or dyadic, and apply to arrays.

(8 of 95) Insert

Adverbs modify verbs (functions) to produce new verbs.

For example, the adverb / inserts its verb argument between the items of its argument.

Thus, +/ is summation and */ is product. These are the "big sigma" and "big pi" of conventional notation. Moreover, / can be applied to any function: >./ is maximum, <./ is minimum, +./ is or or GCD, *./ is and or LCM, etc.

(9 of 95) Table

If f is a verb (function), then f/ is a verb, and, like any other verb, it can be monadic or dyadic. The monadic meaning is "insert". The dyadic meaning is "table", that is, a function table.

Function tables are a good way to organize systematic experimentation on unfamiliar functions.

(10 of 95) Table (ctd)

The Hilbert matrix is a simple function on the addition table. As shown below, its pattern is more apparent in the extended precision (rational) domain.

Although Hilbert matrices are notoriously unstable under inversion, the matrix inverse (%.) gives an exact integer result (as shown below):

(11 of 95) Table (ctd)

The "triangle" of Pascal is an example of a function table, based on the binomial coefficient function ! .

An advantage of treating it as a table rather than as a triangle is that matrix operations (such as matrix inverse) can be applied to it.

(12 of 95) Prefix

Prefix is another adverb. f\ applies f to the prefixes of the argument.

The monad < (box) is helpful in understanding prefix.

(13 of 95) Permutations

The dyadic function x{y indexes y by x If p is a permutation p, then p{y permutes y by p.

(14 of 95) Permutations (ctd)

{/ (m,#p) $ p inserts { between m copies of the permutation, and computes the m-th power of p.

The corresponding prefixes, {/\ (m,#p) $ p, are the successive powers of p.

(15 of 95) Permutations (ctd)

C. p computes the cycles of the permutation p. The Least Common Multiple (*./) of the cycle lengths is the order of the subgroup generated by p.

(16 of 95) Patterns: color - Addition Table

The pattern seen in an addition table can be emphasized by producing a window in which equal values in the table are assigned the same color.

(17 of 95) Subtraction Table

(18 of 95) Multiplication Table

When applied to a list of positive and negative integers, the multiplication table provides an interesting pattern.

(19 of 95) Multiplication Table (ctd)

The monad * is called the "signum" or "sign" function. When applied to a multiplication table, it shows the pattern of positive and negative results produced by multiplication.

(20 of 95) Remainder Table

3 | 5 gives the "remainder" or "residue" on dividing 3 into 5. Study the following remainder table and (before advancing to the next panel), try to predict the appearance of coloring the 2-residue of the addition table given by 2 | (i.8) +/ (i.8).

(21 of 95) Checkerboard

(22 of 95) Fractals

Residues of binomial coefficient tables provide examples of fractals (which "replicate according to their own pattern").

This is illustrated in this and the next three panels.

(23 of 95) Fractals (ctd)

(24 of 95) Fractals (ctd)

(25 of 95) Fractals (ctd)

(26 of 95) Fractals (ctd)

This is the end of this chapter. To continue with the next chapter, advance as usual. But to select any other chapter, click on Chapters under the Studio menu.

(27 of 95) Patterns: Plots - Simple plot

The square function (*:) applied to a list x may be plotted against its argument as follows:

(28 of 95) Stick and Line Plot

A plot that shows vertical lines to the argument axis may be produced similarly as follows.

(29 of 95) Stick and Line Plot (ctd)

Combined plots of two or more functions are produced as follows.

(30 of 95) Stick and Line Plot (ctd)

The sine and cosine functions may be plotted as follows.

(31 of 95) Patterns: Variation - Introduction

More general patterns may be observed by comparing successive items produced in applying a function to a systematic list argument.

Items may be compared in various ways, notably by subtraction and by division.

(32 of 95) Differences and ratios

We now define functions called dif and rat to perform these comparisons.

(33 of 95) Differences and ratios (ctd)

f ^: n is "f to the power n", that is, n applications of the function f.

(34 of 95) Series - Introduction

In the list a=: 1 3 5 7 9 11, the expression 2{a selects the item with the value 5, and 2 is said to be its "index".

The function f=: >:@+: gives each element of a as a function of its index, and is said to define the "series" a. This is true only for arguments in the list i.#a, but if we assume (or assert) that f applies to every index, then it is said to define an "infinite" series.

(35 of 95) Determining a defining function

Using the list b=: 0 _2 _4 0 16 50 108 we can define a function for the corresponding series. We will use repeated application of the difference function dif=:}.-}: to obtain the coefficients for the falling factorial polynomial ffp=:p.!._1. These matters will be discussed more fully in a subsequent chapter on polynomials.

(36 of 95) Determining a defining function (ctd)

Try further examples, as illustrated below.

(37 of 95) Polynomials - Introduction

The expression 2*x^3 is a monomial (single name), and a sum of monomials is a polynomial.

The expression c p. x is a polynomial with "coefficients" c.

(38 of 95) Polynomials - Introduction (ctd)

Polynomials are important for a number of reasons:

1. A sum of polynomials is a polynomial
2. A product of polynomials is a polynomial
3. The derivative of a polynomial is a polynomial
4. The integral of a polynomial is a polynomial
5. Polynomials serve to approximate many functions, such as sine, cosine, and exponential.

(39 of 95) Sums and products

Since (e,0) p. x is equivalent to e p. x, coefficients that differ in number of items can be added as illustrated below.

Moreover, the coefficients of a product can be obtained from the multiplication table by using the adverb /. to sum its diagonals.

(40 of 95) Derivatives and Integrals

The derivative of a polynomial is obtained by multiplying each monomial by its exponent, and reducing the exponent by 1.

Equivalently, the coefficients of the derivative of c p. x are obtained by multiplying c by the exponents i.#c, and dropping the first item.

(41 of 95) Derivatives and Integrals (ctd)

Conversely, the coefficients of the integral of c p. x are obtained by dividing c by 1+i.#c, and appending a leading constant of integration (for which we will use 20).

(42 of 95) Derivatives and Integrals (ctd)

We now define functions DER and INT for the derivative and integration of coefficients.

(43 of 95) Derivatives and Integrals (ctd)

If ce is a list of coefficients that approximates the exponential, then DER ce is approximately equal to ce.

(44 of 95) Falling Factorial

The falling factorial function is related to the power function, obtained as a "variant" of it by using ^ !. _1.

The falling factorial polynomial ffp=: p. !. _1 (used in the chapter on series) is a polynomial based on the falling factorial rather than the power.

(45 of 95) Taylor Series - Introduction

A series that can be used as coefficients of a polynomial to approximate a function f is called the Taylor series for f. Taylor series are provided by the adverb t. as illustrated below.

(46 of 95) Extended Precision and Rationals

The expression ! x: 20 gives factorial 20 to complete precision. Moreover, 2 % x:3 gives the result of dividing 2 by 3 in rational form.

(47 of 95) Extended Precision and Rationals (ctd)

(48 of 95) Joint display

A joint display of Taylor series.

(49 of 95) Binomial Coefficients - Introduction

Matrix products and inverses of binomial coefficient tables give interesting results.

(50 of 95) Matrix Products of bct

(51 of 95) Identities

Since the matrix products of abc are sums of products of binomial coefficients, any independent expression that gives these "powers" of bct yields a host of identities concerning binomial coefficients.

(52 of 95) Identities (ctd)

We can now use a subtraction table as an exponent to give a result equal to bct4 (the fourth "power" of bct).

(53 of 95) Geometry - Tables of coordinates

A 4-by-3 table can be used to represent coordinates of the 4 vertices of a tetrahedron in 3-space, and an n-by-2 table represents the n vertices of a polygon.

(54 of 95) Area of triangle

Analysis of this use of the determinant for triangles (and tetrahedrons) may be found in Klein "Elementary Mathematics From an Advanced Viewpoint".

Because areas of triangles are signed, the area of any polygon can be obtained by adding lines to triangulate it, and summing the areas.

(55 of 95) Regular pentagon

A regular pentagon is obtained by appying the cos and sin to angles at intervals of 2r5p1 (two-fifths of pi), and displayed by applying plot to the boxed x and y coordinates.

(56 of 95) Regular pentagon (ctd)

The missing line from the last vertex to the first can be provided as follows.

(57 of 95) Improper polygon

An interchange of indices 1 and 2 illustrates the possibility of an"improper polygon" whose sides cross.

(58 of 95) Triangulation

The pentagon may be triangulated as follows:

(59 of 95) Area of pentagon

These triangulated components of the pentagon can be selected and boxed, and their areas can be determined, as follows:

(60 of 95) Area of concave pentagon

Although the function area gives signed results according to the clockwise or counter-clockwise order of the vertices, these areas are all of the same sign.

This occurs because pent is a convex polygon, and the significance of signed areas is not apparent. We will make it so by using a concave polygon, obtained by multiplying the second vertex of pent by zero.

(61 of 95) Area of concave pentagon (ctd)

The boxed coordinates of the triangular components of the concave pentagon are obtained as shown below. Their areas are not all of the same sign, but sum to give its total area.

(62 of 95) Displacement and side length

The displacement from one vertex to the next can be obtained by rotating the table of vertices up by one place, and subtracting from it the original table.

(63 of 95) Displacement and side length (ctd)

The lengths of the sides can then be obtained from these displacements as the square root of the sum of the squares.

(64 of 95) Heron's formula

Heron's formula for the (unsigned) area of a triangle is the square root of the product of the semiperimeter with the semiperimeter less each of the sides.

(65 of 95) Slope and Rate of Change - Introduction

The rate of change of a function is an important attribute: for example, the rate of change of the sine is the cosine, the rate of change of the exponential is itself, and the rate of change of the nth power is n times the (n-1)th power.

Although the instantaneous rate of change at a point may be difficult to determine, the average rate of change over a non-zero interval i is straightforward.

(66 of 95) Slope

We use the term "slope" for the average rate of change, because the graph of a function at intervals of i exhibits the average rate of change as the slopes of the lines connecting successive points.

(67 of 95) Slope (ctd)

For a small interval the average slope approaches the slope AT each point, a result that is called the derivative of the function.

(68 of 95) Slope (ctd)

The derivative (the slope AT a point) should be given by a zero interval, but this is the meaningless division of a zero rise by a zero interval.

However, the case of a power function can be analyzed to give a simple meaningful result. For example, the cube function applied to x+i gives

```(x*x*x)+(3*x*x*i)+(3*x*i*i)+(i*i*i)```

```Sutraction of the cube of x gives:```

```(3*x*x*i)+(3*x*i*i)+(i*i*i)```

```which can be divided by i to yield:```

```(3*x*x)+(3*x*i)+(i*i)```

```Since i is zero, the last two terms can be dropped to yield```
```3*x*x (that is, three x squared, or formally, 3:*]*]) for the slope with zero interval.```

(69 of 95) Slope (ctd)

Similar analysis for other powers gives n*x^(n-1) as the derivative of x^n Moreover, the derivative of a multiple of a function is the same multiple of the derivative, and the derivative of a sum of functions is the sum of their derivatives.

These observations extend the analysis to polynomials, with the simple consequence that the derivative of the polynomial c&p. is the polynomial d&p., where d=:}. c*i.#c.

(70 of 95) Slope (ctd)

The foregoing shows that the essential notion of the calculus (that is, the derivative) can be treated without resort to the general analysis of limits, provided that attention is restricted to polynomials or to rational functions obtained as the ratio of polynomials.

Since polynomials and rationals can be used to approximate all the functions of interest in an introductory course in calculus, this is not a serious restriction. This approach to the calculus will be pursued in the next chapter.

(71 of 95) Calculus - Introduction

We will restrict attention to polynomials, and will use the results developed in the chapter on Slopes.

(72 of 95) Calculus - Introduction (ctd)

The operator d. gives successive derivatives of various orders (using d.1 and d.2 and d.3, etc.), as well as integrals (using d._1 d._2 etc.).

(73 of 95) Calculus - Introduction (ctd)

The Taylor adverb t. gives the coefficients of derivatives and integrals.

From the results shown below it is clear that d._1 uses a zero constant of integration. The effect of any other can be obtained by adding it.

(74 of 95) Theorems and proofs - Theorems

A theorem is an assertion that one expression L,the left limb, is equivalent to another R, and may be expressed as the function T=. L -: R . A theorem may also be called a tautology, a function that yields 1 (true) for any argument. For example:

(75 of 95) Theorems and proofs - Theorems (ctd)

We can also assign the name n to the right argument function ] to allow a function such as R1 to be written more readably for a beginner. Thus:

(76 of 95) Proofs

A proof is a sequence of equivalent expressions that lead in justifiable steps from a left limb to a right. We will write one expression below another to assert that it is equivalent to the one above it, possibly annotating it with the justification to provide a formal proof:

```L NB. Theorem 1```

```+/@i. NB. Definition of L```

(77 of 95) Proofs (ctd)

The foregoing proof can be illuminated by entering each expression followed by an argument, and observing that each gives the same result. Any mis-step in a proof will likely show an anomolous result.

An expression can be conveniently entered by moving the cursor up to it, pressing enter to bring it to the input area, modifying it by inserting the argument, and then pressing enter. Moreover, partial expressions may be entered to observe their results. Thus:

(78 of 95) Proofs (ctd)

How would you express the second step (+/@|.@i.6) in conventional notation (without English or arm-waving). Remember that Sigma from 5 to 0 is a sum over an empty list)

Reproduce other of the proofs in pure conventional notation.

(79 of 95) Proofs (ctd)

The following is a similar proof that the sum of the first n odd integers equals the square of n:

```(odds=: 1: + 2: \* i.) NB. First odd integers```

```+/@(1: + 2: \* i.) NB. Sum of odds```

```(n + +/@(2: \* i.)) NB. Sum of n ones is n```

```(n + 2: \* +/@i.) NB. Sum of twice is twice sum```

```(n + 2: \* (n \* n - 1:) % 2:) NB. Result of preceding theorem```

```(n + n \* n - 1:) NB. Simple algebra```

```(n \* n) NB. Simple algebra```

```*: NB. Definition of square```

(80 of 95) Induction

An inductive proof is based (explicitly or implicitly) on a recursive definition of a function. Recursive definition is treated in the next chapter.

(81 of 95) Selcting topics

This is the end of this chapter. To continue with the next chapter, advance as usual. But to select any other chapter, click on Chapters under the Studio menu.

(82 of 95) Recursion - Introduction

If a function recurs in the expression that defines it, the function is said to be recursively defined. Such a definition must be supplemented by a definition for some specific argument, using an expression that does not make use of the function being defined.

For example, the factorial of the argument j may be defined by j * f j-1 (or more formally by ] * f@<:), supplemented by the definition 1: (the constant function 1) for the case j=: 0. Thus:

(83 of 95) Recursion - Introduction (ctd)

In the foregoing definition, the signum function * yields 0 if the argument is zero, and 1 if it is greater than zero.

Consequently, the agenda @. chooses the last element of the gerund 1:`(]*f@<:) each time until the argument (repeatedly decremented by <:) becomes zero, in which case it chooses the constant function 1:, thus terminating the process.

Alternatively, the imposition of zero rank could be incorporated in the recursive definition:

(84 of 95) Recursion - Introduction (ctd)

The reference to f within the definition works only because the name f is assigned to the function defined; we may instead use the symbol $: for self-reference to define an anonymous function to which any name may be assigned:

(85 of 95) Quicksort

Quicksort is an interesting example of the use of recursion: the basic procedure is the segregation of the items of an argument list according to whether they are less than the leading item, equal to it, or greater than it.

This procedure is applied recursively to the segregated lists, repeating as long as the argument has more than one item.

(86 of 95) Quicksort (ctd)

Details of the action of the recursive definition of quicksort can be analyzed as illustrated below.

(87 of 95) Quicksort (ctd)

Continuation may lead to empty boxes.

(88 of 95) Permutations and Anagrams - Introduction

A permutation (re-ordering) of the letters of a word is called an anagram, and may be performed by the anagram function denoted by A. -- an anagram may or may not be an English word.

(89 of 95) Permutations and Anagrams - Introduction (ctd)

The list to be permuted may be numbers, and the result may be used to index any list of the correct number of items.

(90 of 95) Permutations and Anagrams - Introduction (ctd)

The right argument may be any list of items, such as a boxed list of words.

(91 of 95) Permutations and Anagrams - Introduction (ctd)

This indexed list can also be produced by direct use of A. and the two equivalent results will be displayed side-by-side (separated by a boxed empty list provided by a:).