О булевых матрицах полного факторизационного ранга

Я. Н. Шитов

?

О булевых матрицах полного факторизационного ранга

Математический сборник. 2013. Т. 204. № 11. С. 151–160.

Шитов Я. Н.

Показано, что каждая (0,1)-матрица размера n×m, имеющая булев ранг n, содержит столбец, в котором по крайней мере sqrt(n)/2-1 элементов равны нулю. Доказано, что приведенная оценка является асимптотически оптимальной. В качестве приложения полученных результатов показано, что булевы матрицы полного ранга не могут иметь сколь угодно большого размера при условии ограниченности их тропических или минорных рангов.

Приоритетные направления: компьютерно-математическое

Язык: русский

Полный текст

Текст на другом сайте

Ключевые слова: 01-матрица булев ранг

A Three-Party W-State Quantum Secret Sharing Protocol with X-Gate Encoding and Forbidden-Outcome Detection

Терегулов Т. Р., Лубенец Е. Р., / Series Quantum Physics "arXiv". 2026. No. 2609.31472.

Добавлено: 28 сентября 2026 г.

On calibration of remote sensing retrievals of ecosystem respiration (Reco) with tower measurements over,Russian forests and wetlands

Shabanov N., Kuricheva O., Kurbatova J. и др., / Series Working Papers SSRN "Department of Economics Ca’ Foscari University of Venice". 2026.

Добавлено: 21 августа 2026 г.

Three Algorithms for Merging Hierarchical Navigable Small World Graphs

Пономаренко А. А., / Series Computer Science "arxiv.org". 2025.

Добавлено: 30 июля 2026 г.

Growth in noncommutative algebras and entropy in derived categories

Пионтковский Д. И., / Series arXiv "math". 2026.

Добавлено: 23 июня 2026 г.

Multilinear nilalgebras and the Jacobian theorem

Пионтковский Д. И., / Series arXiv "math". 2025.

Добавлено: 23 июня 2026 г.

ML-based Fast Simulation of FARICH Responses

Шипилов Ф. А., Barnyakov A., Ivanov A. и др., / Series Physics "arxiv.org". 2026.

Добавлено: 19 мая 2026 г.

Natural hazard database from Internet publications: text mining with a large language model

Деркачева А. А., Сакиркина М. А., Краев Г. Н. и др., /. 2026.

Добавлено: 28 апреля 2026 г.

Algorithmic overlaps as thermodynamic variables: from local to cluster Monte Carlo dynamics in critical phenomena

Пиле Я. Э., Deng Y., Щур Л. Н., / Series arXiv "math". 2026. No. 2604.10254.

Добавлено: 20 апреля 2026 г.

Using predefined vector systems to speed up neural network multimillion class classification

Gabdullin N., Андросов И. А., / Series Computer Science "arxiv.org". 2026.

Добавлено: 2 апреля 2026 г.

Iterative Ricci-Foster Curvature Flow with GMM-Based Edge Pruning: A Novel Approach to Community Detection

Сорокин К. С., Бекетов М. Е., Онучин А. и др., / arxiv.org. Серия cs.SI "Social and Information Networks ". 2025.

Обнаружение сообществ в сложных сетях — фундаментальная проблема, открытая для новых подходов в различных научных областях. Мы представляем новый метод обнаружения сообществ, основанный на потоке Риччи на графах. Наша техника итеративно обновляет веса ребер (их метрические длины) в соответствии с их (комбинаторной) версией кривизны Риччи Фостера, вычисленной на основе эффективного расстояния сопротивления между узлами. Известно, ...

Добавлено: 15 января 2026 г.

On the determinant of a sparse 0-1 matrix

Шитов Я. Н., Linear Algebra and its Applications 2018 Vol. 554 P. 49–50

Добавлено: 30 января 2019 г.

Конституция России-неоднозначность матрицы развития

Мазаев В. Д., Вестник Саратовской государственной юридической академии 2018 № 3(122) С. 47–53

Статья посвящена характеристике результатов действия Конституции РФ как правового акта и как прогностического документа. Сегодня многие проблемы реализации Конституции РФ обусловлены переоценкой либеральнодемократических ценностей образца 1993 года. Конституционная матрица общественно-политического строя в современных условиях требует дальнейшего осмысления, превращения в более действенный инструмент развития страны с учетом особенностей собственного национального государства и общемировых трендов. ...

Добавлено: 14 декабря 2018 г.

On the determinant of a sparse 0-1 matrix

Шитов Я. Н., Linear Algebra and its Applications 2018 Vol. 554 P. 49–50

Добавлено: 26 сентября 2018 г.

On Boolean matrices with full factor rank

Шитов Я. Н., Sbornik Mathematics 2013 Vol. 204 No. 11 P. 1691–1699

It is demonstrated that every (0, 1)-matrix of size n×m having Boolean rank n contains a column with at least √n/2 − 1 zero entries. This bound is shown to be asymptotically optimal. As a corollary, it is established that the size of a full-rank Boolean matrix is bounded from above by a function of ...

Добавлено: 20 января 2014 г.