# Examples of Binary Functions that Yield Regular Graphs with Invertible Adjacency Matrix

Question:

What are, provided their existence, examples of functions $$f$$ with the following properties:

\begin{align}f:& \ \mathbb{N}\times\mathbb{N}\ni(i,j)&\mapsto\ \quad\quad\quad\quad\quad\ \beta\in\lbrace 0,1\rbrace\\ &f(i,i)&=\quad\quad\quad\quad\quad\quad\quad\quad\quad\ 0\\ &f(i,j)&=\quad\quad\quad\quad\quad\quad\quad\ f(j,i)\\ &\sum_{i=1}^{\infty}{f(i,j)}&=\quad k\in\mathbb{N}\quad \forall n\ge n_0\ge k\\ &\sum_{j=1}^{\infty}{f(i,j)}&=\quad k\in\mathbb{N}\quad \forall n\ge n_0\ge k\\ &F\in\lbrace0,1\rbrace^{n\times n},\ 1\le i,j \le n,\ F_{ij}=f(i,j)&\implies\quad\quad\quad\quad\quad\quad \ |F|\ne 0\end{align}
The calculation of $$f(i,j)$$ must not depend on $$n$$ but would ideally be parameterized by $$k\in\mathbb{N}$$

In reply to @PuckRombach's comment: Another restriction is that, given $$k$$ the $$f(i,j)$$ must yield matrices with the described properties for all $$n\ge n_0\ge k$$

• These exist for every $n$: if you take a matrix that has 0s on the diagonal and 1s everywhere else it is invertible. Does your question come down to: how many matrices in $GL(n,\mathbb{Z}_2)$ have constant row/column sums and 0s on the diagonal? – Puck Rombach Dec 23 '18 at 14:05
• @PuckRombach your first example amounts to $k=n$, which implies a dependency of $k$ on $n$, a case that I thought I had ruled out; I will edit accordingly. To your second question: I am not so much interested in the number of such matrices or in concrete examples of such matrices, but rather in functions that yield such matrices. – Manfred Weis Dec 23 '18 at 15:03
• It would be $k=n-1$, but we can also let every column have $k$ 1s starting below the diagonal, for example. Isn't the matrix equivalent to the kind of function you want? – Puck Rombach Dec 23 '18 at 15:21
• @PuckRombach Initially I would be happy with a function that works for $k=2$ and arbitrary $n\ge 4$ – Manfred Weis Dec 23 '18 at 15:24
• In that case I think you should rephrase the question here to include explicitly the properties that you need your matrix to have. – Puck Rombach Dec 23 '18 at 16:03