Sunday, October 28, 2012

r-permutation matrices

Here is a fairly simple combinatorial problem that seems to have an important application. Maybe its generalizations deserve further study.

Let n be a positive integer, and r a positive divisor of n. An r-permutation matrix P of order n is a square (0,1)-matrix of order n with the following property: there is a subdivision of the row set I into a disjoint union of r-element blocks I_1, ... , I_{n/r}, and a similar subdivision of the column set J, such that  the (i,j)-entry of P is equal to 1 if and only if i \in I_s, and j \in J_s (with the same s).

Thus P has exactly r units in each row or column; in particular, for r=1, we get precisely the permutation matrices.

Claim. Suppose n is a multiple of 6. If P_3 is a  3-permutation matrix, and P_2  a 2-permutation matrix of order n, then P_3 - P_2 has at least one positive entry and at least one negative entry.  

Proof. The sum of all entries in P_3 - P_2 is equal to 3n - 2n = n, so at least one of them is positive. 

Now the number of 2-blocks in P_2 is n/2, and the number of 3-blocks in P_3 is n/3 < n/2, implying that there exists a 2-block \{i,i'\} \subset I that is not contained in a 3-block. It follows that for some j \in J, both (i,j) and (i',j)-entries of P_2 are equal to 1, while one of these entries in P_3 (say the (i,j)-entry) is 0. Then the (i,j) entry in P_3 - P_2 is -1 < 0, finishing the proof.

Is there a natural generalization?

Saturday, October 27, 2012

К столетию И.М.Гельфанда

с 28 августа по 2 сентября 2013 года в MIT состоится конференция. Интересно, что последний день конференции - 2 сентября - это истинный день рождения Израиля Моисеевича. Десять лет назад конференция в честь его 90-летия тоже закончилась 2 сентября, причем в последний день с часовым докладом выступал сам юбиляр ...

Квиддич в натуре

Я слыхал уже, что квиддич (из Гарри Поттера, кто не в курсе) становится популярной забавой, но увидел впервые сегодня, гуляя по кампусу Беркли. Все атрибуты бережно сохранены, включая комментарий прямо у кромки поля и дикий энтузиазм болельщиков. Духовой оркестр тоже не подкачал.

Но против природы не попрешь - летать на метелках ни у кого не получилось, так что симпатичные парни и девушки носились по полю с метелками, зажатыми между ног, а некоторые для верности их еще и рукой придерживали. Зрелище, вынужден признать, не слишком пристойное.    

Sunday, October 21, 2012

Самая короткая рецензия

После довольно длительного перерыва на литературу куда более низкого качества, наконец-то вернулся к Патрику ОБрайену и закончил 11-ю книжку серии: The Reverse of the Medal. А вот и обещанная рецензия: wow!!.

Тут недавно юзер авва сознался, что не удержался от слез в некотором месте этой книжки.  И я вынужден сознаться в том же, притом что ни сам не страдаю от излишней чувствительности, ни автор не склонен ни к малейшей сентиментальности. Как он добивается "total immersion" effect, отмечаемого читателями и критиками - секрет настоящей литературы. 

Edik Frenkel on his mekh-mat entrance exams in 1984

Nothing new for most of my friends of course but I still recommend a well-written and completely accurate excerpt from Edik Frenkel’s forthcoming book, Love and Math.

We walked out of the room and entered the elevator. The doors closed. It was just the two of us. The examiner was clearly in a good mood. He said: 

“You did very well. A really impressive performance. I was wondering: did you go to a special math school?” 

 I grew up in a small town, we didn’t have special math schools. 

“Really? Perhaps, your parents are mathematicians?” 

No, they are engineers. 

 “Interesting. . . . It’s the first time I’ve seen such a strong student who did not go to a special math school. 

I couldn’t believe what he was saying. This man had just failed me after an unfairly administered, discriminatory, grueling five-hour exam. For all I knew, he had killed my dream of becoming a mathematician. A sixteen-year-old student, whose only fault was that he came from a Jewish family. And now this guy is giving me compliments and expecting me to open up to him?! 

 But what could I do? Yell at him, punch him in the face? I was just standing there, silent, stunned. He continued: 

“Let me give you some advice. Apply to the Moscow Institute of Oil and Gas. They have an Applied Mathematics program, which is quite good. They take students like you there.” 

 The elevator doors opened and a minute later he handed me my thick application folder, with a bunch of my school trophies and prizes oddly sticking out of it. 

 “Good luck to you,” he said, but I was too exhausted to respond. My only wish was to get the hell out of there!

Birthday conference

Some of my Northeastern friends and colleagues are organizing a conference in relation to my birthday (terrifying number but what can one do ...). I am very grateful to them (special thanks to Ben). Here is the conference page.

All my friends including the readers of this blog are very welcome to attend or just to stop by, so please save the dates: April 24-28, 2013. 

Tuesday, October 16, 2012

Покой нам только снится

В воскресенье вечером вернулся в Беркли, а в понедельник с утра взял машину напрокат и сгонял в Дэвис сделать там доклад. Было приятно повидать несколько друзей/коллег. На снимке мы с Моникой Вазирани (courtesy of Anne Schilling who has invited me there;  many thanks to both for their warm hospitality; and the Japanese dinner place was wonderful!).



Saturday, October 13, 2012

Трижды тринадцать

Поскольку годовщина приходится на 13 число, эта вполне может считаться круглой. Сегодня, конечно, не до празднования, но может, устроим небольшую семейную прогулку.

Кстати, пару дней назад при покупке алкогольных напитков Галю попросили предъявить ее водительские права, чтобы доказать, что ей уже исполнилось  21. А вот меня что-то перестали спрашивать ... 

Friday, October 12, 2012

S.E.'s funeral

took place today at Sharon Memorial Park, a gorgeous large park in our little town.

Here is a photo collage made by Galya, Karen and Katya: a few pictures from his life.

Tuesday, October 9, 2012

Выполнил гражданский долг

Раз уж я оказался дома, сходил в наш горсовет (или поселковый совет?) и проголосовал на предстоящих выборах. Впервые за республиканских кандидатов - Ромни и Скотта Брауна. И это несмотря на мощную ЖЖ-агитацию в пользу этих кандидатов. Просто горжусь собой. :)

Кстати, как у нас принято, никаких документов ни в какой момент показать не требовалось. И ничего, небо не обвалилось. 

Monday, October 8, 2012

Back in Boston

for a week. For a very sad reason. Here is the FB posting of my son:

My maternal grandfather passed away today. He has been in very poor health for a while now. 

It is hard for me to reconcile my recent memories of him with the older ones, where he was such a smart, vibrant man. I remember being really impressed by the amount of poetry he could remember and tell wonderfully.

This picture from my wedding is how I will remember him forever.