# Tag Info

7

JavaScript (ES6), 68 bytes This is using xnor's method -- but obviously without complex numbers. Takes the input matrix $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ as 4 distinct parameters a,b,c,d. Returns a string of digits ($0$ for $S$, $1$ for $T$). f=(a,b,c,d)=>b|c|a-1|d-1?a*c>-b*d?1+f(a-c,b-d,c,d):0+f(c,d,-a,-b):'' Try it online! ...

7

Python, N = 7 Using variable neighborhood search over elementary row and column operations. Not every seed works quickly (or at all?), but seed 9 finds a solution for N = 7 in a few seconds. $time python3 search.py 7 9 [[0 3 6 6 1 6 6] [0 1 5 5 0 5 5] [1 3 1 2 1 8 1] [0 0 1 0 0 1 0] [1 7 9 9 0 9 9] [1 3 1 1 1 0 1] [0 0 1 1 0 1 1]] [[5 5 1 1 0 4 0] [... 6 Python, 67 bytes g=lambda z,w:(z/w).real>0and'T'+g(z-w,w)or z+w*w and'S'+g(w,-z)or'' Try it online! Thanks to Bubbler for cutting a byte Takes input as two complex numbers for the rows. The idea is simple and easy-to-see on a less-golfed version: def f(a,b,c,d): if (a,b,c,d)==(1,0,0,1): return '' elif a*c+b*d>0: return 'T'+f(a-c,b-d,c,d) else: ... 6 Jelly, 7 bytes ŒPḊ^/ÞḢ A monadic Link accepting the list of distinct integers representing the vectors which yields a subset representing the linear dependence. (May be employed as a dyadic Link also accepting the number of dimensions on the right.) Try it online! How? ŒPḊ^/ÞḢ - Link: list of distinct integers e.g. [1,3,4,7] ŒP - power-set ... 5 Perl 6, 39 bytes {first {![+^]$_},.combinations(1..$_)} Try it online! Returns the first combination of the input that is zero when reduced XOR. I wish {![+^]$_} could be changed to !*.&[+^].

5

Pyth, 6 bytes hxFDty Try it online! To explain, back to front: y generates all subsets of the input. t (tail) removes the first, empty subset. D means order by the following function: F means reduce on: x is the xor function. h (head) takes the first element of the sorted list. The lists that xor to 0 will be sorted to the front.

4

MATL, 12 bytes t1Y)-X$&Yvoz Input is a matrix, where each row defines a point. Try it online! Or verify all test cases. Explanation The code uses the singular value decomposition of a matrix, which is done symbolically to prevent floating-point issues. The rank of a matrix equals the number of non-zero singular values. t % Implicit input: matrix of ... 4 Wolfram Language (Mathematica), 23 bytes MatrixRank@*Differences Try it online! Alternative: (23 bytes, 21 characters) MatrixRank[#&@@#-#]& Try it online! SingularValueDecomposition in Mathematica is already 26 bytes long. 3 APL (Dyalog Extended), 47 bytesSBCS Anonymous tacit prefix function. Gives Boolean list with 0 and 1 meaning $S$ and $T$ respectively. {⍺≡⊃+.×/(r←⊤⍵)⊇2 2∘⍴¨(0 ¯1 1)(1 1 0):r⋄⍺∇1+⍵}∘1 Try it online! (Faster edition emulating Extended in Unicode.) {…}∘1 apply the following function with 1 and the given matrix as right and left arguments: (0 ¯1 1)(1 1 ... 3 Python 3.8, 74 bytes f=lambda a,s=[],v=0:s*(v<1)or a and(f(n:=a[1:],s+a[:1],v^a)or f(n,s,v)) Try it online! 3 05AB1E, 8 bytes æ¦.Δ.»^> Try it online! How? æ¦.Δ.»^> - implicitly take input æ - power-set ¦ - tail .Δ - keep first which is 1 under: .» - reduce by: ^ - XOR > - increment - implicit print 3 Haskell, 79 bytes import Data.Bits p[a]=[[a]] p(a:b)=map(a:)(p b)++p b filter((1>).foldl xor 0).p Try it online! Defines the power set (ignoring the empty set) as p, then our solution is: filter((1>).foldl xor 0).p Or in english: Get the power set and then select all the members whose xor sum is less than 1 (i.e. zero). 3 APL (Dyalog Extended), 19 bytes {×/-∊(⍳≢⍵)↓¨↓∘.-⍨⍵} Dfn producing the pairs, then taking the product. ↓∘.-⍨⍵ all pairs (with repeats) (⍳≢⍵) range from 1 to the length of the input ↓¨ drop 1 2 3 4... elements to avoid repeats -∊ flatten and negate ×/ take the product Try it online! 3 05AB1E, 36 29 bytes ÄàD(Ÿsgãsgãã.ΔD2FsN._øδ*O}-Q -7 bytes thanks to @ovs in another answer of mine. Extremely slow since I'm using a brute-force approach with three cartesian products. But performance is irrelevant for code-golf challenges I guess (would love to see this same challenge as fastest-code or fastest-algorithm). Try it online (only works for ... 3 N = 2 This is a naive brute force approach in R: randomvalid <- function(N) { while (T) { X <- matrix(sample(10,N*N,T)-1,N) if (sum(X==0) < N*N/2 && qr(X)$rank == N) return(X) } } tryforever <- function(N) { i <- 1 while (T) { i <- i + 1 if (i %% 100000 == 0) print(sprintf("after %d tries...",...

2

JavaScript (Node.js), 121 119 117 115 101 bytes A=>(F=(a,t,r)=>{a--?A[t].map((x,i)=>F[i]=F[i]||F(F[i]=a,i,a%2?r:r*x/(a+2))):s+=r})(A.length,s=0,1)||s Try it online! Explanation & Ungolfed function hafnian(A) { // Main function taking an array return ( F = function( // Helper function, and also a temporary ...

2

Ruby, 78 bytes f=->a{(1..a.size).map{|x|a.combination(x).map{|x|return x if x.reduce(:^)<1}}} Try it online! :^) Probably golfable.

2

JavaScript (ES6),  84 60  58 bytes Ignores $d$. Returns $0$ if there's no solution. f=([v,...a],x,o=[])=>x<1?o:v?f(a,x,o)||f(a,x^v,[...o,v]):0 Try it online! Commented f = ( // f is a recursive function taking: [v, // v = next value from the input set ...a], // a[] = ...

2

Jelly,  24  22 bytes ⁽¬Pb3’s2$⁺⁸ṃæ×/⁼ 0ç1#B A monadic Link accepting the target matrix which outputs a list containing a single list of 1s ($S$) and 0s ($T$). As a full program a Jelly representation of this list is printed. Always yields a resulting equation with a leading $S$ (except for an input of $T$ itself). Note that since $S^4=I\... 2 Python 3, 301$\cdots\$ 139 129 bytes def f(a,b,c,d,l=''): while c: while 0>a or b<0:a,b,c,d=c,d,-a,-b;l+='S' if c:q=-a//c;a+=q*c;b+=q*d;l+='T'*-q return l+'T'*b Try it online! Saved 18 bytes thanks to Arnauld!!! Takes the 4 matrix elements as separate numbers as input and outputs a string of 'S's and 'T's.

2

MATL, 42 38 32 bytes @B"@?FT!tqh}IlhB]]Nq:"Y*]G-z}@B The code enumerates all finite sequences that begin with S, and stops when a solution is found. It is sufficient to test sequences beginning with S because S*S*S*S equals the identity matrix (inspiration from @Adam's APL solution). Outputs a binary sequence, where 1 corresponds to matrix S and 0 to ...

2

05AB1E, 48  44  43 40 bytes Crossed out &nbsp;44&nbsp; is no longer 44 :) 9bS[)DðýIk©d#¼vyDÁ0T·Sǝ+y2Å€(}2ôí˜]T¾ã®è 9bS and DÁ0T·Sǝ+ could alternatively be 9Yв/т1ª/тĆS/TºS and D2ôO13Sǝ/DÁ2Å€0}+ for the same byte-count. Brute-force approach with pretty bad performance (it times out for the last three test cases - the previous 48;44;43 bytes versions ...

