

A349481


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


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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 NPhard and one of the stateoftheart 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.


REFERENCES

A. Albano and B. Chornomaz, Why concept lattices are large: extremal theory for generators, concepts, and VCdimension. Int. J. Gen. Syst. 46(5) (2017) 440457.
A. Albano, Upper Bound for the Number of Concepts of ContranominalScale Free Contexts. ICFCA 2014: 4453.
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: 127141.
B. Ganter and R. Wille, Formal Concept Analysis  Mathematical Foundations. Springer 1999, ISBN 9783540627715, pp. IX, 1284.
D. I. Ignatov and A. Yakovleva, On Suboptimality of GreConD for Boolean Matrix Factorisation of Contranominal Scales. FCA4AI@IJCAI 2021, 8798.
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) 85103.


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.


FORMULA

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


EXAMPLE

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] .


CROSSREFS

A305233 represents the Schein rank of the contranominal scale of size n.
Sequence in context: A006159 A081610 A063273 * A200262 A347762 A270432
Adjacent sequences: A349478 A349479 A349480 * A349482 A349483 A349484


KEYWORD

nonn


AUTHOR

Dmitry I. Ignatov, Nov 19 2021


STATUS

approved



