مصفوفة كوستاس

في الرياضيات ، يمكن اعتبار مصفوفة كوستاس هندسيًا مجموعة من n نقطة، تقع كل منها في مركز مربع ضمن تبليط مربع n × n ، بحيث يحتوي كل صف أو عمود على نقطة واحدة فقط، وتكون جميع متجهات الإزاحة n ( n - 1)/2 بين كل زوج من النقاط متميزة. ينتج عن ذلك دالة غموض ذاتي مثالية تشبه "دبوس الإبهام" ، مما يجعل المصفوفات مفيدة في تطبيقات مثل السونار والرادار . يمكن اعتبار مصفوفات كوستاس نظيرًا ثنائي الأبعاد لبنية مسطرة غولومب أحادية البعد ، وإلى جانب أهميتها الرياضية، لها تطبيقات مماثلة في التصميم التجريبي وهندسة رادار المصفوفات الطورية .  

سُميت مصفوفات كوستاس نسبةً إلى جون ب. كوستاس ، الذي كتب عنها لأول مرة في تقرير فني عام 1965. وفي العام نفسه، كتب إدغار جيلبرت عنها أيضًا، ناشرًا ما يُعرف الآن بطريقة ويلش اللوغاريتمية لإنشاء مصفوفات كوستاس. ^{[ 1 ]} يُعدّ التعداد العام لمصفوفات كوستاس مسألة مفتوحة في علوم الحاسوب ، كما أن إيجاد خوارزمية قادرة على حلّها في وقت متعدد الحدود لا يزال سؤالًا بحثيًا مفتوحًا .

يمكن تمثيل مصفوفة كوستاس عدديًا كمصفوفة أعداد من الرتبة n × n ، حيث يكون كل عنصر إما 1 (لوجود نقطة) أو 0 (لعدم وجود نقطة). عند تفسيرها كمصفوفات ثنائية ، تتميز هذه المصفوفات العددية بخاصية أن كل صف وعمود فيها مقيد بوجود نقطة واحدة فقط، وبالتالي فهي أيضًا مصفوفات تبديل . ومن ثم، فإن مصفوفات كوستاس لأي قيمة معطاة لـ n هي مجموعة جزئية من مصفوفات التبديل من الرتبة n .

تُعرَّف المصفوفات عادةً بأنها سلسلة من المؤشرات التي تُحدد العمود لأي صف. وبما أنه من المعلوم أن كل عمود يحتوي على عنصر واحد فقط، فمن الممكن تمثيل المصفوفة بشكل أحادي البعد. على سبيل المثال، فيما يلي مصفوفة كوستاس صالحة من الرتبة N  =  4:

${\displaystyle {\begin{array}{|c|c|c|c|}\hline 0&0&0&1\\\hline 0&0&1&0\\\hline 1&0&0&0\\\hline 0&1&0&0\\\hline \end{array}}}$  أو ببساطة  ${\displaystyle {\begin{array}{|c|c|c|c|}\hline &&&\bullet \\\hline &&\bullet &\\\hline \bullet &&&\\\hline &\bullet &&\\\hline \end{array}}}$

توجد نقاط عند الإحداثيات التالية: (1،2)، (2،1)، (3،3)، (4،4)

بما أن الإحداثي السيني يزداد خطيًا، يمكننا كتابة ذلك باختصار على أنه مجموعة جميع الإحداثيات الصادية . ويكون موضع العنصر في هذه المجموعة هو الإحداثي السيني . لاحظ أن {2، 1، 3 ، 4} يصف المصفوفة المذكورة. وهذا يُعرّف تبديلاً. وهذا يُسهّل وصف المصفوفات لترتيب مُعطى لـ N.

تُعرف أعداد مصفوفة كوستاس للأوامر من 1 إلى 29 ^{[ 2 ]} (التسلسل A008404 في OEIS ) :

فيما يلي بعض المصفوفات المعروفة:

