Arnold’s Cat MapGabriel PetersonMath 45 – Linear AlgebraFall 1997AbstractThe purpose of this paper is to discuss and explore the properties of Arnold’s catmap, a chaotic mapping of the pixels of an image. By way of this, the introductoryprinciples of the exciting new science of chaos are addressed.Introduction: ChaosBefore undertaking a discussion of Arnold’s cat map, a working understanding of chaos mustfirst be established. We enter into this discussion already in the possession of some intuitive senseregarding chaos, some nebulous sense that it involves disorder, randomness, disorganization,entropy... Who among us has not observed that, over time, systems tend to become disorganized orchaotic. Does a bedroom not evolve from an initial state of order to disorder with indifferentcleaning? A jar containing marbles of two different colors, initially group by color, promptlydistributes the marbles randomly when vigorously shaken. Indeed, the inviolable and sacrosanctSecond Law of Thermodynamics tells as much: the entropy, the measure of disorder, of theUniverse increases over time.However, the chaos that concerns this discussion, while inextricably tied to the above, is that ofthe fledgling science of chaos. This science has leapt into the public consciousness in recent yearswith popularization in motion pictures, such as Jurassic Park, and books, such as James Gleick’sChaos: Making a New Science. Chaos evolved from the work of Edward Lorenz, a meteorologistat Massachusetts Institute of Technology. In 1960, equipped with a newly purchased electroniccomputer, he created a simulation of the weather using a simple system of equations; the machinehad neither the computational power nor the memory for a more sophisticated model. Initialconditions were entered, and the weather in this electronic world would unfold, its binary denizensenduring downpours, blizzards, droughts, and other meteorological adversities. Wanting to examinea particular run in greater detail, Lorenz reenter its initial conditions. However, the data from thefirst run had been entered to six decimal places of accuracy, whereas the second only to three. Hisdiscovery was startling: comparing the second run to the first – which should have been virtuallyidentical – he found that the second rapidly diverged from the first. Surely, the small errorintroduced by truncating the initial conditions to three decimal places could not have induced thistroubling behavior. But it did. Complex systems – even a simplified complex system such asLorenz’s – are extremely sensitive to initial conditions, so-called sensitivity dependence upon initialconditions. Small errors rapidly propagate through such systems. Lorenz called this the ButterflyEffect: the beating of a butterfly’s wings in China could cause a blizzard in Chicago.It was not until the publishing of the paper mischievously titled ”Period Three Implies Chaos” in1975 by James Yorke and Tien-Yien Li that the word chaos was coined mathematically to give theseideas a name. Broadly defined, chaos pertains to those mathematical or physical phenomena that are1apparently random yet possess underlying order. As James Gleick commented,Over the last decade, physicists, biologists, astronomers, and economists havecreated a new way of understanding the growth of complexity in nature. This newscience, called chaos, offers a way if seeing order and pattern where formerly onlythe random, erratic, the unpredictable – in short, the chaotic – had been observed(Chaos and Fractals, vii).In a now famous series of debates with Niels Bohr concerning quantum physics, Albert Einstienproclaimed ”God does not play dice with the Universe,” the Universe is not governed by chance.However, chaos implies, in the words of Joseph Ford of the Georgia Institute of Technology,God does play dice with the Universe. But they are loaded dice. And the mainobjective of physics now is to find out by what rules were they loaded and how canwe use them for our own end (Chaos, 314).Introduction:ImagesAs matter is composed of discrete units called atoms (which are themselves composed ofdiscrete units), so too images are composed of discrete units called pixels. A pixel is a small squarerepresenting some color value, which when taken together form the mosaic that is the image. Theimage is a mxnmatrix, where m represents the number of rows of pixels and n the number ofcolumns of pixels, with each entry in the matrix being a numeric value that represents a given color.For example, consider the 175 x 175 image of a caffeine molecule below.20 40 60 80 100 120 140 16020406080100120140160Let the image be the matrix X, and we can examine selected entries in X.2X ã217 217 217 217 ... 217 217 217 217251 251 251 251 ... 251 251 251 251251 251 251 251 ... 251 251 251 251251 251 251 251 ... 251 251 251 251...........................251 251 251 251 ... 251 251 251 251251 251 251 251 ... 251 251 251 251251 251 251 251 ... 251 251 251 251217 217 217 217 ... 217 217 217 217The numeric entries merely represent some color value.Arnold’s Cat MapThe particular instance of chaos we will explore in this discussion is the chaotic mapping calledArnold’s cat map in recognition of Russian mathematician Vladimir I. Arnold, who discovered itusing an image of a cat. It is a simple and elegant demonstration and illustration of some of theprinciples of chaos – namely, underlying order to an apparently random evolution of a system. Animage (not necessarily a cat) is hit with a transformation that apparently randomizes the originalorganization of its pixels. However, if iterated enough times, as though by magic, the original imagereappears.If we let X ãxybe a nxnmatrix of some image, Arnold’s cat map is the transformationáxyvx ò yx ò 2ymodnwhere mod is the modulo of thex ò yx ò 2yand n . For example, 3.142mod1 ã .142 or150mod100 ã 50 or123154mod100 ã2354. Since the signs of both arguments are thesame sign in this exercise, the modulo will simply be the remainder of the long division ofx ò yx ò 2yand n.3To better understand the mechanism of the transformation á, let us decompose it into itselemental pieces.1. Shear in the x-diection by a factor of 1.xyvx ò yy2. Shear in the y-direction by a factor of 1.xyvxx ò y3. Evaluate the modulo.xyvxymodnIncluded below is a visual aide illustrating these steps. The first step shows the shearing in the x-and y-directions, followed by evaluation of the modulo and