When a deck of playing cards is shuffled perfectly, the result is not random. A perfect shuffle places the cards in a mathematically precise order. As a result, when the most common version of a perfect shuffle is repeated eight times, the deck returns to its original state.

Contents

A Deck of Playing Cards

Fresh out of its package, a deck of playing cards always has the Ace of Spades first, followed by the rest of the spades. The hearts, in order, are next, followed by the clubs (shown here in green), and finally the diamonds (blue). The King of Diamonds is last. Here is a view of a fresh deck.

   v = 1:52;
   deck_view(v)
   title(0)

Faro Shuffles

A perfect shuffle is also known as a faro shuffle, because it is used frequently in the classic card game, Faro. The deck is cut into two packs, each containing exactly half of the cards. Then the two packs are merged by precisely interleaving the cards.

There are two variants. In an out-faro shuffle, the merger is started with the top card from the first half and eventually completed with the last card from the second half. So with an out-faro shuffle of a fresh deck, the Ace of Spades remains on top and the King of Diamonds remains on the bottom. An in-faro shuffle is started with the second half. So the Ace of Spades and the King of Diamonds are inserted in the second and next to last positions respectively.

Out-Faro

A shuffle is a permutation of the elements of a vector representing the deck. Here is the index vector that produces an out-faro shuffle. A rectangular matrix is created with 1:26 in the first row and 27:52 in the second. So its first column is [1;27], its second column is [2;28], and so on. The reshape operation, which is carried out by columns, then generates the desired index vector.

   pout = reshape([1:26; 27:52],[1,52])

pout =
  Columns 1 through 13
     1    27     2    28     3    29     4    30     5    31     6    32     7
  Columns 14 through 26
    33     8    34     9    35    10    36    11    37    12    38    13    39
  Columns 27 through 39
    14    40    15    41    16    42    17    43    18    44    19    45    20
  Columns 40 through 52
    46    21    47    22    48    23    49    24    50    25    51    26    52

Here is the result of two successive out-faro shuffles of a fresh deck.

   v = 1:52;
   v = v(pout);
   deck_view(v)
   title(1)

   v = v(pout);
   deck_view(v)
   title(2)

The four Aces have moved to the front and the four Kings are bringing up the rear.

It takes only 8 Out-Faro shuffles.

Let's start over with a fresh deck, apply the pout permutation eight times, and capture the results in an animated gif. The deck is returned to its original state in just 8 steps.

v = 1:52;
deck_view(v)
title(0)
for t = 1:8
   v = v(pout)
   deck_view(v)
   title(t)
end

In-Faro

Here is the indexing vector for the in-faro suffle.

   pin = reshape([27:52; 1:26],[1,52])

pin =
  Columns 1 through 13
    27     1    28     2    29     3    30     4    31     5    32     6    33
  Columns 14 through 26
     7    34     8    35     9    36    10    37    11    38    12    39    13
  Columns 27 through 39
    40    14    41    15    42    16    43    17    44    18    45    19    46
  Columns 40 through 52
    20    47    21    48    22    49    23    50    24    51    25    52    26

It takes 52 in-faro shuffles to get back to the original state.

Permutation Matrices

Both of the faro shuffles can be represented by permutation matrices. Can you see how their spy plots differ?

   I = eye(52);
   close
   Pout = I(pout,:);
   spy(Pout)
   title('Pout')

   Pin = I(pin,:);
   spy(Pin)
   title('Pin')

It turns out that the smallest value of t for which the matrix power P^t is equal to the identity matrix is t = 8 for P = Pout and t = 52 for P = Pin.

Eigenvalues.

All of this is explained by eigenvalues. The matrix Pout has order 52, but only 8 distinct eigenvalues, namely the 8-th roots of unity.

   plot(eig(Pout),'o')
   title('eig(Pout)')
   axis(1.25*[-1 1 -1 1])
   axis('square')

On the other hand, Pin has 52 distinct eigenvalues, the 52-nd roots of unity.

   plot(eig(Pin),'o')
   title('eig(Pin)')
   axis(1.25*[-1 1 -1 1])
   axis('square')

Multiplicities

The eigenvalues of Pout occur with different multiplicites. Can you explain where these counts come from?

   e = eig(Pout);
   z = exp(pi/4*1i)
   count = zeros(1,8);
   for k = 0:7
      count(k+1) = sum(abs(e-z^k)<52*eps);
   end
   disp(' ')
   disp('multiplicites = ')
   disp('     1     z     i    z^3   -1    z^5   -i    z^7')
   disp(count)

z =
   0.7071 + 0.7071i
 
multiplicites = 
     1     z     i    z^3   -1    z^5   -i    z^7
     9     6     6     6     7     6     6     6

Deck_view.

Here is the listing of deck_view.

   type deck_view

function deck_view(v)
% deck_view(v) displays the card deck v.

   % Prepare the figure window.
   f = clf;
   f.Position = [200 300 600 150];
   f.NumberTitle = 'off';
   f.ToolBar = 'none';
   f.MenuBar = 'none';
   f.PaperPositionMode = 'auto';
   
   % Prepare the axes.
   ax = axes;
   ax.Position = [0 0 1 .88];
   ax.XLim = [-1 54];
   ax.YLim = [-1 15];
   ax.XTick = '';
   ax.YTick = '';
   ax.Box = 'on';
   
   % Colors for spades, hearts, clubs, diamonds.
   shcd = [0 0 0; 1 0 0; 0 .5 0; 0 0 .5];
   
   % Plot one text character per card.
   pips = 'A23456789TJQK';
   for i = 1:52
      j = mod(v(i)-1,13)+1;
      k = floor((v(i)-1)/13)+1;
      t = text(i,j,pips(j));
      t.FontSize = 10;
      t.Color = shcd(k,:);
   end
end

An informative video.

Kevin Houston is a mathematician at the University of Leeds in the UK who can also do perfect shuffles. Here is a link to his YouTube video. Perfect Shuffle.

Get the MATLAB code

Published with MATLAB® R2015b