2

Mathematica, 61 bytes f[d_,l_]:=NullSpace[IntegerDigits[#,2,d]&/@l,Modulus->2][] This gives a bitmask (well a list of zeros and ones) of which elements of the list are in the set, as was allowed by the OP.

2

J, 36 bytes 0-.~1{ ::0[:(#~0=XOR/"1)]#~2#:@i.@^# Try it online!

2

APL (Dyalog Unicode), 17 bytes ≢⍸1≠1+2⊃8415⌶2-⌿⎕ Try it online! Happens to be a mix of existing MATL and Mathematica solutions. Performs Singular Value Decomposition on pairwise differences of the rows, and counts nonzero eigenvalues in the result of SVD. Since APL does not have symbolic computation, we use "significantly different from zero" ...

2

Julia 0.7, 18 bytes m->rank(m.-m[:,1]) Try it online! Analogous approach in R is slightly longer (3 bytes saved by Giuseppe): R, 27 24 bytes function(m)qr(m-m[,1])\$r Try it online!

2

JavaScript (ES6), 187 bytes There's probably a much shorter way. This is using the matrix rank method. m=>m[m=m.map(r=>r.map((v,i)=>v-m[i])),n=0].map((_,i)=>(R=m.find((r,k)=>r[i]&&r[j=~k]^(r[j]=1)))&&m.map(r=>++j*r[i]&&R.map((v,k)=>r[k]-=k>i&&v*r[i]),n++,R=R.map((v,k)=>k>i?v/R[i]:v)))|n Try ...

2

N = 4, Swi-Prolog After all the math, my best result so far is a relatively naive solution in prolog. :- use_module(library(clpfd)). % N is the dot product of lists V1 and V2. dot(V1, V2, N) :- maplist(product,V1,V2,P), my_sumlist(P,N). product(N1,N2,N3) :- N3 #= N1*N2. my_sumlist([], 0). my_sumlist([H|T], N) :- my_sumlist(T, X), N #= X + H. my_scamul(_, ...

1

Burlesque, 16 bytes peR@{{$$}r[n!}fe Try it online! Takes arguments as d {1 2 3 4...} pe # Read vals and push to stack R@ # Generate all subsets { {$$}r[ # Reduce by xor n! # Boolean not }fe # Find first element

1

Mathematica, 38 bytes Select[Rest@Subsets@#,BitXor@@#==0&]& Returns the list of solutions or an empty list if no solutions exist. Try it online!

Only top voted, non community-wiki answers of a minimum length are eligible