Algebra

Three shears, and no pixel lost

Every rotation of the plane is three shears, one after another. That is a fact about two-by-two matrices, and on a screen it becomes a fact about pixels: a shear slides whole rows along themselves, so rounding it to whole pixels still moves every pixel to a place of its own. Rotating a picture by rounding the rotation directly loses up to a fifth of its pixels — except at the angles of the 3-4-5, 5-12-13 and 7-24-25 triangles, and of one infinite family of right triangles after them.
18 min read 6 figures The same thing twiceSmall cases lie

Worth reading first: A matrix is a picture of what happens to the grid · What a map throws away.

A matrix is a picture of what happens to the grid read a two-by-two matrix as an instruction for redrawing the plane’s grid, and two of the instructions it drew are opposites in character. A rotation turns the grid rigidly, every square staying a square. A shear slides the grid’s horizontal lines along themselves, each by an amount proportional to its height, so that squares lean into parallelograms of the same area while every horizontal line stays exactly where it was. One looks like the most natural motion there is, the other like a deformation.

They are not as different as they look. Every rotation is a product of three shears: a horizontal one, a vertical one, and the first horizontal one again. That is a two-line calculation with matrices, known for a long time and rediscovered by people writing graphics software in the 1980s, because it turns out to matter enormously on a screen. A screen is a grid of pixels, and a rotation of a picture has to send each pixel to a pixel. Rounding the rotated positions loses pixels; rounding the shears does not. This essay draws why, measures how much is lost the other way, and finds that the angles at which rounding a rotation loses nothing are the angles of one family of Pythagorean triangles.

The factorisation

A rotation by 30° as three shears. angle 30: shears -0.267949, 0.500000, -0.267949; product equals rotation.
Fig. 1 A square with a flag in it sheared across by −0.268, up by 0.500, and across by −0.268 again. The three steps together are exactly the rotation by 30°.

A horizontal shear by aa is the matrix (1a01)\begin{pmatrix}1 & a\\ 0 & 1\end{pmatrix}, which sends (x,y)(x, y) to (x+ay,y)(x + ay, y); a vertical shear by bb is (10b1)\begin{pmatrix}1 & 0\\ b & 1\end{pmatrix}. Multiplying a horizontal shear by aa, a vertical one by bb and a horizontal one by aa gives

(1a01)(10b1)(1a01)=(1+ab2a+a2bb1+ab).\begin{pmatrix}1 & a\\ 0 & 1\end{pmatrix}\begin{pmatrix}1 & 0\\ b & 1\end{pmatrix}\begin{pmatrix}1 & a\\ 0 & 1\end{pmatrix} = \begin{pmatrix}1 + ab & 2a + a^2 b\\ b & 1 + ab\end{pmatrix}.

For this to be the rotation (cos⁡θ−sin⁡θsin⁡θcos⁡θ)\begin{pmatrix}\cos\theta & -\sin\theta\\ \sin\theta & \cos\theta\end{pmatrix}, the bottom-left entry says b=sin⁡θb = \sin\theta, and the diagonal says 1+asin⁡θ=cos⁡θ1 + a\sin\theta = \cos\theta, so a=(cos⁡θ−1)/sin⁡θ=−tan⁡(θ/2)a = (\cos\theta - 1)/\sin\theta = -\tan(\theta/2). The top-right entry then comes out right by itself: 2a+a2b=−sin⁡θ2a + a^2 b = -\sin\theta is a half-angle identity. So the rotation by θ\theta is a horizontal shear by −tan⁡(θ/2)-\tan(\theta/2), a vertical shear by sin⁡θ\sin\theta, and the same horizontal shear again, and the figure draws the three steps for 30∘30^\circ. The square leans left, is lifted on its right side, and leans left again, and what comes out is the square turned rigidly through thirty degrees.

The same calculation works for any matrix of determinant one, not only rotations. A matrix (pqrs)\begin{pmatrix}p & q\\ r & s\end{pmatrix} with ps−qr=1ps - qr = 1 and r≠0r \neq 0 is the product of horizontal shears by (p−1)/r(p-1)/r and (s−1)/r(s-1)/r around a vertical shear by rr. Shears all have determinant one — they keep area, as what a map throws away measured determinants to do — and the factorisation says they generate every area-preserving linear map of the plane, three at a time.

A shear keeps one direction and a rotation keeps none

