# Julia, 9

I identify a class of full rank matrices for which the criterion `A*B = 10A + B` can be checked in constant time, `nxn`-matrices of the form

       a b b b . . . b
       b a b b       .
       b b a b       .
       b b b a       .
       .       .     .
       .         .   .
       .           a b
       b . . . . . b a


Then I do a random search for those matrices in this class fulfilling the criteria. As these are full, I can make block-matrices out of two random elements of the class get a half-filled larger solution.




```julia
using Random, LinearAlgebra
check(a1, a2, b1, b2, n, base) = a2 != 0 && a1*b1*n + a2*b1 + b2*a1 == base*a1 + b1 && a1*b1*n + a2*b1 + b2*a1 + a2*b2 == base*(a1 +a2) + b1 + b2

function generate(base=10)
    while true
        a1 = rand(1:base-1)
        b1 = rand(1:base-1)
        a2 = rand(-a1+1:base-1-a1)
        b2 = rand(-b1+1:base-1-b1)
        n = rand(1:10)
        if check(a1, a2, b1, b2, n, base)
            return a1*ones(Int, n, n) + a2*I, b1*ones(Int, n, n) + b2*I
        end
    end
end
nosp(A) = sum(A .== 0) <= size(A,1)*size(A,2)/2
fake(A, B) = rank(A) > 0 && rank(B) > 0 && nosp(A) && nosp(B) && A*B == 10*A + B
```

```julia
Random.seed!(333333333333); A1, B1 = generate()
A2, B2 = generate()
A = [A1 0I; 0I A2]
B =[B1 0I; 0I B2]
fake(A2, B2)
```

```
 1  2  2  2  2  2  0  0  0  0  0  0
 2  1  2  2  2  2  0  0  0  0  0  0
 2  2  1  2  2  2  0  0  0  0  0  0
 2  2  2  1  2  2  0  0  0  0  0  0
 2  2  2  2  1  2  0  0  0  0  0  0
 2  2  2  2  2  1  0  0  0  0  0  0
 0  0  0  0  0  0  1  2  2  2  2  2
 0  0  0  0  0  0  2  1  2  2  2  2
 0  0  0  0  0  0  2  2  1  2  2  2
 0  0  0  0  0  0  2  2  2  1  2  2
 0  0  0  0  0  0  2  2  2  2  1  2
 0  0  0  0  0  0  2  2  2  2  2  1

 6  1  1  1  1  1  0  0  0  0  0  0
 1  6  1  1  1  1  0  0  0  0  0  0
 1  1  6  1  1  1  0  0  0  0  0  0
 1  1  1  6  1  1  0  0  0  0  0  0
 1  1  1  1  6  1  0  0  0  0  0  0
 1  1  1  1  1  6  0  0  0  0  0  0
 0  0  0  0  0  0  6  1  1  1  1  1
 0  0  0  0  0  0  1  6  1  1  1  1
 0  0  0  0  0  0  1  1  6  1  1  1
 0  0  0  0  0  0  1  1  1  6  1  1
 0  0  0  0  0  0  1  1  1  1  6  1
 0  0  0  0  0  0  1  1  1  1  1  6
```

There are not too many valid pairs of them but there are ten distributed over the dimensions for base 10. It also produces only a single 12x12 solution therefore it was agreed to count the method at the level of the second largest solutions it produces, ie 9.