Матрицы с определителем 1

[mihiv]

В журнале Am.math.monthly видел такую задачу:дано $2^{n^2}$ матриц размера $n{\times}n$,с элементами $1$и$0$, найти или оценить N(1,n),т.е. число матриц с определителем $1$.Задача публиковалась давно и м.б. уже решена,мне известна только оценка

$$N(1,n)\geqslant\frac34n!2^{\frac{n(n-1)}2}$$

[maxal]

A086264

[Утундрий]

Он там только численно и всего лишь до $n=6$...

[maxal]

Потому что это сложная открытая проблема.

[Утундрий]

Сразу бы предупредили... убил полночи и часть утра напрасно)

[maxal]

Утундрий
Ну почему же напрасно? Если посчитаете для $n=7$ - уже будет результат, а как минимум в OEIS вы будете упомянуты...

[mihiv]

Получается,что это еще одна задача из серии задач с простой формулировкой и сложным решением, типа задачи $3n+1$

[green5]

И решить в виде рекурентной функии?

[green5]

Тех вопрос по GAP
gap>Size(SL(4,2))/2
10080

Это что за число? (число матриц с дет 1? вроде нет)

[maxal]

green5 в сообщении #226443 писал(а):

Тех вопрос по GAP
gap>Size(SL(4,2))/2
10080

Это что за число? (число матриц с дет 1? вроде нет)

Почему нет?
SL(4,2) - это группа матриц размером $4\times 4$ над $\mathbb{Z}_2$ с единичным определителем.
Ее порядок можно вычислить так:

$$(2^4 - 2^0) (2^4-2^1)(2^4-2^2)(2^4-2^3)=20160$$

Половина этого числа как раз равна 10080 - так что, GAP прав.

[green5]

Но ведь если по теме, то число матриц 4x4 с элементами 0 или 1, с детерм.=1 равно 10020
[0,1] не Z2?
Где то торможу (:

Ну да это 10020(det=1)+60(det=3)
Если переопределить умножение матриц C=A*B: c[i][j]= sum(a[i][k]*b[k][j]) mod 2
то что это за группа?

[green5]

Задача N(n) аналогична N(n+1) c элементами -1,1

[Mathusic]

mihiv в сообщении #185098 писал(а):

В журнале Am.math.monthly видел такую задачу:дано $2^{n^2}$ матриц размера $n{\times}n$,с элементами $1$и$0$, найти или оценить N(1,n),т.е. число матриц с определителем $1$.Задача публиковалась давно и м.б. уже решена,мне известна только оценка

$$N(1,n)\geqslant\frac34n!2^{\frac{n(n-1)}2}$$

Так эта оценка для любых $n$? Где можно посмотреть доказательство?

maxal в сообщении #185668 писал(а):

Потому что это сложная открытая проблема.

Так она состоит в оценке (в первом посте есть) или точном нахождении $ N(1,n)$ ?

[Бодигрим]

Хорошо бы точно решить.

[maxal]

Докажите, что количество $n\times n$ (0,1)-матриц с единичным перманентом равно количеству ациклических направленных графов, умноженному на $n!$.