Вопрос по матрицам

[tac]

Добрый день, помогите с такой задачей ..
если сразу не сможете ответить, то хотя бы дайте наметки ... Матрица А - бинарная, т.е. состоит из нулей и единиц. Нужно вычислить вероятность того, что она не будет особенной в зависимости от ее размера. Перебор здесь не подходит, нужно оценить аналитически, хотя бы приблизительно ... В принципе вопрос можно переформулировать ... и спросить, какое возможно максимально число различных матриц, у которых определитель равен нулю, если знать, что матрица бинарная и определенного размера ... может быть какие-нибудь законы симметрии подойдут - незнаю ... например, для матрицы 2х2 можно перебрать 16 вариантов - и сказать, что 10 матриц являются особенными (определитель равен нулю), а 6 неособенные ... но вот для размера 3х3 - уже 512 вариантов так просто не переберешь .. а если учесть, что меня интересуют матрицы гиганских размеров не менее 1000х1000, то становится жутко ... но приблизительно какой процент из них особенных знать очень хочется ..

Всем спасибо, кто примет участие в обсуждении ...

[Yu_K]

Поработайте с двоиными строками - всего строк 2^n длины n. Дальше посчитайте число комбинаций по n из этого набора и ищите те которые линейнонезависимы.

http://www.research.att.com/~njas/sequences/Seis.html - да кстати здесь есть эта последовательность (кол-во невыржденных двоичных матриц n*n).

[tac]

Yu_K писал(а):

Поработайте с двоиными строками - всего строк 2^n длины n. Дальше посчитайте число комбинаций по n

Это мне совершенно понятно ...

Yu_K писал(а):

из этого набора и ищите те которые линейнонезависимы.

http://www.research.att.com/~njas/sequences/Seis.html - да кстати здесь есть эта последовательность (кол-во невыржденных двоичных матриц n*n).

А вот это если можите поясните, пожалуйсто, как можно подробнее ... честно говоря "там" я ничего не понял ...

[Yu_K]

http://www.research.att.com/~njas/sequences/A002884

Для размерности 3*3 - выбираем любую ненулевую строку на первое место - всего 7 вариантов, на второе место можем поставить любую из 6 оставшихся, а дальше нужно выбросить линейно зависимые с ними - и из них выбрать одну - получится 7*6*4. Может это не совсем хороший подход - но для начала и для понимания можно начать с этого. И про перманенты поищите материалы.

[tac]

Yu_K писал(а):

http://www.research.att.com/~njas/sequences/A002884

Для размерности 3*3 - выбираем любую ненулевую строку на первое место - всего 7 вариантов, на второе место можем поставить любую из 6 оставшихся, а дальше нужно выбросить линейно зависимые с ними - и из них выбрать одну - получится 7*6*4. Может это не совсем хороший подход - но для начала и для понимания можно начать с этого. И про перманенты поищите материалы.

Постепенно начинает доходить здесь http://www.research.att.com/~njas/seque ... 2884&fmt=4 как раз расчитанно число неособенных матриц ... а что это вообще за сайт, в смысле чем они там занимаются ... это какие-то базы данных математические ?
Спасибо - это уже хорошо ...

Теперь бы разобраться как это получается ...

там приводятся такие формулы Product(2^n-2^i, i=0..n-1); or 2^(n*(n-1)/2) * product( 2^i - 1, i=1..n)

что такое Product() ?

Как получится 7*6*4, все равно не понял ... 7 почему ? 2^3 - 1 - это и есть ненулевая строка ?

на второе место можем поставить любую из 6 оставшихся - это всегда на один меньше или специфично для размера 3х3

"а дальше нужно выбросить линейно зависимые с ними" - а это как делать ? почему 4 ?

Например, для размера 4х4, как я понимаю будет 4 сомножителя ... первый вроде как 2^4 - 1 = 15

Второй что 14 ? А дальше ?

[Yu_K]

Цитата:

в смысле чем они там занимаются ...

Most people use this web site to get information about a particular number sequence. If you are a new visitor, then you might ask the database if it can recognize your favorite sequence, if you have one. To do this, go to the main look-up page. (Of course, the number sequence should be well-defined, of general interest and ideally it should be infinite. Short sequences such as phone numbers are not appropriate.)

If your sequence isn't in the database, and if it is interesting, please submit it using the web page for contributing a new sequence or comment.

If you have stumped the database, you can try Superseeker, which tries really hard to identify a sequence.

You can browse the database, using the WebCam. This can be set to look at the most interesting sequences, recent additions, or sequences needing more terms. It can be quite addictive.