The factorisation is surprising for a reason that the directions a map leaves alone makes precise. A linear map’s eigenvectors are the directions it sends to themselves, and the two kinds of map sit at opposite extremes. A shear has exactly one: every horizontal line is slid along itself, so the horizontal direction is kept, and no other direction is. Its characteristic polynomial is (λ−1)2(\lambda - 1)^2, a repeated root with only one line of eigenvectors, which the polynomial whose roots are the stretches singled out as the case that cannot be made diagonal. A rotation by anything other than a half-turn keeps no direction at all; its eigenvalues are cos⁡θ±isin⁡θ\cos\theta \pm i\sin\theta, off the real line altogether.

So the factorisation builds a map with no fixed direction out of three maps that each have one, and the trick is that the three fixed directions are not the same. The two horizontal shears keep the horizontal and the vertical shear keeps the vertical, and no direction survives all three. It is the same mechanism by which a chaotic map that always comes back builds Arnold’s cat map from two shears of a square torus: each shear on its own is tame, keeping a direction and sliding everything else along it, and their product stretches one direction and squeezes another. A rotation is the third possibility for a product of shears of determinant one, the case where the trace lies strictly between −2-2 and 22.

Shears also have the oldest pedigree of any area-preserving map. Euclid proves it without moving anything traced the proof of Pythagoras’s theorem in the Elements as a sequence of shears in all but name — a triangle slid along a parallel keeps its area — and the slice that has to match is Cavalieri’s principle, which says that sliding the slices of a solid along themselves keeps its volume. Both are statements that a shear keeps area. The factorisation adds that, among maps keeping area and orientation, shears are not a special case but the raw material.

Why two are never enough

Two shears cannot make a rotation. angle 30: two shears give [[1, -0.5000],[0.5000, 0.7500]], rotation [[0.8660, -0.5000],[0.5000, 0.8660]]; three-shear amount -0.2679, 0.5000.
Fig. 2 Two shears keep area and can match the sine of a rotation, but always leave one diagonal entry of the matrix equal to 1. On the left the square sheared across and then up; on the right the rotation by 30°.

If three shears suffice, it is natural to ask whether two do. They do not, for any angle other than nothing, and the figure shows what goes wrong. Two shears of the same kind are just one shear, since sliding rows by aa and then by a′a' slides them by a+a′a + a'. Two of different kinds multiply to (1+abab1)\begin{pmatrix}1 + ab & a\\ b & 1\end{pmatrix} or to (1ab1+ab)\begin{pmatrix}1 & a\\ b & 1 + ab\end{pmatrix}, depending on the order, and in both one diagonal entry is exactly 1. A rotation’s diagonal entries are both cos⁡θ\cos\theta, which is 1 only when θ\theta is a whole number of turns.

So two shears can get the sine right — the vertical shear by sin⁡θ\sin\theta lifts the right-hand side of the square to exactly the height the rotation puts it — but the left-hand column of the result is then (1,sin⁡θ)(1, \sin\theta) instead of (cos⁡θ,sin⁡θ)(\cos\theta, \sin\theta), too long by a factor of 1+sin⁡2θ\sqrt{1 + \sin^2\theta}. The figure’s left panel is that near-miss: the square is leaned and lifted, its area unchanged, its flag tilted at roughly the right angle, and it is visibly not a rotated square. The third shear is exactly the correction that shortens the stretched side back to length one while keeping the area. The count of three is therefore the least possible, and the order matters only in the trivial sense that the vertical shear could be put on the outside and the horizontal one in the middle instead.

What a shear does to a grid of pixels

A picture rotated by 30°, rounded two ways. rounded rotation: 10 lost, 10 doubled; three rounded shears: 0 lost, 0 doubled; 112 pixels.
Fig. 3 A picture of 112 pixels rotated by 30° in two ways. Rounding each rotated pixel to the nearest square loses 10 pixels to collisions, marked red; rotating by three shears, each rounded row by row, keeps all 112.

On a screen a picture is a set of pixels with whole-number coordinates, and rotating it means deciding, for each pixel, which pixel it moves to. The obvious method is to rotate each pixel’s centre exactly and round the result to the nearest whole coordinates. The left half of the figure does that to a small picture, a flag on a pole inside a ring, rotated by 30∘30^\circ. Ten of the 112 pixels land on a square some other pixel has already taken, so ten squares are hit twice and ten pixels vanish — and since the picture has the same number of squares to fill as it had pixels, ten squares that should have been filled are left as holes. A rotated photograph shows the result as a speckle of missing dots.

The shears do not have this problem, and the reason is a property each shear has on its own. A horizontal shear by aa moves the pixel (x,y)(x, y) to (x+round⁡(ay),y)(x + \operatorname{round}(ay), y): every pixel in row yy is moved along its row by the same whole number of places. So within a row the pixels keep their order and spacing, and different rows never mix. That is a one-to-one map of the grid onto itself, and its exact inverse is to move each row back by the same amount. The vertical shear is the same with columns. Three one-to-one maps compose to a one-to-one map, so the rotation by three rounded shears, on the right of the figure, moves every pixel to a square of its own: no collisions, no holes. Alan Paeth published the method in 1986 for exactly this reason, and it was in use earlier; each step only shifts rows or columns, which is also why it is fast.