ن = 1 {1}

N = 2 {1,2} {2,1}

N = 3 {1,3,2} {2,1,3} {2,3,1} {3,1,2}

N = 4 {1,2,4,3} {1,3,4,2} {1,4,2,3} {2,1,3,4} {2,3,1,4} {2,4,3,1} {3,1,2,4} {3,2,4,1} {3,4,2,1} {4,1,3,2} {4,2,1,3} {4,3,1,2}

N = 5 {1,3,4,2,5} {1,4,2,3,5} {1,4,3,5,2} {1,4,5,3,2} {1,5,3,2,4} {1,5,4,2,3} {2,1,4,5,3} {2,1,5,3,4} {2,3,1,5,4} {2,3,5,1,4} {2,3,5,4,1} {2,4,1,5,3} {2,4,3,1,5} {2,5,1,3,4} {2,5,3,4,1} {2,5,4,1,3} {3,1,2,5,4} {3,1,4,5,2} {3,1,5,2,4} {3,2,4,5,1} {3,4,2,1,5} {3,5,1,4,2} {3,5,2,1,4} {3,5,4,1,2} {4,1,2,5,3} {4,1,3,2,5} {4,1,5,3,2} {4,2,3,5,1} {4,2,5,1,3} {4,3,1,2,5} {4,3,1,5,2} {4,3,5,1,2} {4,5,1,3,2} {4,5,2,1,3} {5,1,2,4,3} {5,1,3,4,2} {5,2,1,3,4} {5,2,3,1,4} {5,2,4,3,1} {5,3,2,4,1}

N = 6 {1,2,5,4,6,3} {1,2,6,4,3,5} {1,3,2,5,6,4} {1,3,2,6,4,5} {1,3,6,4,5,2} {1,4,3,5,6,2} {1,4,5,3,2,6} {1,4,6,5,2,3} {1,5,3,4,6,2} {1,5,3,6,2,4} {1,5,4,2,3,6} {1,5,4,6,2,3} {1,5,6,2,4,3} {1,5,6,3,2,4} {1,6,2,4,5,3} {1,6,3,2,4,5} {1,6,3,4,2,5} {1,6,3,5,4,2} {1,6,4,3,5,2} {2,3,1,5,4,6} {2,3,5,4,1,6} {2,3,6,1,5,4} {2,4,1,6,5,3} {2,4,3,1,5,6} {2,4,3,6,1,5} {2,4,5,1,6,3} {2,4,5,3,6,1} {2,5,1,6,3,4} {2,5,1,6,4,3} {2,5,3,4,1,6} {2,5,3,4,6,1} {2,5,4,6,3,1} {2,6,1,4,3,5} {2,6,4,3,5,1} {2,6,4,5,1,3} {2,6,5,3,4,1} {3,1,2,5,4,6} {3,1,5,4,6,2} {3,1,5,6,2,4} {3,1,6,2,5,4} {3,1,6,5,2,4} {3,2,5,1,6,4} {3,2,5,6,4,1} {3,2,6,1,4,5} {3,2,6,4,5,1} {3,4,1,6,2,5} {3,4,2,6,5,1} {3,4,6,1,5,2} {3,5,1,2,6,4} {3,5,1,4,2,6} {3,5,2,1,6,4} {3,5,4,1,2,6} {3,5,4,2,6,1} {3,5,6,1,4,2} {3,5,6,2,1,4} {3,6,1,5,4,2} {3,6,4,5,2,1} {3,6,5,1,2,4} {4,1,2,6,5,3} {4,1,3,2,5,6} {4,1,6,2,3,5} {4,2,1,5,6,3} {4,2,1,6,3,5} {4,2,3,5,1,6} {4,2,3,6,5,1} {4,2,5,6,1,3} {4,2,6,3,5,1} {4,2,6,5,1,3} {4,3,1,6,2,5} {4,3,5,1,2,6} {4,3,6,1,5,2} {4,5,1,3,2,6} {4,5,1,6,3,2} {4,5,2,1,3,6} {4,5,2,6,1,3} {4,6,1,2,5,3} {4,6,1,5,2,3} {4,6,2,1,5,3} {4,6,2,3,1,5} {4,6,5,2,3,1} {5,1,2,4,3,6} {5,1,3,2,6,4} {5,1,3,4,2,6} {5,1,6,3,4,2} {5,2,3,1,4,6} {5,2,4,3,1,6} {5,2,4,3,6,1} {5,2,6,1,3,4} {5,2,6,1,4,3} {5,3,2,4,1,6} {5,3,2,6,1,4} {5,3,4,1,6,2} {5,3,4,6,2,1} {5,3,6,1,2,4} {5,4,1,6,2,3} {5,4,2,3,6,1} {5,4,6,2,3,1} {6,1,3,4,2,5} {6,1,4,2,3,5} {6,1,4,3,5,2} {6,1,4,5,3,2} {6,1,5,3,2,4} {6,2,1,4,5,3} {6,2,1,5,3,4} {6,2,3,1,5,4} {6,2,3,5,4,1} {6,2,4,1,5,3} {6,2,4,3,1,5} {6,3,1,2,5,4} {6,3,2,4,5,1} {6,3,4,2,1,5} {6,4,1,3,2,5} {6,4,5,1,3,2} {6,4,5,2,1,3} {6,5,1,3,4,2} {6,5,2,3,1,4}