It is interesting to scan the Index to the database to see the variety of topics that are covered. In a way this database can be regarded as an index to all of science. It is like a dictionary or fingerprint file for number sequences.

Also worth visiting are the pages dealing with Puzzle sequences, Classic sequences and Hot sequences. и тд. Когда здесь появится Максим он может подробней рассказать, чем они там занимаются....

Цитата:

что такое Product() ?

- а Вы как думаете?

.......

Цитата:

А дальше ?

- попробуйте сами подумать дальше.

[tac]

Yu_K писал(а):

Цитата:

что такое Product() ?

- а Вы как думаете?

Ну, откуда я интересно могут догадаться ? А что такое PRST() - как вы думаете ?

Добавлено спустя 5 минут 9 секунд:

Yu_K писал(а):

Цитата:

А дальше ?

- попробуйте сами подумать дальше.

Ну, если трудно объяснить ... то хотя бы сказали бы правильно ли я думаю в конкретных вопросах , ответы на которые я сам предположил выше ...

[Yu_K]

http://www.anekdot.ru/scripts/author.php?o=o2&a1=PRST - это ник одного мужика, который анекдоты у Димы Вернера рассказывает. Но это уже оффтоп и флуд - придет модератор и тему загонит в карантин - и обидется на Вас за то, что Вы его заставляете работать.

[tac]

Yu_K писал(а):

Цитата:

что такое Product() ?

- а Вы как думаете?

Произведение что ли ?

Добавлено спустя 1 час 4 минуты 28 секунд:

Ура ! Дошло ...

Для случая 6х6 .. = 63*62*60*56*48*32

вырисовывается простая формула ...



В общем виде:

$$P = \frac {\prod^{n-1}_{i=0} (2^n-2^i)} {2^{n*n}} = \frac {2^{n*(n-1)/2} * \prod^{n}_{i=1} (2^i -1)} {2^{n*n}} $$

Помогите сократить ... наверное как-то можно на 2^n

вроде как

$$P = \frac {\prod^{n}_{i=1} (2^i -1)} {2^{(n^2+n)/2}} $$

Правильно ? ( А еще больше нельзя никак сократить ? например для случаев n>10)

До завтра попробую сформулировать еще один супер пупер вопрос ... очень прошу помогите ... а то дальше я уж точно не сображу ...

Yu_K отдельное спасибо за помощь

Итак, Exel смог сосчитать до случая 44х44, уже после n>30, вероятность практически стабильная и очень медленно уменьшается ... Кому интересно P = 28,8788 % и с точностью до этих знаков похоже не изменится даже при n>1000000 ...

Теперь ВАЖНОЕ усложнение ... Рассмотрим случай 30х30, там вероятность, что матрица будет не особенной P = 28,8788 %. Но это при равновероятном исходе ... как изменится эта вероятность, если гарантировать, что в матрице находится хотя бы m единиц ... например, если случай 2х2 и m=1, то общие число вариантов сокращается с 16 до 15 ... а вот если m=2 и т.д. что изменится ? при этом мы не знаем в каких именно местах эти единицы будут ...

[tac]

С делителем вроде разобрался ... делим на число из распределения Бернулли ... т.е. для случая 2х2, имеем распределение в зависимости от m -> (1,4,6,4,1)

а вот с тем на что делить похуже для случая 2х2 можно перебрать и получить следующие распределение (0, 0, 2, 4, 0) ... а вот как формулу то написать ???

[Jnrty]

Jnrty:

tac, подправьте, пожалуйста, формулы в своём сообщении. Чтобы они правильно отображались, их нужно окружать знаками доллара (одиночными или двойными; многоэтажные формулы лучше двойными, чтобы символы были не слишком мелкими).

[tac]

Ok. Догадаться очень трудно ...

[tac]

Ау ..

я тут подсчитал в МатЛабе для варианта 3х3 число особенных матриц - дало 174, а по формуле получается 168 ... как так может быть ? Формула не точна ? Или у меня с программкой проблемы ... хотя тогда скорее с МатЛабом ... вроде все проверил ...

[ИСН]

Как надо было считать, чтобы возникли проблемы с нахождением числа 7*6*4 ?

[tac]

ИСН писал(а):

Как надо было считать, чтобы возникли проблемы с нахождением числа 7*6*4 ?

Да, в том-то и дело, что это не 7*6*4, МатЛаб однозначно из 512 вариантов возможных матриц дает 174 матрицы у которых детерминант не равен нулю, т.е. не 168 !!!