The rounding has not disappeared. The rounded shears are not the exact shears, and the picture they produce is not exactly the rotated picture — pixels near the edge may be one place from where exact rotation would send them. What the method guarantees is not accuracy but bijectivity: nothing is lost, so the operation can be undone exactly, and that is a different and in practice more valuable property.

How much the direct method loses

Pixels lost by rounding a rotation. radius 40, 5025 pixels; worst 19.82% at 28 degrees; shears lose 0.
Fig. 4 The share of the 5,025 pixels of a disc of radius 40 lost when the rotation is rounded directly, every half degree from 0.5° to 89.5°. Rotation by rounded shears loses none at any angle.

The ten lost pixels in the flag picture are not bad luck. The figure takes a disc of 5,025 pixels and rounds the rotation at every half degree from half a degree to just under ninety, counting the pixels that collide. The loss rises from nothing at small angles to a maximum of 19.8% near 28∘28^\circ — almost one pixel in five — and falls back towards nothing at a right angle, where the rotation sends whole coordinates to whole coordinates and rounding has nothing to do. The curve is roughly symmetric about 45∘45^\circ, since rotating by 90∘−θ90^\circ - \theta is rotating by −θ-\theta followed by a quarter-turn, which is exact, but the fine structure is jagged: the count of collisions depends on how the rotated grid happens to sit against the original one, and that is arithmetic rather than geometry.

The three rounded shears lose nothing at every one of the 179 angles, as the argument above says they must, and the computation checks it angle by angle rather than taking the argument’s word. The second column of the comparison is just as stark. Rotate the disc forwards by θ\theta and then backwards by θ\theta: with the shears every pixel comes back to where it started, at every angle, because each rounded shear is undone exactly by the opposite rounded shear; with direct rounding, at 30∘30^\circ, 792 of the 5,025 pixels end somewhere other than where they began. Rounding a rotation and then rounding its inverse is not the identity, and the error compounds each time a picture is turned.

And there are a few blue dots on the axis where even the direct method loses nothing. They are not small angles or right angles. They are at 36.87∘36.87^\circ, 22.62∘22.62^\circ, 16.26∘16.26^\circ and their complements — the angles of the 3-4-5, 5-12-13 and 7-24-25 triangles.

The triangles at which rounding is exact

The angles at which rounding loses nothing. 3-4-5:0, 5-12-13:0, 8-15-17:16564, 7-24-25:0, 20-21-29:9700, 12-35-37:7604, 9-40-41:0, 28-45-53:10604, 11-60-61:0, 33-56-65:8664, 16-63-65:4332, 48-55-73:11588, 13-84-85:0, 36-77-85:6644, 39-80-89:9492, 65-72-97:11608
Fig. 5 The first 16 Pythagorean triangles, and for each the rotation by its smaller angle rounded on the pixels of a disc of radius 150. The rotations that round one-to-one, shaded, are exactly those whose hypotenuse is one more than the longer leg.

The rotation by the smaller angle of a right triangle with sides aa, bb, cc has cosine b/cb/c and sine a/ca/c, both fractions, and every triple on one circle showed that the Pythagorean triples are exactly the points with rational coordinates on the unit circle. So for these angles the rotated position of a pixel is a pair of fractions with denominator cc, and whether two pixels round to the same square becomes a question of whole-number arithmetic. The figure asks it for the first sixteen primitive triples, on a disc of more than seventy thousand pixels.

The answer has a sharp pattern. The rotations that round one-to-one are those of 3-4-5, 5-12-13, 7-24-25, 9-40-41, 11-60-61, 13-84-85 — and no others in the list. Every one of them is a triangle whose hypotenuse is one more than its longer leg, the family (2k+1, 2k2+2k, 2k2+2k+1)(2k+1,\ 2k^2+2k,\ 2k^2+2k+1) whose odd legs run through every odd number. The triangle 20-21-29, whose two legs are almost equal, loses 9,700 pixels; 8-15-17 loses 16,564. Bertrand Nouvel and Éric Rémila proved in 2004 that this is the whole truth on the infinite grid: the rounded rotation by θ\theta is a bijection of the grid exactly when θ\theta is a multiple of a right angle or an angle of one of the triangles (2k+1, 2k2+2k, 2k2+2k+1)(2k+1,\ 2k^2+2k,\ 2k^2+2k+1), up to the symmetries of the square.

