Кіріспе

Квадраттық матрица математикада, әсіресе ықтималдықтар және комбинаторика салаларында, екі рет стохастикалық матрица (сонымен қатар бистохастикалық матрица деп аталады) – теріс емес нақты сандардан құралған квадраттық матрица, оның әрбір қатары мен бағанының қосындысы 1-ге тең, яғни:

Осылайша, екі рет стохастикалық матрица сол жақтан стохастикалық және оң жақтан стохастикалық болып табылады. Шындығында, сол және оң жақтан стохастикалық болатын кез келген матрица квадраттық болуы керек: егер әрбір қатардың қосындысы 1-ге тең болса, онда матрицадағы барлық элементтердің қосындысы қатарлар санына тең болуы керек, ал бағаналар үшін де осы ереже сақталғандықтан, қатарлар мен бағаналар саны бірдей болуы керек.) Бұл политоп – пермутациялық матрицалар жиынының дөңгелек қабығы және одан әрі, оның төбелері пермутациялық матрицалар болып табылады. Басқаша айтқанда, егер X екі рет стохастикалық матрица болса, онда оған сәйкес келетін скалярлық мәндер және пермутациялық матрицалар табылады, олар арқылы:

(X-тің мұндай жіктелуі «дөңгелек комбинация» деп аталады.) Холлдың үйлену теоремасына негізделген теореманың дәлелі төменде келтірілген. Бұл бейнелеу Біркхофф–фон Нейман жіктелуі деп аталады және бірегей болмауы мүмкін. Оны көбінесе Кёниг теоремасының нақты мәнді кеңейтілген түрі деп сипаттайды, онда сәйкестік графтардың жабыстық матрицалары арқылы орнатылады.

Басқа қасиеттері

Екі есе стохастикалық матрицалардың көбейтіндісі екі есе стохастикалық болады. Дегенмен, екі есе стохастикалық матрицаның керісі міндетті түрде екі есе стохастикалық болуы керек емес (іс жүзінде, керісі тек оң және теріс емес элементтері болса ғана екі есе стохастикалық болады). Кемелденбейтін, апериодты шекті Марков тізбегінің стационарлық таралуы біркелкі болады, егер және тек ғана оның өту матрицасы екі есе стохастикалық болса. Синкхорн теоремасы бойынша, қатаң оң элементтері бар кез келген матрицаны диагональдық матрицаларға көбейту арқылы екі есе стохастикалық етуге болады. , үшін барлық бистохастикалық матрицалар унистохастикалық және ортостохастикалық болады, бірақ үлкенірек мәндер үшін мұндай емес. Ван дер Ваерденнің болжамы бойынша, барлық n × n екі есе стохастикалық матрицалар арасындағы ең төменгі тұрақтылық , барлық элементтері тең матрицамен қол жеткізіледі. Бұл болжамды Б. Жиирс 1980 жылы және Г. П. Егорычев пен Д. И. Фаликман 1981 жылы жариялады; осы жұмысы үшін Егорычев пен Фаликман 1982 жылы Фулкерсон сыйлығын жеңіп алды.