تتوفر قوائم بمصفوفات كوستاس المعروفة حتى الرتبة 200، ^{[ 3 ]} والرتبة 500 ^{[ 4 ]} والرتبة 1030 ^{[ 5 ]} . على الرغم من أن هذه القوائم وقواعد البيانات الخاصة بمصفوفات كوستاس هذه تكاد تكون كاملة، فقد توجد مصفوفات كوستاس أخرى برتب أعلى من 29 غير مدرجة في هذه القوائم. بشكل عام، فإن أفضل حد أعلى معروف حاليًا لعدد${\displaystyle C(n)}$من مصفوفات كوستاس من الرتبة${\displaystyle n}$له شكل تقاربي${\displaystyle C(n)/n!\leq e^{-\Theta (n)}}$[ ^{6 ]​}

توجد عدة طرق لإنتاج مصفوفات كوستاس بشكل منهجي لقيم n كبيرة كيفما كانت . ومع ذلك، فإنها تنتج مصفوفات كوستاس لبعض قيم n فقط ، ولا تنتج جميع مصفوفات كوستاس الممكنة.

تُعرف مصفوفات كوستاس على شبكة سداسية باسم مصفوفات قرص العسل . وقد ثبت أن عدد هذه المصفوفات محدود، ويجب أن يكون عدد عناصرها فرديًا، مرتبة على شكل سداسي. حاليًا، يُعرف 12 مصفوفة من هذا النوع (مع مراعاة التناظر)، ويُعتقد أن هذا هو العدد الإجمالي. ^{[ 12 ]}

لاحظ غولومب وتايلور أن عددًا قليلًا من مصفوفات كوستاس يتميز بخاصية عدم وجود نقطتين متجاورتين قطريًا. ^{[ 8 ]} تُعرف هذه المصفوفات باسم مصفوفات كوستاس للملوك غير المهاجمين (NAKCAs)، حيث أن وضع ملك شطرنج في كل نقطة ينتج عنه تكوين لا يهاجم فيه ملكان بعضهما البعض. يتم توليد مجموعة فرعية من مصفوفات NAKCAs بشكل منهجي باستخدام صيغة معدلة من بناء ليمبل-غولومب. يُعرّف شرط أقوى مصفوفات كوستاس للملكات غير المهاجمات (NAQCAs)، وهي مصفوفات كوستاس التي تُعد أيضًا حلولًا لمسألة الملكات n . مصفوفة NAQCA الوحيدة المعروفة هي مصفوفة كوستاس البسيطة 1 × 1، ويُفترض عدم وجود غيرها. ^{[ 13 ]}

