A349481 a(n) is the number of Boolean factors of the contranominal scale of size n by the GreConD algorithm for Boolean matrix factorization.

0, 2, 3, 4, 5, 5, 5, 6, 7, 7, 7, 7, 7, 7, 7, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12

Offset: 1

Author

Dmitry I. Ignatov, Nov 19 2021

Keywords

• nonn

Comments

Contranominal scales can be considered as Boolean matrices of size n X n full of ones except the main diagonal, which is filled by zeros (Ganter and R. Wille, 1999). The optimal number k of Boolean factors for a Boolean matrix A is known as its Schein rank (Kim, 1982; Marenich, 2010) and is defined as the smallest k such that A=P*Q, where * is Boolean matrix multiplication, A has the size n X m, and P,Q are n X k and k X m Boolean matrices, respectively. The problem of Boolean matrix factorization (BMF) is NP-hard and one of the state-of-the-art greedy algorithms is GreConD (Belohlavek & Vychodil, 2010). Contranominal scales are known as the worst theoretical case w.r.t. the number of potential Boolean factors (formal concepts), 2^n (Albano, 2014; Albano and Chornomaz, 2017; Dürrschnabel et al., 2021), while their Schein rank is given by A305233. The output of GreConD does not always result in the optimal number of factors for contranominal scales, so the sequence of its outputs is checked empirically for n up to 128 and the formula for a(n) is provided in (Ignatov & Yakovleva, 2021). See the links below for more checked examples up to n=513.

Examples

			For n=1 there are zero factors.
For n=2 the factors are ({1}, {0}), ({0}, {1}). The coresspoding factorization is below:
  A  =  P  *  Q
[0 1] [0 1] [1 0]
[1 0] [1 0] [0 1] .
For n=3 the factors are ({1, 2}, {0}), ({0, 2}, {1}), ({0, 1}, {2}). The corresponding trivial factorization, A=P*Q, where P=A and Q is the 3 X 3 identity matrix, is below:
[0 1 1] [0 1 1] [1 0 0]
[1 0 1]=[1 0 1]*[0 1 0]
[1 1 0] [1 1 0] [0 0 1] .
For n=4 the factors are ({2, 3}, {0, 1}), ({0, 1}, {2, 3}), ({1, 3}, {0, 2}), ({0, 2}, {1, 3}).
...
For n=7 the factors are ({3, 4, 5, 6}, {0, 1, 2}), ({0, 1, 2, 6}, {3, 4, 5}), ({1, 2, 4, 5}, {0, 3, 6}), ({0, 2, 3, 5}, {1, 4, 6}), ({0, 1, 3, 4, 6}, {2, 5}).
The nontrivial factorizaion with the number of factors k=5 smaller than n=7 is below:
[0 1 1 1 1 1 1] [0 1 0 1 1]
[1 0 1 1 1 1 1] [0 1 1 0 1] [1 1 1 0 0 0 0]
[1 1 0 1 1 1 1] [0 1 1 1 0] [0 0 0 1 1 1 0]
[1 1 1 0 1 1 1]=[1 0 0 1 1]*[1 0 0 1 0 0 1]
[1 1 1 1 0 1 1] [1 0 1 0 1] [0 1 0 0 1 0 1]
[1 1 1 1 1 0 1] [1 0 1 1 0] [0 0 1 0 0 1 0]
[1 1 1 1 1 1 0] [1 1 0 0 1] .
		

References

• A. Albano and B. Chornomaz, Why concept lattices are large: extremal theory for generators, concepts, and VC-dimension. Int. J. Gen. Syst. 46(5) (2017) 440-457.
• A. Albano, Upper Bound for the Number of Concepts of Contranominal-Scale Free Contexts. ICFCA 2014: 44-53.
• R. Belohlavek and V. Vychodil, Discovery of optimal factors in binary data via a novel method of matrix decomposition. Journal of Computer and System Sciences 76(1) (2010) 3 - 20.
• D. Dürrschnabel, M. Koyda, and G. Stumme, Attribute Selection Using Contranominal Scales. ICCS 2021: 127-141.
• B. Ganter and R. Wille, Formal Concept Analysis - Mathematical Foundations. Springer 1999, ISBN 978-3-540-62771-5, pp. I-X, 1-284.
• D. I. Ignatov and A. Yakovleva, On Suboptimality of GreConD for Boolean Matrix Factorisation of Contranominal Scales. FCA4AI@IJCAI 2021, 87-98.
• K. H. Kim, Boolean matrix theory and applications. Marcel Dekker, New York and Basel (1982).
• E. Marenich, Determining the Schein Rank of Boolean Matrices. Matrix Methods: Theory, Algorithms and Applications (2010) 85-103.

Links

• Dmitry I. Ignatov, Table of n, a(n) for n = 1..513
• Dmitry I. Ignatov, iPython notebook with the code and the examples of factors up to 513
• Dmitry I. Ignatov, iPython notebook in PDF with the code and the examples of factors up to 513
• D. I. Ignatov and A. Yakovleva, On Suboptimality of GreConD for Boolean Matrix Factorisation of Contranominal Scales.
• A. Yakovleva, Python Code.
• Wikipedia, Formal Concept Analysis.

Crossrefs

A305233 represents the Schein rank of the contranominal scale of size n.

Formula

a(n) = floor(log_2(n)) + ceiling(log_2(n)).