This morning, I was working on some paper on inequality measures, and for computational reasons, I had to sort elements in a matrix. To make it simple, I had a rectangular matrix, like the one below,
> set.seed(1) > u=sample(1:(nc*nl)) > (M1=matrix(u,nl,nc)) [,1] [,2] [,3] [,4] [,5] [,6] [1,] 7 5 11 23 6 17 [2,] 9 18 1 21 24 15 [3,] 13 19 3 8 22 2 [4,] 20 12 14 16 4 10
I had to sort elements in this matrix, by row.
> (M2=t(apply(M1,1,sort))) [,1] [,2] [,3] [,4] [,5] [,6] [1,] 5 6 7 11 17 23 [2,] 1 9 15 18 21 24 [3,] 2 3 8 13 19 22 [4,] 4 10 12 14 16 20
Nice, elements are sorted by row. But for symmetric reasons, I also wanted to sort them by column. So from this sorted matrix, I decided to sort elements by column,
> (M3=apply(M2,2,sort)) [,1] [,2] [,3] [,4] [,5] [,6] [1,] 1 3 7 11 16 20 [2,] 2 6 8 13 17 22 [3,] 4 9 12 14 19 23 [4,] 5 10 15 18 21 24
Nice, elements are sorted by column now. Wait… elements are also sorted by row. How comes ? Is it some coincidence ? Actually, no, you can try…
> library(scatterplot3d) > nc=6; nl=5 > set.seed(1) > u=sample(1:(nc*nl)) > (M1=matrix(u,nl,nc)) [,1] [,2] [,3] [,4] [,5] [,6] [1,] 8 23 5 30 10 15 [2,] 11 27 4 29 21 28 [3,] 17 16 13 24 26 12 [4,] 25 14 7 20 1 3 [5,] 6 2 18 9 22 19 > M2=t(apply(M1,1,sort)) > M3=apply(M2,2,sort)
> M3
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] 1 3 7 14 19 22
[2,] 2 6 9 15 20 25
[3,] 4 8 10 17 23 26
[4,] 5 11 16 18 24 29
[5,] 12 13 21 27 28 30
or use the following function is two random matrices are not enough,
> doublesort=function(seed=2,nl=4,nc=6){ + set.seed(seed) + u=sample(1:(nc*nl)) + (M1=matrix(u,nl,nc)) + (M2=t(apply(M1,1,sort))) + return(apply(M2,2,sort)) + }
Please, feel free to play with this function. Because this will always be the case. Of course, this is not a new result. Actually, it is mentioned in More Mathematical Morsels by Ross Honsberger, related to some story on marching band. The idea is simple: consider a marching band, a rectangular one. Here are my players
> library(scatterplot3d) > scatterplot3d(rep(1:nl,nc),rep(1:nc,each=nl), as.vector(M1), + col.axis="blue",angle=40, + col.grid="lightblue", main="", xlab="", ylab="", zlab="", + pch=21, box=FALSE, cex.symbols=1,type="h",color="red",axis=FALSE)
Quite messy, isn’t it ? At least, this is what the leader of the band though, since some tall players were hiding shorter ones. So, he brought the shorter ones forward, and moved the taller ones in the back. But still on the same line,
> m=scatterplot3d(rep(1:nl,nc),rep(1:nc,each=nl), as.vector(M2), > col.axis="blue",angle=40, + col.grid="lightblue", main="", xlab="", ylab="", zlab="", + pch=21, box=FALSE, cex.symbols=1,type="h",color="red",axis=FALSE)
From the leader’s perspective, everything was fine,
> M=M2
> for(i in 1:nl){
+ for(j in 1:(nc-1)){
+ pts=m$xyz.convert(x=c(i,i),y=c(j,j+1),z=c(M[i,j],M[i,j+1]))
+ segments(pts$x[1],pts$y[1],pts$x[2],pts$y[2])
+ }}
But someone in the public (on the right of this graph) did not have the same perspective.
> for(j in 1:nc){
+ for(i in 1:(nl-1)){
+ pts=m$xyz.convert(x=c(i,i+1),y=c(j,j),z=c(M[i,j],M[i+1,j]))
+ segments(pts$x[1],pts$y[1],pts$x[2],pts$y[2])
+ }}
So the person in the audience ask – one more time – players to move, but this time, to match with his perspective. Since I consider someone on the right, some minor adjustments should be made here
> sortrev=function(x) sort(x,decreasing=TRUE) > M3b=apply(M2,2,sortrev)
This time, it is much bettter,
> m=scatterplot3d(rep(1:nl,nc),rep(1:nc,each=nl), as.vector(M3b), + col.axis="blue",angle=40, + col.grid="lightblue", main="", xlab="", ylab="", zlab="", + pch=21, box=FALSE, cex.symbols=1,type="h",color="red",axis=FALSE)
And not only from the public’ perspective,
> M=M3b
> for(j in 1:nc){
+ for(i in 1:(nl-1)){
+ pts=m$xyz.convert(x=c(i,i+1),y=c(j,j),z=c(M[i,j],M[i+1,j]))
+ segments(pts$x[1],pts$y[1],pts$x[2],pts$y[2])
+ }}
but also for the leader of the marching band
Nice, isn’t it ? And why is this property always valid ? Actually, it comes from the pigeonhole theorem (one more time), a nice explanation can be found in The Power of the Pigeonhole by Martin Gardner (a pdf version can also be found on http://www.ualberta.ca/~sgraves/..). As mentioned at the end of the paper, there is also an interpretation of that result that can be related to some magic trick, discussing – in picture – a few month ago on http://www.futilitycloset.com/… : deal cards into any rectangular array:
Then put each row into numerical order:
Now put each column into numerical order:
That last step hasn’t disturbed the preceding one: rows are still in order. And that’s a direct result from pigeonhole theorem. That’s awesome, isn’t it ?
Depuis le début de la semaine, après avoir déposé les enfants au camp de jour du Musée des Beaux Arts, je viens à pieds à l’université. Chaque fois, je me dis que je pourrais prendre le bus, mais comme aucun ne vient, je commence en marchant, en me disant que si un bus passe, je le prendrais. Et tous les matins, j’arrive au bureau sans m’être fait dépassé par le moindre bus. Et bien sur, j’en ai croisé un paquet qui passaient en sens inverse…
à parcourir, on suppose que les bus sont espacés d’une distance 
, et qu’ils avancent à une vitesse 
. Autrement dit, les bus passent tous les 
secondes (si ma vitesse est exprimée en secondes).
avec 
(oui, on va supposer que je vais moins vite que le bus… ce qui n’est pas forcément une hypothèse faible aux heures de pointes, mais disons que le problème n’a de sens que si aller en bus me permet d’aller plus vite). Le temps que je vais mettre si je fais tous le trajet à pied est 
. Maintenant, comptons les bus qui passent en face. Je vais croiser tous ceux qui sont déjà sur ma portion de trajet, et il y en a 
. En plus, je croiserais tous ceux qui vont arriver à l’université, et qui n’y sont pas encore, soit 
, i.e. le temps qu’il me reste à marcher divisé par le temps qui s’écoule entre deux bus. On a alors un total de 
bus à croiser, en face.
, draw a point 
in a neighborhood of 
, 
then 
then 
then 
then 
. To illustrate the idea, consider the following function
chambers, it there are 
bullets in 
if we don’t. Not spinning is better if and only if
… or 
(in that case, it might not be a good idea actually to play the game).
has a priori distribution 
, and that 
, given 
.
? Or is it just trivial ?”. After having those previous philosophical questions, we came to the point that if it was trivial, then we should be able to prove it. A standard way of writing the algorithm is to use the quantile based technique
with 
,
with 
,
where 
and 
are two independent random variables with a uniform distribution on the unit interval. Let us try to derive its distribution, i.e.
so in 5 or 6 steps the algorithm of subdivision should converge. I guess… I mean, I do not know for sure, since 50 is not a power of 2, so it might be difficult, each time, to split in two: we have to deal only with integers here…
