Linear Fractional Transformations
1.0 Introduction
A linear fractional transformation (LFT) is defined as a function of the form
where a,b,c,d are complex constants. Every LFT defines a one-to-one mapping of the extended complex plane (C È ) onto itself. Two LFTs f and g are similar iff there exists a purely linear transformation L(z) = a z + b where a and b are complex constants such that
L ( g(z) ) = f ( L(z) )
for every complex z. (The condition is reciprocal, because if L is a linear function, then so is the inverse of L.) This condition implies a mapping between the iterates of f and the iterates of g as shown schematically in Figure 1. In essence, letting zk denote the iterates of f for any given initial value z0, and letting wk denote the iterates of g with the corresponding initial value w0 = L(z0), it follows that if f and g are similar, then wk = L(zk) for all k. In other words, the iterates of f can be mapped to the iterates of g by the linear function L, and since a linear transformation of the complex plane consists of (at most) a simple translation, a rotation about the origin, and a uniform scale change, it follows that the configuration of points L(zk) is geometrically similar to the configuration of points zk.
To derive necessary and sufficient conditions for similarity, suppose the two LFTs
are similar. Then by definition there exists a linear function L(z) = a z + b such that L(f(z)) = g(L(z)), so we have
Substituting for f(z) and L(z) into this equation gives
Clearing the fractions and equating the coefficients of like powers of z gives the following three conditions
If c,C,a 0 the first condition can be divided by a and solved for b to give
Substituting this into the second condition and solving for a gives
(assuming ad - bc 0). Substituting the expression for b into the third condition gives
Dividing by AD-BC (assumed not zero) and noting that (ad-bc)/(AD-BC) = (c/Ca)2 we have
Since we assume c 0 we can divide by c2 and solve for a
Equating this with the previous expression for a, we arrive at a necessary and sufficient condition for the LFTs f and g to be similar:
This shows that for any given LFT (az+b)/(cz+d), the similarity class is determined solely by the parameter (a+d)2/(ad-bc). Hereafter we will refer to this as the similarity parameter, and denote it by s. Thus, for any LFT (az+b)/cz+d) we define
Two LFTs f and g are said to be conjugate if there exists an LFT h such that h(f(z)) = g(h(z)) for all z. This is identical to the definition of similarity, except that similarity requires h to be purely linear. Thus, similarity would seem to be a more restrictive condition than conjugacy. However, the necessary and sufficient condition for f and g to be conjugate is exactly the same as the condition for similarity (cf. Complex Functions, p 32, Jones and Singerman, 1987). The only strength gained by allowing h to be an LFT instead of a linear function is in the "singular" cases when the coefficients of the linear coupling function L are not well defined, such as when c, C, (a+d), or (A+D) are equal to 0. However, when (a+d) = 0 the only conjugate LFTs are those with A+D = 0. Thus, returning to the previous conditions and inserting (a+d) = (A+D) = 0, we find that in this case it is necessary and sufficient for a to be given by
Thus, the only case when conjugacy can exist without a well-defined linear similarity correspondence relationship between the two LFTs is if c or C equal zero. The first of the three conditions above implies that is either c or C is zero, then the other is also zero, unless a is zero, which would imply a degenerate linear function.) In these cases, by the inclusion of the "point at infinity" (which is the same expedient used to ensure closure of the LFT iterates) we can include among the linear similarity relations those with infinite coefficients (and, conversely, zero coefficients).
2.0 Closed Form Expressions For the nth Iterate
To find a closed-form expression for the nth iterate zn of the linear fractional transformation f(z) = (az+b)/(cz+d), it is most convenient to consider a similar function, g, having the sequence of iterates w0, w1, w2, ... where wk is related to zk by a linear function
for some complex constants a and b. Our objective is to find a linear transformation such that a closed-form expression for wn (the nth iterate of g) is easy to determine. In general, the original LFT can be expressed in terms of w as follows
Solving for wk+1 gives
where
Notice that if c is not equal to zero, we cannot force C to equal zero (except by putting a = 0, which is singular). This rules out any chance of finding coefficients a,b for which wk+1 = Kwk. However, there are several other "nice" LFT forms for which a closed-form solution can easily be found. One such, which we will call the "bi-polar" form, is
Every LFT (az+b)/(cz+d) with two distinct fixed points is similar to an LFT of this special form. The coefficients a and b of the linear similarity function are determined by setting B = 0, which implies that
We then impose the condition (C+D)/A = 1, which implies
Substituting the previous expression for b and solving for a gives
This is determined by mapping the two fixed points to the points 0 and 1 on the complex plane. We will refer to this as the bi-polar form of the given LFT similarity class. The value of K here is given by
Notice that this implies
The "K form" has fixed points at 0 and 1, and it can be shown by induction that zn has the convenient closed-form expression
In this case the periodicity requirement is simply 
. It's interesting that to convert a purely real LFT to this "bi-polar K" form, the real axis is mapped to the line 0.5 + m i, which figures in the Riemann Hypothesis.
The real and imaginary components of zn = xn + iyn can be expressed in closed form in terms of the components of K and z0. If we set
then the components of zn are given by
where f = nq . This shows that the action of the LFT on the complex plane is entirely dependent on the magnitude and phase angle of the constant K, which, as we saw previously, is given by
If a,b,c,d are all real, then s is real, in which case either K is real (s>4 or s<0) or K is complex (0<s<4) with a magnitude (norm) of 1. However, if a,b,c,d are allowed to be complex, then K can be complex with a magnitude other than 1.
If K is real, then we can set R = K and q = 0, so f equals zero for all n, and the equations for xn and yn reduce to
If (a+d) = 0 then K = -1, in which case the only conjugate LFTs are those with s = 0.The preceding expressions for the nth iterate of a linear fractional transformation assume the LFT has two distinct fixed points. More generally, given any linear fractional recurrence relation
we can derive a closed-form expression for the nth iterate zn in terms of n and z0. These expressions are summarized in Table 1 for the various cases. Notice that cases 2 and 3 are really linear transformations, since c = 0. Case 4 corresponds to the case when the two fixed points of the LFT are co-incident. In this "parabolic" case, if a + d = 0 then the LFT reduces to Case 1 with ad-bc = 0. Case 5 is the general case with two distinct fixed points. In this case, if a + d = 0 then s = 0 and K = -1.
It's also interesting to note that the general expression for Case 5 can be written in the form
so if we define the LFT
we have
Setting n = 1 and noting that f(z0) = z1, we have
which shows that f(z) is conjugate to the simple function Kz. It's interesting to note that a + b is the "conjugate" of b, and so h(z) can be expressed as
where
Therefore, if c = 0, then either h(z) = 0 or h(z) is undefined.
3.0 General Periodicity Condition
It can be shown that the sequence of iterates zk of an LFT is cyclical with a period of m (meaning that zk+m = zk for every integer n) if and only if
for some integer k. The "periodic" values of s can also be expressed algebraically in the form
It's interesting that each -sm is a root of the polynomial
This gives the roots of polynomials whose coefficients are diagonal elements of Pascal's triangle
For example, the five roots of the quintic x5 + 9x4 + 28x3 + 35x2 + 15x + 1 are given by
and the three roots of the cubic x3 + 6x2 + 10 + 4 are given by
The factorizations of the first 24 "periodic s polynomials" are presented in Table 2. If Fk(x) denotes the polynomial with roots -sk, then Fm(x) divides Fn(x) if and only if m divides n. This follows from the fact that if an LFT is cyclical with a period of m, and if m divides n, then the LFT also is has a (not fundamental) period of n.Although the roots of each Fm(x) are easily expressed in trigonometric form, it's interesting to note the following algebraic solutions for m = 16, 20, and 24. These are found by solving the quartic factor of Fm(x) in each case, which gives the four values of s corresponding to the LFTs with a fundamental period of p in each case.
Since the condition for having period m is entirely a function of s, and two LFTs are similar if they have the same s, if follows that the number of dissimilar LFT groups of order m is equal to the number of distinct values 4cos2(kp /m). This is clearly half the number of integers less than and co-prime to m, so the number is f (m)/2, half the Euler totient function. If an LFT has a periodic of m, then it is said to generate a (cyclic) group order m.
4.0 The s Form
Given any linear fractional transformation f(z) = (az+b)/(cz+d) with ad bc and (a+d),c 0, we can solve the similarity parameter equation
for b to give
It follows that the function
is similar to f(z) for any choice of parameters a, b, and c (provided c and a+d do not equal zero). In particular, setting d=0 and a=c gives the simple form
This implies that the iterates of g(z) are given as simple continued fractions. For example, z3 can be expressed as a function of z0 as follows
5.0 Self-Similar Iterations
Given any linear fractional transformation f(z) = (az+b)/(cz+d), the first iterate of this function is
which has the similarity parameter
Therefore, the sequence of similarity parameters of the iterates of a linear fractional transformation satisfy the non-linear recurrence
Setting sk+1 = sk and solving the resulting quadratic shows that all the iterates of f are similar to each other if and only if s = 1 or 4. The recurrence gives a chaotic sequence for a range of initial values, similar to the logistic equation.
6.0 The l Form
One of the most interesting special forms of linear fractional transformations is
Every (non-degenerate) LFT is similar to an LFT of this special form. In fact, it is similar to exactly two LFTs of this form, because this special LFT is similar to the LFT given by replacing l with 1/l. This implies the important fact that every periodic l is either purely real or it is complex with a magnitude of 1 (i.e., on the unit circle). Figure 2 shows the range of periodic l values in the complex plane.
The periodicity condition for this form is that zn+m = zn if and only if l has one of the values
where k is an integer. These values can also be expressed in terms of the corresponding similarity parameters as
which implies
We saw in the previous section that iterations of f have the same similarity parameter s if and only if s equals 1 or 4. These values of s gives the following values for the corresponding l forms
Note that these are the extreme values of periodic l on the imaginary axis and the real axis, respectively (excluding -1).
The values of l that give periodic LFT iterations are the roots of a special set of polynomials whose coefficients are members of a generalized set of binomial coefficients. Each member of the generalized family of coefficient sets is denoted by a three-index symbol, defined as follows
Based on this definition, the following properties can be established:
Symmetry:
Unit Plane:
Binomial Plane:
Recurrence Relation:
Column Relations:
It is often more convenient to index the generalized coefficients in a manner similar to the indexing of the binomial coefficients. We define the generalized form as
with the understanding that if no J subscript is specified, the value J=1 is implied (giving the normal binomial coefficients). In these terms we can establish the following recurrence relating the sums of successive rows of the coefficients:
For J=1 this obviously gives the sums of the rows of binomial coefficients as powers of 2. The sum of the general row with alternating signs is given by
(with the stipulation that the sum equals 1 for the case J=1, m=0). The generalized coefficients with J = -1 are as follows
The roots of the polynomials with coefficients from a row of this table are precisely the values of l for which the LFT is periodic. Specifically, letting lq denote the values of l for which l(1+z)/(1-z) has period q, we have
Since the coefficients are symmetrical, we know that if l is a root, then so is 1/l. The general form of the roots of these polynomials was given earlier in terms of the cosine function. However, several of these can be expressed purely algebraically. A list of these is presented in Table 3.
7.0 The Sum and Difference Form
Another interesting special form is
which has the convenient closed form expression
The periodicity condition for this form is
8.0 The Complement Form
Another interesting form of linear fractional transformation is
The values of a for which zn+m = zn are 4sin2(kp/2m), k = 1, 2,...
9.0 The Diagonal Form
Another interesting form is
This LFT is similar to any other LFT with a s such that
The values of G for which the LFT has a finite period m are
The values of -Gm2 are precisely the roots of the polynomial whose coefficients are every second value in the mth row of Pascal's triangle. For example, consider the polynomial with coefficients taken from the 7th row
The three roots of the cubic x3 + 21x2 + 35x +7 are -tan2(kp /7) with k=1,2,3. If, on the other hand, we took every other coefficient from the 7th row beginning with the second column, we know that the three roots of the cubic 7x3 + 35x2 + 21x + 1 are simply the inverses of the roots of the former polynomial, i.e., -1/tan2(kp/7) with k = 1, 2, 3.
A convenient way of expressing these roots is to make use of the trigonometric identity
On this basis, we can say that the roots of the two polynomials with coefficients from the 7th row of Pascal's triangle are given by
Notice that we now have 2m instead of m in the denominator of the tangent. This same formulation works for even numbered rows as well. For example, the roots of the two polynomials taken from the 8th row are
10.0 Density of Real Iterates
Given the linear fractional recurrence
we can derive a closed-form expression for zn that is particularly useful when the sequence is purely real. Beginning with the closed-form solution presented in Table 1 for the general case 5, we can substitute the trigonometric for the exponential form and arrive at the expression
where we have defined the parameters
and
If we set z0 = m , then the expression for zn reduces to
The function tan(x) is periodic modulo p , and assuming q /p is irrational we can surmise that the values of nq (mod p ) for n = 0,1,2,...k... will approach an even distribution on the interval [0 , p ] for sufficiently large k. Therefore, the asymptotic density of the iterates at any value zq is proportional to the slope, i.e., derivative, of n with respect to z, since that is proportional to the number of n's that fall within a given interval Dz. The preceding equation gives
so the derivative of n with respect to z is
The asymptotic density of the iterates is proportional to this derivative, so we need only determine the appropriate scale factor to give the absolute density. The scale factor must be such that the integral of the density from z = - to + equals 1. In terms of the variable y = (z-m )/e , we know that
and since invtan( ) = p /2, it follows that
Therefore, the scale factor on 1/(1 + y2) must be 1/(e p ), so the asymptotic density of iterates is given by
This is called the Cauchy distribution in probability theory. It's easy to show that half of the iterates will fall within the range m + e , and 2/3 of the iterates will fall within the range m 2e .