The family is the same one that a tree that holds every triple finds along one of its outermost branches, and the rope that squares a corner starts from its first member. Nothing about rotation suggests it should appear here. The connection runs through the denominators: when the hypotenuse is one more than a leg, the cosine b/cb/c is within 1/c1/c of one, and the rotated grid sits against the original one so precisely that every rounding cell catches exactly one point. The search sees the pattern on a disc; the proof is what extends it to the whole plane, and the essay does not reproduce it.

Twelve turns that do not make a full turn

12 turns of 30° do not make a full turn. angle 30 x 12, radius 24: 861/1793 home.
Fig. 6 Every pixel of a disc of radius 24 sent through 12 successive rotations by 30°, each made of three rounded shears. The 861 blue pixels end where they began; the red ones do not.

The shears buy bijectivity, and the figure shows exactly what they do not buy. Rotating by 30∘30^\circ twelve times is a full turn, and a full turn should put every pixel back where it was. Each rounded-shear rotation is a one-to-one shuffle of the grid, so twelve of them are too, and nothing is lost — but of the 1,793 pixels in a disc of radius 24, only 861 come back to their starting place. The others have been permuted among themselves. The rounded rotations do not compose the way rotations do: rounding each step is not rounding the whole, and the small displacements of twelve roundings add up to a scramble rather than cancel.

This is the precise cost of discretising a linear map. The exact rotations form a group in which twelve turns of thirty degrees are the identity; the rounded shears are each invertible, so they generate a group of permutations of the grid, but in that group the twelfth power of the thirty-degree turn is a different permutation. Repeated rotation of a picture by small steps therefore does damage even when every single step is lossless, and an image editor that rotates by recomputing from the original each time, rather than rotating the rotated image, is doing the right thing. For a quarter-turn the shears are by −1-1, 11 and −1-1, whole numbers with nothing to round, and four of them bring every pixel home.

What the drawings cannot settle

The figures check a great deal exactly: the factorisation is multiplied out and compared entry by entry, every pixel collision is counted on the grid, every shear-rotation is checked to be one-to-one at every half degree, and every triple in the table is decided on a disc of radius 150. What they cannot reach is the infinite grid. A rounded rotation might be one-to-one on a disc of radius 150 and fail on a bigger one, and indeed tiny angles look one-to-one on small discs simply because the disc is not big enough for two points to collide; the claim about the triples on the whole plane is Nouvel and Rémila’s theorem and is quoted here, not shown.

Nor does the census of lost pixels describe a photograph exactly. A real image is resampled, not pushed pixel by pixel: good software computes each new pixel’s colour by interpolating among the old ones, and then nothing is “lost” in the counting sense, though detail is blurred. The three-shear method’s advantage in that setting is speed and a cleaner kind of interpolation along one direction at a time. The bijection drawn here is the discrete core of the idea, the version in which a pixel is a token to be moved rather than a sample to be blended.

Still open: which angles keep the most

The theorem settles which rounded rotations lose nothing, and the answer is a thin set of angles. The question the loss curve raises is quantitative and less settled: for a given angle, what share of the infinite grid’s points collide, as a density? The computed shares on a disc approximate it, and they depend on the angle in a jagged way that reflects how well cos⁡θ\cos\theta and sin⁡θ\sin\theta are approximated by fractions. Exact formulae are known for some angles, and the structure of the whole function — where its peaks are, how it behaves near the bijective angles — has been studied by people working in digital geometry without a complete description.

The orbit question is open in a stronger sense. Each rounded rotation is a permutation of the infinite grid, and the dynamics of such maps — whether every orbit is finite, how long the orbits are, how they are arranged — have been studied for the closely related rotation by rounding, with striking pictures and few theorems. Whether every orbit of a given discretised rotation is periodic is known for some angles and open for most.

Area kept, pixels kept

A rotation is three shears: across by −tan⁡(θ/2)-\tan(\theta/2), up by sin⁡θ\sin\theta, across by −tan⁡(θ/2)-\tan(\theta/2); two can never do it, because two shears always leave a 1 on the diagonal. On a grid of pixels each shear moves whole rows by a whole number of places, so rounding it keeps it one-to-one, and the three together rotate a picture with no pixel lost and an exact inverse. Rounding the rotation itself loses up to a fifth of the pixels, and is lossless only at the angles of the right triangles whose hypotenuse is one more than a leg — 3-4-5, 5-12-13, 7-24-25 and their infinite family. What the shears cannot do is compose like rotations: twelve lossless turns of thirty degrees bring fewer than half the pixels home.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A dashed tag is an object no other essay names yet.

AreaBijectionDeterminantLinear mapMatrixPythagorean triplesRotationShear