Just generate first a symettric matrix then perturb a "the overwhelming minority" of elements.
Whatever that definnition means.
>> T=randi(9,10,10);
>> T=randi(9,10,10);
>> S=T+T'
S =
4 13 4 9 10 10 11 9 12 16
13 2 12 18 8 9 9 13 4 11
4 12 2 9 12 17 4 12 10 13
9 18 9 6 7 11 12 7 7 6
10 8 12 7 8 6 4 3 9 8
10 9 17 11 6 10 6 11 6 5
11 9 4 12 4 6 18 15 10 6
9 13 12 7 3 11 15 14 12 10
12 4 10 7 9 6 10 12 16 9
16 11 13 6 8 5 6 10 9 16
>> S(randperm(numel(S),10))=randi(10,1,10)
S =
4 13 4 9 10 10 11 9 12 16
13 10 10 18 8 9 9 13 4 11
4 12 2 9 12 17 4 12 10 13
9 18 9 6 7 11 12 7 7 6
10 8 12 7 8 6 4 3 9 8
10 9 10 11 6 10 6 11 6 5
11 9 4 12 5 6 18 15 10 6
9 13 5 7 3 11 15 14 12 10
12 4 10 7 9 6 2 12 16 9
16 11 2 3 8 4 6 10 9 5
Best Answer