• التبديل
• مجموعة ثنائية السطوح
• التصميم التوافقي

• باركر، ل.؛ دراكاكيس، ك.؛ ريكارد، س. (2009)، "حول تعقيد التحقق من خاصية كوستاس" (ملف PDF) ، وقائع معهد مهندسي الكهرباء والإلكترونيات ، 97 (3): 586-593 ، doi : 10.1109/JPROC.2008.2011947 ، S2CID 29776660 ، مؤرشف من النسخة الأصلية (PDF) بتاريخ 25 أبريل 2012 ، تم استرجاعه بتاريخ 10 أكتوبر 2011 .
• بيرد، جيمس (مارس 2006)، "توليد مصفوفات كوستاس من الرتبة 200"، المؤتمر السنوي الأربعون لعلوم وأنظمة المعلومات لعام 2006 ، معهد مهندسي الكهرباء والإلكترونيات، doi : 10.1109/ciss.2006.286635 ، S2CID 2241386 .
• بيرد، جيمس ك. (مارس 2008)، "متعددات حدود مولد مصفوفة كوستاس في الحقول المنتهية"، المؤتمر السنوي الثاني والأربعون لعلوم وأنظمة المعلومات لعام 2008 ، معهد مهندسي الكهرباء والإلكترونيات، doi : 10.1109/ciss.2008.4558709 ، S2CID 614347 .
• بيرد، جيمس ك. (2017)، مصفوفات كوستاس والتعداد حتى الرتبة 1030 ، IEEE Dataport، doi : 10.21227/H21P42.
• بيرد، ج.؛ روسو، ج.؛ إريكسون، ك.؛ مونتيليوني، م.؛ رايت، م. (2004)، "التعاون التوافقي في مصفوفات كوستاس وتطبيقات الرادار"، مؤتمر IEEE للرادار، فيلادلفيا، بنسلفانيا (ملف PDF) ، الصفحات 260-265 ، doi : 10.1109/NRC.2004.1316432 ، S2CID 7733481 ، مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 25 أبريل 2012 ، تم استرجاعه بتاريخ 10 أكتوبر 2011  .
• بيرد، جيمس؛ روسو، جون؛ إريكسون، كيث؛ مونتيليوني، مايكل؛ رايت، مايكل (أبريل 2007)، "منهجية توليد مصفوفة كوستاس والبحث فيها" ، معاملات IEEE في أنظمة الفضاء والطيران والإلكترونيات ، 43 (2): 522-538 ، doi : 10.1109/taes.2007.4285351 ، S2CID 32271456 .
• كوستاس، جيه بي (1965)، القيود المتوسطة على تصميم وأداء السونار ، تقرير من الفئة 1 R65EMH33، شركة جنرال إلكتريك
• كوستاس، جيه بي (1984)، "دراسة لفئة من أشكال موجات الكشف ذات خصائص غموض دوبلر مثالية تقريبًا" (ملف PDF) ، وقائع معهد مهندسي الكهرباء والإلكترونيات ، 72 (8): 996-1009 ، doi : 10.1109/PROC.1984.12967 ، S2CID 2742217 ، مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 30-09-2011 ، تم استرجاعه بتاريخ 10-10-2011 .
• دراكاكيس، كونستانتينوس؛ ريكارد، سكوت؛ بيرد، جيمس ك.؛ كاباليرو، رودريغو؛ إيوريو، فرانشيسكو؛ أوبراين، غاريث؛ والش، جون (أكتوبر 2008)، "نتائج تعداد مصفوفات كوستاس من الرتبة 27"، معاملات IEEE في نظرية المعلومات ، 54 (10): 4684-4687 ، doi : 10.1109/tit.2008.928979 ، hdl : 2262/59260.
• دراكاكيس، كونستانتينوس؛ إيوريو، فرانشيسكو؛ ريكارد، سكوت (2011)، "تعداد مصفوفات كوستاس من الرتبة 28 ونتائجه"، مجلة التقدم في رياضيات الاتصالات
• دراكاكيس، كونستانتينوس؛ إيوريو، فرانشيسكو؛ ريكارد، سكوت؛ والش، جون (أغسطس 2011)، "نتائج تعداد مصفوفات كوستاس من الرتبة 29"، مجلة Advances in Mathematics of Communications ، 5 (3): 547-553 ، doi : 10.3934/amc.2011.5.547 ، hdl : 2262/59260.
• جيلبرت، إي إن (1965)، "المربعات اللاتينية التي لا تحتوي على ثنائيات متكررة"، مجلة SIAM ، 7 (2): 189-198 ، doi : 10.1137/1007035 ، MR 0179095 .
• غولومب، سولومون و. (1984)، "الإنشاءات الجبرية لمصفوفات كوستاس"، مجلة نظرية التوافيق ، السلسلة أ، 37 (1): 13-21 ، doi : 10.1016/0097-3165(84)90015-3 ، MR 0749508 .
• غولومب، سولومون و. (1992)، "الـ${\displaystyle T_{4}}$و${\displaystyle G_{4}}$"إنشاءات لمصفوفات كوستاس"، معاملات IEEE في نظرية المعلومات ، 38 (4): 1404-1406 ، doi : 10.1109/18.144726 ، MR 1168761 
• غولومب، إس دبليو ؛ تايلور، إتش. (1984)، "بناء وخصائص مصفوفات كوستاس" (ملف PDF) ، وقائع معهد مهندسي الكهرباء والإلكترونيات ، 72 (9): 1143-1163 ، doi : 10.1109/PROC.1984.12994 ، S2CID 39718506 ، مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 30-09-2011 ، تم استرجاعه بتاريخ 10-10-2011 .
• جاي، ريتشارد ك. (2004)، "القسمان C18 وF9"، مسائل غير محلولة في نظرية الأعداد (  الطبعة الثالثة)، دار نشر سبرينغر ، رقم ISBN 0-387-20860-7.
• مورينو، أوسكار (1999)، "مسح لنتائج أنماط الإشارات لتحديد موقع هدف واحد أو عدة أهداف"، في بوت، ألكسندر؛ كومار، ب. فيجاي؛ هيليسيث، تور؛ وآخرون  (محررون)، مجموعات الفرق، والمتتاليات وخصائص ارتباطها ، سلسلة معاهد العلوم المتقدمة التابعة لحلف الناتو، المجلد  542، كلوير، ص  353، ISBN 0-7923-5958-5.
• ريكارد، سكوت (2004)، "البحث عن مصفوفات كوستاس باستخدام خصائص الدورية"، المؤتمر الدولي للرياضيات في معالجة الإشارات التابع لـ IMA.
• وارنكي، لوتز؛ كوريل، بيل؛ سوانسون، كريستوفر (2023)، "كثافة مصفوفات كوستاس تتناقص أُسّيًا"، معاملات IEEE في نظرية المعلومات ، 69 (1): 575-581 ، doi : 10.1109/TIT.2022.3202507 ، MR 4544975 .

• تحدي المبرمجين في مؤتمر ماك تك 1999: مصفوفات كوستاس
• موسوعة متواليات الأعداد الصحيحة على الإنترنت :
  • A008404: عدد مصفوفات كوستاس من الرتبة n ، مع احتساب عمليات الدوران والانقلاب كعمليات منفصلة.
  • A001441: عدد مصفوفات كوستاس غير المتكافئة من الرتبة n تحت المجموعة ثنائية السطوح.
• "مصفوفة كوستاس" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]