. متن داده‌شده را خلاصه کن

متن: ۱) قضیه هال (صورت ماتریسی): ماتریس m یک ماتریس m× n با درایه‌های صفر و یک است. در این صورت در هر سطر آن یک عدد ۱ وجود دارد و در هیچ ستونی بیش از یک عدد ۱ وجود ندارد اگر و تنها اگر برای هر مجموعه از سطرها (مثلا r تایی) تعداد ستون‌هایی که ۱ های این سطرها در آن‌ها قرار دارند، حد اقل برابر r باشد. ۲) یک خانواده از مجموعه‌ها به صورت {s= {a ۱، a ۲، a ۳، …، an را در نظر می‌گیریم. مجموعه p را نیز یصورت زیر فرض می‌کنیم: p زیر مجموعه a ۱ ∪a ۲ ∪ … ∪an حال sدارای یک مجموعه نماینده‌های متمایز شامل مجموعه p است اگر و تنها اگر: الف) s یک مجموعه نماینده‌های متمایز داشته باشد. ب) برای هر داشته باشیم: لم: فرض کنید l، مستطیل لاتین p × q شامل درایه‌های {۲ ٬ ۱، …، n} باشد. اگر دو عدد صحیح باشند، آنگاه تعداد اعضای مجموعه {۲ ٬ ۱، …، n} که دقیقا m بار در l آمده و در همه r سطر اول ظاهر شده‌اند بیشتر از نمی‌باشند. قضیه ۱: هر مستطیل لاتین n×p را می‌توان به مربع لاتین n×n گسترش داد اثبات: فرض کنیم l مستطیل لاتین n×p باشد. برای هر n>i> ۱ تعریف می‌کنیم: یافتن یک سطر اضافی از اعضای مجموعه {۳ ٬ ۲، ۱ …n} برای تبدیل l به مستطیل لاتینیp+ ۱) ×n) در واقع معادل یافتن یک مجموعه نماینده‌های متمایز از خانواده {s= {a ۱، a ۲، a ۳، …، an است. طبق قضیه هال اجتماع هر r تا از این مجموعه‌ها حداقل شامل r عضو متمایز است که n>r> ۱. قبل از ارائه استدلال به دو نکته اشاره می‌کنیم. ۱) a ۱ | = |a ۲ | = |a ۳ | = … = |an| = n - p| چون هر کدام از این مجموعه‌ها شامل عضوهایی از مجموعه {۳ ٬ ۲، ۱ …n} است که در ستون p عضوی مربوط به آن نیامده‌اند. ۲) به ازای هر n>j> ۱ عدد j در دقیقا n - p مجموعه از خانواده s وجود دارد. زیرا j در دقیقا p مکان l ظاهر می‌شود (p ستون مختلف). پس در n - p ستون وجود ندارد و بنا بر تعریف aiها درn-p مجموعه مختلف ظاهر می‌شود. هر خانواده از مجموعه‌ها مانند s با ویژگی‌های مذکور باید یک مجموعه نماینده‌های متمایز داشته باشد. r مجموعه از خانواده s را در نظر گرفته و ثابت می‌کنیم شامل حد اقل r عضو متمایز است. ابتدا همه اعضای r مجموعه مفروز را (با در نظر گرفتن اعضای تکراری) در یک لیست ردیف می‌کنیم. (r (n – p عضو بدست می‌آید. چون شامل (r (n-p عضو است. به همین ترتیب می‌توان با ادامه این رویه به مربع لاتین n×n رسید. پس (p - l (i …
خلاصه:
مربع لاتین یک آرایهٔ مربعی (ماتریس مربعی) است که در هر سطر و هر ستون آن اعضای مجموعه a به‌طور کامل و بدون تکرار قرار داشته باشند . مثال : در احتمالات ماتریس « متغیر تصادفی دوگانه » (که حاصل جمع هر سطر و ستون آن یک است) یک مربع لاتین است . حال در مورد مستطیل‌ها و مربع‌هایی بحث می‌کنیم که درایه‌های آن اعداد صحیح و مثبت هستند . یک مستطیل لاتین a با ابعاد p×q عبارت است از : یک ماتریس p × q که هر یک از درایه‌های آن عضو مجموعه { ۳٬۲ ، ۱ …n } بوده و هیچ عضو تکراری در سطر یا ستون آن به وجود نیاید . مستطیل لاتین اول می‌تواند به مربع لاتین گسترش پیدا می‌کند .