# Attempt to solve a matrix (counterbalancing) problem computationally gives “spooky” result: why?

This question is posted on the mathematics section of stackexchange because my uneducated guess is that the answer involves some basic mathematical principles, possibly in the domain of linear algebra. However, the initial problem is a practical one and involves counterbalancing a number of experimental conditions across a number of study participants. I wish I knew how to formulate the problem mathematically in more general terms. The question also contains snippets of MATLAB code but hopefully those snippets of code can be directly understood by non-MATLAB people. If it turns out that the solution doesn't involve any math, the question will be moved to another section.

There are 16 pictures, and 16 words that describe each of the pictures. If a word is presented at the same time as a picture that doesn't fit (e.g. the word "tree" spoken as the picture of a nose is presented), it is a mismatch. So, for each of the 16 pictures, there are 15 possible mismatches. All participants cannot see every possible combinations (the study would take too long), but in theory just 15 participants are sufficient to sample all of the 16x15 mismatch pairs once.

One uses a matrix to describe the counterbalancing of the mismatch conditions across participants, which as 15 rows (one per participants) and 16 columns (one per picture). In each cell of the matrix is the number of the audio stimuli that is used as a mismatch for this particular subject/picture.

The matrix needs to meet three conditions:

1. each number should appear exactly once in each line
2. each number, except the number of the column, should appear exactly once in each column
3. filling out the matrix should be done "as randomly as possible", provided that conditions 1 and 2 are met

Below is the piece of MATLAB code that was used to generate a solution:

n=16;
maxIt = n;

mismatches     = NaN([n-1 n]);
columnsampler  = 1:n;
linesampler    = 1:(n-1);

% filling out the matrix cell by cell, taking the lines and column in
% random order to try to maximize randomness
columnsampler  = columnsampler(randperm(length(columnsampler)));
linesampler    = linesampler(randperm(length(linesampler)));

for j = linesampler
for i = columnsampler

% Try all possible mismatching audio stimuli iteratively, in
% the same order as columnsampler (otherwise no solution was found after a large number of trials)
mismatch = columnsampler; mismatch(mismatch==i)=[];
done = 0;
it = 1;
while (done == 0)&&(it<(maxIt))

token = mismatch(it);

% Check conditions 1 and 2
repeated = nansum(mismatches(j,:) == token) + nansum(mismatches(:,i) == token);
if repeated == 0
done = 1;
mismatches(j,i) = token;
end

if repeated >0
it=it+1;
if it >= maxIt
disp('WARNING: MaxIt reached, returning early without finding a solution')
done = 1;
end
end
end

end
end


Now one of the solution provided is below:

Spooky solution

Surprisingly to me (but hopefully not to this section), the mismatches matrix has obvious properties that were not (as far as I can tell) explicitly built-in.

(1) in each row i,

if

mismatches(i,j) = k

then

mismatches(i,k) = j

i.e. for a given subject i the audio/visual conditions are simply permuted pair by pair to give the mismatches. This is not a welcome behavior, but probably fine in terms of risk of experimental bias.

(2) because of the above property, reading a given row in the order given by this same row gives back 1:16 (ok, funny)

(3) now another property (that is just downright spooky) is that when one reads the numbers in one row i in the order that is given by a different row j, the result is equal to another row k. One can explore this property by filling out a matrix called "recursivity" (probably not the proper term) as in the piece of MATLAB code below:

recursivity=NaN([15 15]);
for i = 1:15
for j = 1:15
for k = 1:15
if sum(abs(mismatches(k,:)-mismatches(i,mismatches(j,:)))) ==0
recursivity(i,j)=k;
elseif sum(abs((1:16)-mismatches(i,mismatches(j,:)))) ==0
recursivity(i,j)=0;
end
end
end
end


The result is here: recursivity matrix.

(4) another property is that recursivity is symmetrical, which I think means that for all i and j

mismatches(i,mismatches(j,:)) = mismatches(j,mismatches(i,:))

so reading the elements of line i in the order given by the elements of line j is the same as reading the elements of line j in the order given by the elements of line i. Now I'm really scratching my head as to why this happened.

After this lengthy description, my question is two-fold:

• What am I looking at? Is this an involuntary "feature" of the code that produced this behavior in the solution? Or does it logically follow from the problem at hand? Was I just very very unlucky?
• Are there other solutions that do no exhibit this behavior, and if so how can I find them?

It turns out that the answer has nothing to do with linear algebra, and all to do with the awkward way in which the sampling was implemented in the code.

Because the sampling method was so inefficient, it only returned a solution (in a reasonable amount of time) when, inside each cell, the numbers were tried in the order of the columns. This non-randomness caused the spooky behavior (in a way that I don't understand precisely).

The more efficient code below found a truly random solution very fast:

mismatches=[];

while (size(mismatches,1)<(n-1))

GlobalChoices = 1:n; % keeps track of the pairings available       (*)
CurMismatch   = NaN([1 n]); % we'll fill this in
found         = true; % we'll only change this to false if we need to start over

for i=1:16

LocalChoices = GlobalChoices;       % we'll make a list of things we can pair i with, given the criteria
LocalChoices(LocalChoices==i) = []; % can't pair i with itself

for k = 1: size(mismatches,1)
LocalChoices(LocalChoices == mismatches(k,i))=[]; % can't repeat pairs
end

if isempty(LocalChoices) %oops! we need to start over at position (*)
found = false;
break;  % exit the for loop to try again
else % so far, so good
x = LocalChoices(randi(length(LocalChoices))); % random element of LocalChoices
CurMismatch(i)= x;
GlobalChoices(GlobalChoices == x) = []; % can't use this again
end

end  % close the for loop

if found
%if we found a solution, add it. Continue until we have 15.
mismatches(size(mismatches,1)+1,:) = CurMismatch;
end

end


Thanks to the person who provided me this code!

Moral of the story: Be careful how you randomly sample, because if you do it in a crappy way your solution can be very slow/impossible to find, or not random at all.