The Inequalities of Merris and Foregger for Permanents
Conjectures on permanents are well-known unsettled conjectures in linear algebra. Let <i>A</i> be an <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>×</mo>...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-09-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/13/10/1782 |
| _version_ | 1797513145118359552 |
|---|---|
| author | Divya K. Udayan Kanagasabapathi Somasundaram |
| author_facet | Divya K. Udayan Kanagasabapathi Somasundaram |
| author_sort | Divya K. Udayan |
| collection | DOAJ |
| description | Conjectures on permanents are well-known unsettled conjectures in linear algebra. Let <i>A</i> be an <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>×</mo><mi>n</mi></mrow></semantics></math></inline-formula> matrix and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>S</mi><mi>n</mi></msub></semantics></math></inline-formula> be the symmetric group on <i>n</i> element set. The permanent of <i>A</i> is defined as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>per</mi><mi>A</mi><mo>=</mo><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>σ</mi><mo>∈</mo><msub><mi>S</mi><mi>n</mi></msub></mrow></munder></mstyle><mstyle displaystyle="true"><munderover><mo>∏</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover></mstyle><msub><mi>a</mi><mrow><mi>i</mi><mi>σ</mi><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msub><mo>.</mo></mrow></semantics></math></inline-formula> The Merris conjectured that for all <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>×</mo><mi>n</mi></mrow></semantics></math></inline-formula> doubly stochastic matrices (denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi mathvariant="sans-serif">Ω</mi><mi>n</mi></msub></semantics></math></inline-formula>), <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mi>per</mi><mi>A</mi><mo>≥</mo><mstyle displaystyle="true"><munder><mo movablelimits="false" form="prefix">min</mo><mrow><mn>1</mn><mo>≤</mo><mi>i</mi><mo>≤</mo><mi>n</mi></mrow></munder></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover></mstyle><mi>per</mi><mi>A</mi><mrow><mo>(</mo><mi>j</mi><mo>|</mo><mi>i</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>A</mi><mo>(</mo><mi>j</mi><mo>|</mo><mi>i</mi><mo>)</mo></mrow></semantics></math></inline-formula> denotes the matrix obtained from <i>A</i> by deleting the <i>j</i>th row and <i>i</i>th column. Foregger raised a question whether <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>per</mi><mo>(</mo><mi>t</mi><msub><mi>J</mi><mi>n</mi></msub><mo>+</mo><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>t</mi><mo>)</mo></mrow><mi>A</mi><mo>)</mo><mo>≤</mo><mi>per</mi><mi>A</mi></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>0</mn><mo>≤</mo><mi>t</mi><mo>≤</mo><mfrac><mi>n</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></mfrac></mrow></semantics></math></inline-formula> and for all <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>A</mi><mo>∈</mo><msub><mi mathvariant="sans-serif">Ω</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>J</mi><mi>n</mi></msub></semantics></math></inline-formula> is a doubly stochastic matrix with each entry <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mfrac><mn>1</mn><mi>n</mi></mfrac></semantics></math></inline-formula>. The Merris conjecture is one of the well-known conjectures on permanents. This conjecture is still open for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>4</mn></mrow></semantics></math></inline-formula>. In this paper, we prove the Merris inequality for some classes of matrices. We use the sub permanent inequalities to prove our results. Foregger’s inequality is also one of the well-known inequalities on permanents, and it is not yet proved for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>5</mn></mrow></semantics></math></inline-formula>. Using the concepts of elementary symmetric function and subpermanents, we prove the Foregger’s inequality for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>=</mo><mn>5</mn></mrow></semantics></math></inline-formula> in [0.25, 0.6248]. Let <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>σ</mi><mi>k</mi></msub><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> be the sum of all subpermanents of order <i>k</i>. Holens and Dokovic proposed a conjecture (Holen–Dokovic conjecture), which states that if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>A</mi><mo>∈</mo><msub><mi mathvariant="sans-serif">Ω</mi><mi>n</mi></msub><mo>,</mo><mi>A</mi><mo>≠</mo><msub><mi>J</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula> and <i>k</i> is an integer, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mi>n</mi><mo>,</mo></mrow></semantics></math></inline-formula> then <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>σ</mi><mi>k</mi></msub><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow><mo>≥</mo><mfrac><msup><mrow><mo>(</mo><mi>n</mi><mo>−</mo><mi>k</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow><mn>2</mn></msup><mrow><mi>n</mi><mi>k</mi></mrow></mfrac><msub><mi>σ</mi><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msub><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. In this paper, we disprove the conjecture for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>=</mo><mi>k</mi><mo>=</mo><mn>4</mn></mrow></semantics></math></inline-formula>. |
| first_indexed | 2024-03-10T06:10:35Z |
| format | Article |
| id | doaj.art-96032e4957c84eca8c1f6e9cba32246b |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-10T06:10:35Z |
| publishDate | 2021-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-96032e4957c84eca8c1f6e9cba32246b2023-11-22T20:09:01ZengMDPI AGSymmetry2073-89942021-09-011310178210.3390/sym13101782The Inequalities of Merris and Foregger for PermanentsDivya K. Udayan0Kanagasabapathi Somasundaram1Department of Mathematics, Amrita School of Engineering, Amrita Vishwavidyapeetham, Coimbatore 641112, IndiaDepartment of Mathematics, Amrita School of Engineering, Amrita Vishwavidyapeetham, Coimbatore 641112, IndiaConjectures on permanents are well-known unsettled conjectures in linear algebra. Let <i>A</i> be an <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>×</mo><mi>n</mi></mrow></semantics></math></inline-formula> matrix and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>S</mi><mi>n</mi></msub></semantics></math></inline-formula> be the symmetric group on <i>n</i> element set. The permanent of <i>A</i> is defined as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>per</mi><mi>A</mi><mo>=</mo><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>σ</mi><mo>∈</mo><msub><mi>S</mi><mi>n</mi></msub></mrow></munder></mstyle><mstyle displaystyle="true"><munderover><mo>∏</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover></mstyle><msub><mi>a</mi><mrow><mi>i</mi><mi>σ</mi><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msub><mo>.</mo></mrow></semantics></math></inline-formula> The Merris conjectured that for all <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>×</mo><mi>n</mi></mrow></semantics></math></inline-formula> doubly stochastic matrices (denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi mathvariant="sans-serif">Ω</mi><mi>n</mi></msub></semantics></math></inline-formula>), <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mi>per</mi><mi>A</mi><mo>≥</mo><mstyle displaystyle="true"><munder><mo movablelimits="false" form="prefix">min</mo><mrow><mn>1</mn><mo>≤</mo><mi>i</mi><mo>≤</mo><mi>n</mi></mrow></munder></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover></mstyle><mi>per</mi><mi>A</mi><mrow><mo>(</mo><mi>j</mi><mo>|</mo><mi>i</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>A</mi><mo>(</mo><mi>j</mi><mo>|</mo><mi>i</mi><mo>)</mo></mrow></semantics></math></inline-formula> denotes the matrix obtained from <i>A</i> by deleting the <i>j</i>th row and <i>i</i>th column. Foregger raised a question whether <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>per</mi><mo>(</mo><mi>t</mi><msub><mi>J</mi><mi>n</mi></msub><mo>+</mo><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>t</mi><mo>)</mo></mrow><mi>A</mi><mo>)</mo><mo>≤</mo><mi>per</mi><mi>A</mi></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>0</mn><mo>≤</mo><mi>t</mi><mo>≤</mo><mfrac><mi>n</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></mfrac></mrow></semantics></math></inline-formula> and for all <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>A</mi><mo>∈</mo><msub><mi mathvariant="sans-serif">Ω</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>J</mi><mi>n</mi></msub></semantics></math></inline-formula> is a doubly stochastic matrix with each entry <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mfrac><mn>1</mn><mi>n</mi></mfrac></semantics></math></inline-formula>. The Merris conjecture is one of the well-known conjectures on permanents. This conjecture is still open for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>4</mn></mrow></semantics></math></inline-formula>. In this paper, we prove the Merris inequality for some classes of matrices. We use the sub permanent inequalities to prove our results. Foregger’s inequality is also one of the well-known inequalities on permanents, and it is not yet proved for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>5</mn></mrow></semantics></math></inline-formula>. Using the concepts of elementary symmetric function and subpermanents, we prove the Foregger’s inequality for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>=</mo><mn>5</mn></mrow></semantics></math></inline-formula> in [0.25, 0.6248]. Let <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>σ</mi><mi>k</mi></msub><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> be the sum of all subpermanents of order <i>k</i>. Holens and Dokovic proposed a conjecture (Holen–Dokovic conjecture), which states that if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>A</mi><mo>∈</mo><msub><mi mathvariant="sans-serif">Ω</mi><mi>n</mi></msub><mo>,</mo><mi>A</mi><mo>≠</mo><msub><mi>J</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula> and <i>k</i> is an integer, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mi>n</mi><mo>,</mo></mrow></semantics></math></inline-formula> then <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>σ</mi><mi>k</mi></msub><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow><mo>≥</mo><mfrac><msup><mrow><mo>(</mo><mi>n</mi><mo>−</mo><mi>k</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow><mn>2</mn></msup><mrow><mi>n</mi><mi>k</mi></mrow></mfrac><msub><mi>σ</mi><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msub><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. In this paper, we disprove the conjecture for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>=</mo><mi>k</mi><mo>=</mo><mn>4</mn></mrow></semantics></math></inline-formula>.https://www.mdpi.com/2073-8994/13/10/1782doubly stochastic matricespermanentMerris conjectureForegger’s inequality |
| spellingShingle | Divya K. Udayan Kanagasabapathi Somasundaram The Inequalities of Merris and Foregger for Permanents Symmetry doubly stochastic matrices permanent Merris conjecture Foregger’s inequality |
| title | The Inequalities of Merris and Foregger for Permanents |
| title_full | The Inequalities of Merris and Foregger for Permanents |
| title_fullStr | The Inequalities of Merris and Foregger for Permanents |
| title_full_unstemmed | The Inequalities of Merris and Foregger for Permanents |
| title_short | The Inequalities of Merris and Foregger for Permanents |
| title_sort | inequalities of merris and foregger for permanents |
| topic | doubly stochastic matrices permanent Merris conjecture Foregger’s inequality |
| url | https://www.mdpi.com/2073-8994/13/10/1782 |
| work_keys_str_mv | AT divyakudayan theinequalitiesofmerrisandforeggerforpermanents AT kanagasabapathisomasundaram theinequalitiesofmerrisandforeggerforpermanents AT divyakudayan inequalitiesofmerrisandforeggerforpermanents AT kanagasabapathisomasundaram inequalitiesofmerrisandforeggerforpermanents |