I have a sparse matrix with 100 rows and, when I do a Gauss decomposition, I get a matrix with 90 rows. But if I remove tha last row of the first matrix, now with 99 rows, and I do a Gauss decomposition, I get a matrix with 92 rows. And if I add that last row back to this matrix, now with 93 rows, and do a Gauss decomposition, I get a matrix with 93 rows. Is this possible?
I was thinking that maybe the first matrix had 10 groups of rows that are linearly dependend, and the last row belongs to two of these groups, so when I remove it, the rank increases by two. And when I do a Gauss decomposition, some lines in these groups cancel each other, and now the last row is not linearly dependent anoymore.
I ask because I checked my algorithm for erros a couple of times, it's just a Gauss decomposition, I don't know what I could be doing wrong.
edit: code is not small, and I can't find a small example with the problem, but here it is anyway:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace RankTest
{
class Program
{
static void Main(string[] args)
{
int[] ij = { -665, 661, 662, -678, 999, -140, 135, 138, -151, -346, 999, -20, 15, 17, -21, -26, -353, -566, 999, -120, 115, 117, -124, 999, -570, 565, 567, -617, 999, -595, 591, 592, -673, 999, -190, 186, 188, -194, -259, -399, 999, -25, 20, 23, -29, 999, -555, 550, 553, -596, 999, -495, 490, 493, -498, -516, -663, 999, -125, 121, 122, -128, -181, -253, -313, 999, -475, 471, 472, -491, -656, 999, -465, 461, 462, -496, -521, -661, 999, -91, -107, -162, -700, 999, -335, 331, 332, -386, 999, -240, 236, 237, -289, 999, -10, 5, 8, -14, -294, -609, 999, -505, 501, 503, -512, 999, -100, 95, 97, -102, -579, 999, -380, 376, 377, -384, -634, 999, -660, 656, 657, -679, 999, -610, 606, 607, -689, 999, -520, 515, 517, -524, 999, -360, 356, 357, -363, -563, 999, -540, 536, 537, -546, -586, 999, -620, 615, 617, 999, -545, 541, 542, -593, 999, -655, 651, 652, -680, 999, -15, 11, 13, -19, -299, -559, 999, -515, 510, 513, -526, -591, 999, -15, 11, 12, -19, -299, -559, 999, -555, 551, 553, -597, 999, -665, 660, 663, -678, 999, -126, -186, -252, -311, -698, 999, -635, 631, 633, 999, -240, 235, 237, -288, 999, -75, 70, 72, -79, -82, -99, -134, 999, -70, 65, 67, -74, 999, -610, 605, 607, 999, -180, 175, 177, -249, 999, -460, 455, 457, -463, -508, 999, -605, 600, 603, -690, 999, -535, 531, 532, -553, 999, -75, 71, 73, -79, -82, -99, -134, 999, -85, 81, 83, -89, 999, -315, 311, 312, -326, -401, 999, -395, 390, 393, -414, 999, -590, 585, 587, -669, 999, -585, 581, 583, -639, 999, -360, 355, 358, -363, -563, 999, -650, 646, 647, -681, 999, -285, 281, 283, -434, 999, -175, 170, 172, -179, -319, 999, -130, 125, 127, -183, 999, -25, 20, 22, -28, 999, -125, 120, 123, -128, -181, -253, -313, 999, -50, 45, 48, -53, -63, -66, -138, 999, -425, 421, 423, -427, -482, -654, 999, -345, 341, 343, -377, 999, -675, 670, 672, 999, -70, 65, 68, -73, 999, -305, 301, 303, -359, 999, -305, 301, 302, -359, 999, -70, 66, 68, -74, 999, -440, 436, 437, -456, 999, -20, 16, 17, -22, -27, -354, -567, 999, -545, 541, 543, -594, 999, -520, 515, 518, -523, 999, -155, 150, 153, -158, -343, -576, 999, -190, 185, 187, -194, -259, -399, 999, -260, 255, 257, -267, 999, -207, -217, -436, -467, -695, 999, -630, 626, 627, -685, 999, -665, 660, 662, 999, -30, 26, 27, -33, -148, 999, -150, 146, 147, -153, -348, -571, 999, -170, 165, 168, -174, 999, -520, 516, 518, -524, 999, -365, 361, 363, -369, 999, -320, 316, 317, -323, -333, -583, 999, -315, 310, 312, -327, -402, 999, -206, -216, -437, -466, -695, 999, -170, 166, 168, -174, 999, -20, 15, 18, -22, -27, -354, -567, 999, -600, 596, 598, -672, 999, -590, 585, 588, -668, 999, -470, 466, 468, -472, 999, -615, 610, 612, 999, -400, 395, 398, -406, 999, -595, 590, 592, -674, 999, -605, 601, 602, -690, 999, -415, 411, 413, -419, 999, -485, 481, 482, -488, 999, -660, 656, 658, 999, -190, 185, 188, -193, -258, -398, 999, -275, 270, 273, -428, 999, -405, 400, 402, -408, 999, -510, 505, 508, -514, -549, -589, 999, -405, 400, 403, -408, 999, -80, 75, 78, -84, 999, -515, 510, 512, -527, -592, 999, -615, 611, 613, 999, -540, 535, 537, -547, -587, 999, -505, 500, 502, -512, 999, -235, 231, 233, -239, -287, -504, -539, 999, -670, 665, 667, 999, -415, 410, 413, -418, 999, -280, 276, 278, -282, -452, -477, 999, -245, 241, 243, -247, -582, 999, -370, 365, 367, -373, -621, 999, -551, -692, 999, -600, 595, 598, -671, 999, -205, 200, 203, -209, -212, -439, -469, 999, -185, 180, 183, -188, 999, -480, 476, 478, -487, -652, 999, -225, 220, 223, -229, 999, -290, 285, 288, -533, 999, -225, 221, 223, -229, 999, -295, 291, 293, -302, -357, -612, 999, -110, 106, 108, -114, -117, -244, -309, 999, -55, 50, 53, -56, -573, 999, -120, 115, 118, -123, 999, -120, 116, 118, -124, 999, -330, 325, 327, -392, -417, -642, 999, -355, 350, 352, -367, 999, -590, 586, 588, -669, 999, -365, 360, 363, -368, 999, -52, -61, -71, -136, -702, 999, -605, 601, 603, 999, -100, 95, 98, -101, -578, 999, -500, 496, 498, -519, 999, -75, 70, 73, -78, -81, -98, -133, 999, -285, 280, 282, -433, 999, -600, 596, 597, -671, 999, -550, 545, 548, -599, 999, -455, 450, 452, -459, -474, 999, -80, 76, 78, -84, 999, -430, 426, 428, -484, 999, -195, 190, 193, -199, -204, -279, 999, -660, 655, 658, -679, 999, -345, 340, 343, -376, 999, -160, 155, 157, -171, -338, 999, -525, 520, 522, -529, -542, -667, 999, -225, 220, 222, -228, 999, -95, 91, 92, -176, 999, -10, 6, 7, -14, -294, -609, 999, -390, 386, 387, -394, -412, -644, 999, -15, 10, 13, -19, -299, -559, 999, -355, 351, 353, -367, 999, -127, -187, -251, -312, -698, 999, -195, 191, 193, -199, -204, -279, 999, -370, 365, 368, -374, -622, 999, -115, 110, 112, -118, 999, -560, 555, 557, -562, -614, 999, -640, 636, 638, 999, -60, 55, 58, -104, 999, -520, 516, 517, -523, 999, -400, 395, 397, -407, 999, -50, 46, 47, -53, -63, -66, -138, 999, -410, 405, 407, -422, -647, 999, -490, 486, 487, -493, -658, 999, -475, 470, 472, -492, -657, 999, -435, 431, 433, -454, 999, -485, 480, 483, -488, 999, -610, 605, 608, -689, 999, -5, 0, 2, -24, -32, -569, 999, -25, 21, 23, -29, 999, -380, 376, 378, -384, -634, 999, -400, 396, 398, -407, 999, -140, 136, 137, -151, -346, 999, -670, 666, 667, -677, 999, -30, 25, 28, -33, -148, 999, -265, 261, 263, -269, 999, -405, 401, 402, -408, 999, -450, 445, 447, -462, 999, -445, 441, 443, -507, 999, -350, 345, 347, -372, 999, -290, 285, 287, -534, 999, -460, 455, 458, -464, -509, 999, -395, 390, 392, -413, 999, -420, 416, 417, -423, -648, 999, -635, 630, 633, -684, 999, -35, 31, 32, -58, 999, -635, 631, 632, -684, 999, -540, 536, 538, -547, -587, 999, -360, 356, 358, -364, -564, 999, -270, 266, 268, -272, -284, -432, -479, 999, -120, 116, 117, -123, 999, -191, -256, -397, -697, 999, -160, 156, 158, -172, -339, 999, -675, 671, 672, -676, 999, -650, 645, 648, -681, 999, -155, 151, 153, -159, -344, -577, 999, -545, 540, 542, -594, 999, -40, 36, 37, -44, 999, -110, 105, 108, -114, -117, -244, -309, 999, -215, 210, 212, -219, 999, -295, 290, 292, -302, -357, -612, 999, -385, 381, 382, -389, -637, 999, -405, 401, 403, -409, 999, -455, 450, 453, -458, -473, 999, -280, 275, 278, -281, -451, -476, 999, -245, 241, 242, -246, -581, 999, -375, 370, 372, -378, -626, 999, -295, 291, 292, -301, -356, -611, 999, -180, 175, 178, -248, 999, -375, 371, 373, -379, -627, 999, -275, 271, 272, -428, 999, -370, 366, 367, -374, -622, 999, -445, 440, 442, -507, 999, -490, 485, 487, -494, -659, 999, -135, 131, 132, -156, -341, 999, -675, 671, 673, 999, -11, -291, -607, -705, 999, -280, 276, 277, -281, -451, -476, 999, -115, 111, 113, -119, 999, -105, 100, 103, -169, 999, -555, 551, 552, -596, 999, -270, 265, 267, -271, -283, -431, -478, 999, -210, 206, 207, -214, 999, -465, 460, 462, -497, -522, -662, 999, -310, 305, 307, -322, -332, 999, -455, 451, 453, -459, -474, 999, -110, 106, 107, -114, -117, -244, -309, 999, -355, 351, 352, -366, 999, -305, 300, 302, -358, 999, -35, 30, 32, -59, 999, -145, 141, 142, -146, -351, 999, -300, 295, 297, -304, -362, 999, -580, 576, 578, -629, 999, -530, 525, 528, -543, 999, -30, 26, 28, -34, -149, 999, -650, 646, 648, 999, -160, 156, 157, -171, -338, 999, -236, -501, -531, -537, -693, 999, -205, 201, 202, -209, -212, -439, -469, 999, -580, 576, 577, -628, 999, -55, 51, 52, -56, -573, 999, -615, 611, 612, -688, 999, -470, 465, 467, -472, 999, -310, 306, 307, -321, -331, 999, -325, 321, 322, -328, -403, 999, -230, 226, 227, -233, 999, -525, 520, 523, -528, -541, -666, 999, -490, 485, 488, -493, -658, 999, -265, 260, 263, -269, 999, -8, -603, -707, 999, -410, 406, 407, -421, -646, 999, -565, 561, 562, -618, 999, -560, 556, 558, -562, -614, 999, -670, 666, 668, 999, -425, 420, 422, -426, -481, -653, 999, -395, 391, 392, -414, 999, -625, 620, 622, 999, -105, 101, 103, -169, 999, -465, 460, 463, -496, -521, -661, 999, -580, 575, 577, -629, 999, -50, 45, 47, -54, -64, -67, -139, 999, -360, 355, 357, -364, -564, 999, -340, 335, 338, -381, -631, 999, -575, 570, 572, -624, 999, -640, 636, 637, -683, 999, -9, -604, -691, -707, 999, -85, 80, 82, -89, 999, -655, 651, 653, 999, -320, 316, 318, -324, -334, -584, 999, -580, 575, 578, -628, 999, -185, 181, 182, -188, 999, -170, 165, 167, -173, 999, -140, 136, 138, -152, -347, 999, -365, 361, 362, -368, 999, -535, 531, 533, -554, 999, -260, 256, 258, -267, 999, -530, 525, 527, -543, 999, -535, 530, 533, -553, 999, -485, 481, 483, -489, 999, -645, 641, 642, -682, 999, -105, 100, 102, -168, 999, -7, -602, -706, 999, -620, 616, 618, 999, -390, 386, 388, -394, -412, -644, 999, -285, 280, 283, -434, 999, -660, 655, 657, 999, -510, 505, 507, -513, -548, -588, 999, -645, 641, 643, 999, -335, 330, 333, -386, 999, -5, 1, 3, -24, -32, -569, 999, -390, 385, 387, -393, -411, -643, 999, -220, 216, 218, -224, -227, -444, -449, 999, -560, 556, 557, -561, -613, 999, -605, 600, 602, 999, -255, 250, 253, -261, 999, -470, 466, 467, -471, 999, -620, 615, 618, -687, 999, -640, 635, 638, -683, 999, -450, 446, 447, -461, 999, -185, 180, 182, -189, 999, -350, 346, 348, -372, 999, -610, 606, 608, 999, -410, 406, 408, -422, -647, 999, -290, 286, 288, -534, 999, -440, 435, 437, -457, 999, -340, 335, 337, -382, -632, 999, -6, -601, -706, 999, -570, 566, 567, -616, 999, -130, 125, 128, -184, 999, -40, 36, 38, -44, 999, -620, 616, 617, -687, 999, -475, 470, 473, -491, -656, 999, -60, 56, 58, -104, 999, -575, 570, 573, -623, 999, -380, 375, 377, -383, -633, 999, -630, 626, 628, 999, -510, 506, 508, -514, -549, -589, 999, -25, 21, 22, -29, 999, -485, 480, 482, -489, 999, -192, -257, -396, -697, 999, -585, 581, 582, -638, 999, -640, 635, 637, 999, -330, 326, 327, -391, -416, -641, 999, -165, 160, 163, -166, -316, -336, 999, -175, 171, 172, -178, -318, 999, -10, 5, 7, -13, -293, -608, 999, -90, 85, 88, -93, -108, -163, 999, -410, 405, 408, -421, -646, 999, -75, 71, 72, -78, -81, -98, -133, 999, -145, 140, 142, -147, -352, 999, -225, 221, 222, -229, 999, -635, 630, 632, 999, -500, 495, 497, -518, 999, -250, 246, 247, -264, 999, -440, 435, 438, -456, 999, -135, 131, 133, -157, -342, 999, -45, 40, 43, -48, 999, -196, -202, -277, -696, 999, -235, 230, 232, -239, -287, -504, -539, 999, -470, 465, 468, -471, 999, -240, 236, 238, -289, 999, -250, 246, 248, -264, 999, -15, 10, 12, -18, -298, -558, 999, -4, -36, -46, -141, -703, 999, -385, 381, 383, -389, -637, 999, -95, 90, 93, -176, 999, -230, 225, 228, -233, 999, -12, -292, -606, -705, 999, -76, -86, -97, -131, -701, 999, -490, 486, 488, -494, -659, 999, -237, -502, -532, -536, -693, 999, -95, 90, 92, -177, 999, -575, 571, 573, -624, 999, -415, 410, 412, -419, 999, -575, 571, 572, -623, 999, -77, -87, -96, -132, -701, 999, -310, 305, 308, -321, -331, 999, -350, 346, 347, -371, 999, -395, 391, 393, -414, 999, -320, 315, 318, -323, -333, -583, 999, -265, 260, 262, -268, 999, -140, 135, 137, -152, -347, 999, -565, 560, 562, -619, 999, -200, 195, 197, -274, 999, -515, 511, 512, -526, -591, 999, -51, -62, -72, -137, -702, 999, -3, -37, -47, -142, -703, 999, -510, 506, 507, -514, -549, -589, 999, -585, 580, 583, -638, 999, -615, 610, 613, -688, 999, -425, 421, 422, -427, -482, -654, 999, -565, 561, 563, -619, 999, -5, 0, 3, -23, -31, -568, 999, -495, 490, 492, -498, -516, -663, 999, -480, 476, 477, -486, -651, 999, -390, 385, 388, -394, -412, -644, 999, -550, 545, 547, -598, 999, -630, 625, 628, -685, 999, -500, 495, 498, -518, 999, -655, 650, 652, 999, -675, 670, 673, -676, 999, -325, 321, 323, -329, -404, 999, -165, 160, 162, -167, -317, -337, 999, -150, 145, 147, -154, -349, -572, 999, -550, 546, 547, -599, 999, -245, 240, 242, -247, -582, 999, -340, 336, 338, -382, -632, 999, -455, 451, 452, -458, -473, 999, -45, 41, 43, -49, 999, -125, 121, 123, -129, -182, -254, -314, 999, -270, 266, 267, -272, -284, -432, -479, 999, -50, 46, 48, -54, -64, -67, -139, 999, -655, 650, 653, -680, 999, -550, 546, 548, -599, 999, -595, 590, 593, -673, 999, -435, 431, 432, -453, 999, -160, 155, 158, -171, -338, 999, -340, 336, 337, -381, -631, 999, -65, 61, 62, -69, 999, -445, 440, 443, -506, 999, -355, 350, 353, -366, 999, -325, 320, 323, -328, -403, 999, -135, 130, 132, -157, -342, 999, -210, 206, 208, -214, 999, -125, 120, 122, -129, -182, -254, -314, 999, -130, 126, 128, -184, 999, -670, 665, 668, -677, 999, -585, 580, 582, -639, 999, -425, 420, 423, -427, -482, -654, 999, -275, 271, 273, -429, 999, -645, 640, 642, 999, -215, 210, 213, -218, 999, -450, 445, 448, -461, 999, -460, 456, 457, -464, -509, 999, -420, 415, 418, -423, -648, 999, -40, 35, 38, -44, 999, -320, 315, 317, -324, -334, -584, 999, -35, 30, 33, -58, 999, -515, 511, 513, -527, -592, 999, -111, -121, -242, -306, -699, 999, -665, 661, 663, 999, -445, 441, 442, -506, 999, -10, 6, 8, -14, -294, -609, 999, -105, 101, 102, -169, 999, -430, 425, 428, -484, 999, -85, 81, 82, -88, 999, -295, 290, 293, -301, -356, -611, 999, -345, 341, 342, -376, 999, -85, 80, 83, -88, 999, -330, 326, 328, -392, -417, -642, 999, -190, 186, 187, -193, -258, -398, 999, -540, 535, 538, -546, -586, 999, -100, 96, 97, -101, -578, 999, -220, 215, 218, -223, -226, -443, -448, 999, -90, 86, 88, -94, -109, -164, 999, -530, 526, 527, -543, 999, -245, 240, 243, -246, -581, 999, -130, 126, 127, -184, 999, -645, 640, 643, -682, 999, -221, -231, -442, -446, -694, 999, -35, 31, 33, -59, 999, -380, 375, 378, -384, -634, 999, -545, 540, 543, -593, 999, -385, 380, 382, -388, -636, 999, -630, 625, 627, 999, -220, 216, 217, -223, -226, -443, -448, 999, -60, 56, 57, -104, 999, -435, 430, 432, -454, 999, -625, 621, 623, 999, -600, 595, 597, -672, 999, -65, 60, 62, -68, 999, -20, 16, 18, -22, -27, -354, -567, 999, -45, 40, 42, -49, 999, -420, 416, 418, -424, -649, 999, -260, 256, 257, -266, 999, -235, 231, 232, -238, -286, -503, -538, 999, -525, 521, 523, -529, -542, -667, 999, -150, 146, 148, -154, -349, -572, 999, -315, 311, 313, -327, -402, 999, -350, 345, 348, -371, 999, -450, 446, 448, -462, 999, -115, 110, 113, -119, 999, -275, 270, 272, -429, 999, -205, 201, 203, -209, -212, -439, -469, 999, -65, 61, 63, -69, 999, -250, 245, 247, -263, 999, -185, 181, 183, -189, 999, -430, 425, 427, -483, 999, -90, 86, 87, -93, -108, -163, 999, -65, 60, 63, -69, 999, -475, 471, 473, -492, -657, 999, -590, 586, 587, -668, 999, -230, 225, 227, -234, 999, -595, 591, 593, -674, 999, -30, 25, 27, -34, -149, 999, -420, 415, 417, -424, -649, 999, -290, 286, 287, -533, 999, -560, 555, 558, -561, -613, 999, -112, -122, -241, -307, -699, 999, -300, 296, 297, -303, -361, 999, -80, 75, 77, -83, 999, -200, 196, 198, -274, 999, -210, 205, 208, -214, 999, -650, 645, 647, 999, -500, 496, 497, -518, 999, -555, 550, 552, -597, 999, -305, 300, 303, -359, 999, -40, 35, 37, -43, 999, -565, 560, 563, -618, 999, -375, 371, 372, -379, -627, 999, -335, 331, 333, -387, 999, -325, 320, 322, -328, -403, 999, -215, 211, 213, -219, 999, -70, 66, 67, -73, 999, -2, -16, -39, -42, -144, -296, -557, -704, 999, -552, -692, 999, -150, 145, 148, -153, -348, -571, 999, -80, 76, 77, -84, 999, -570, 566, 568, -617, 999, -570, 565, 568, -616, 999, 4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, 59, 64, 69, 74, 79, 84, 89, 94, 99, 104, 109, 114, 119, 124, 129, 134, 139, 144, 149, 154, 159, 164, 169, 174, 179, 184, 189, 194, 199, 204, 209, 214, 219, 224, 229, 234, 239, 244, 249, 254, 259, 264, 269, 274, 279, 284, 289, 294, 299, 304, 309, 314, 319, 324, 329, 334, 339, 344, 349, 354, 359, 364, 369, 374, 379, 384, 389, 394, 399, 404, 409, 414, 419, 424, 429, 434, 439, 444, 449, 454, 459, 464, 469, 474, 479, 484, 489, 494, 499, 504, 509, 514, 519, 524, 529, 534, 539, 544, 549, 554, 559, 564, 569, 574, 579, 584, 589, 594, 599, 604, 609, 614, 619, 624, 629, 634, 639, 644, 649, 654, 659, 664, 669, 674, 675, 676, 677, 678, 679, 680, 681, 682, 683, 684, 685, 686, 687, 688, 689, 690, 691, 692, 693, 694, 695, 696, 697, 698, 699, 700, 701, 702, 703, 704, 705, 706, 999, -480, 475, 478, -486, -651, 999, -525, 521, 522, -528, -541, -666, 999, -205, 200, 202, -208, -211, -438, -468, 999, -370, 366, 368, -374, -622, 999, -365, 360, 362, -369, 999, -625, 620, 623, -686, 999, -505, 500, 503, -511, 999, -170, 166, 167, -174, 999, -1, -17, -38, -41, -143, -297, -556, -704, 999, -100, 96, 98, -102, -579, 999, -480, 475, 477, -487, -652, 999, -345, 340, 342, -377, 999, -210, 205, 207, -213, 999, -197, -201, -276, -696, 999, -135, 130, 133, -156, -341, 999, -145, 140, 143, -146, -351, 999, -165, 161, 162, -166, -316, -336, 999, -45, 41, 42, -48, 999, -180, 176, 177, -248, 999, -95, 91, 93, -177, 999, -375, 370, 373, -379, -627, 999, -92, -106, -161, -700, 999, -165, 161, 163, -167, -317, -337, 999, -385, 380, 383, -389, -637, 999, -235, 230, 233, -238, -286, -503, -538, 999, -180, 176, 178, -249, 999, -530, 526, 528, -544, 999, -430, 426, 427, -484, 999, -200, 195, 198, -273, 999, -155, 150, 152, -158, -343, -576, 999, -265, 261, 262, -269, 999, -465, 461, 463, -497, -522, -662, 999, -230, 226, 228, -234, 999, -175, 171, 173, -179, -319, 999, -270, 265, 268, -272, -284, -432, -479, 999, -315, 310, 313, -326, -401, 999, -5, 1, 2, -23, -31, -568, 999, -505, 501, 502, -511, 999, -255, 251, 252, -261, 999, -435, 430, 433, -453, 999, -90, 85, 87, -94, -109, -164, 999, -495, 491, 493, -499, -517, -664, 999, -222, -232, -441, -447, -694, 999, -310, 306, 308, -322, -332, 999, -240, 235, 238, -289, 999, -260, 255, 258, -266, 999, -535, 530, 532, -554, 999, -195, 191, 192, -199, -204, -279, 999, -400, 396, 397, -406, 999, -110, 105, 107, -113, -116, -243, -308, 999, -495, 491, 492, -498, -516, -663, 999, -250, 245, 248, -264, 999, -625, 621, 622, -686, 999, -280, 275, 277, -282, -452, -477, 999, -55, 50, 52, -57, -574, 999, -335, 330, 332, -387, 999, -215, 211, 212, -218, 999, -155, 151, 152, -158, -343, -576, 999, -175, 170, 173, -178, -318, 999, -115, 111, 112, -119, 999, -145, 141, 143, -147, -352, 999, -415, 411, 412, -418, 999, -55, 51, 53, -57, -574, 999, -255, 251, 253, -262, 999, -285, 281, 282, -434, 999, -300, 295, 298, -303, -361, 999, -460, 456, 458, -464, -509, 999, -200, 196, 197, -273, 999, -195, 190, 192, -198, -203, -278, 999, -60, 55, 57, -103, 999, -440, 436, 438, -457, 999, -300, 296, 298, -304, -362, 999, -255, 250, 252, -262, 999, -220, 215, 217, -224, -227, -444, -449, 999, -330, 325, 328, -391, -416, -641, 999 };
var M = new LongMatrix();
int row = 0;
for (int i = 0; i < ij.Length; i++)
{
if (ij[i] == 999)
row++;
else if (ij[i] >= 0)
M.set(row, ij[i], 1);
else
M.set(row, -ij[i] - 1, -1);
}
int lastRow = M.Rows.Count - 1;
var A = new LongMatrix();
var B = new LongMatrix();
for (int i = 0; i < lastRow; i++)
foreach (var pair in M.Rows[i])
{
A.set(i, pair.Key, pair.Value);
B.set(i, pair.Key, pair.Value);
}
foreach (var pair in M.Rows[lastRow])
A.set(lastRow, pair.Key, pair.Value);
A.decompose();
B.decompose();
int rankA = A.lastRow();
int rankB = B.lastRow();
foreach (var pair in M.Rows[lastRow])
B.set(lastRow, pair.Key, pair.Value);
B.decompose();
int rankB2 = B.lastRow();
Console.WriteLine("rankA: " + rankA);
Console.WriteLine("rankB: " + rankB);
Console.WriteLine("rankB2: " + rankB2);
Console.ReadLine();
// Result: 528 530 531
}
/// <summary>
/// A sparse matrix.
/// </summary>
class LongMatrix
{
/// <summary>
/// Each row is a map (column, value).
/// Each column is a map (row, value).
/// </summary>
public class Line : Dictionary<int, long>
{
public Line() { }
public Line(Line line) : base(line) { }
}
public List<Line> Rows;
private List<Line> Columns;
public LongMatrix()
{
Rows = new List<Line>();
Columns = new List<Line>();
}
public void set(int row, int column, long value)
{
if (value == 0)
{
clear(row, column);
return;
}
while (Rows.Count <= row)
Rows.Add(new Line());
Rows[row][column] = value;
while (Columns.Count <= column)
Columns.Add(new Line());
Columns[column][row] = value;
}
public long get(int row, int column)
{
long rowValue = 0;
if (row < Rows.Count)
if (Rows[row].ContainsKey(column))
rowValue = Rows[row][column];
// todo: remove after it works
long columnValue = 0;
if (column < Columns.Count)
if (Columns[column].ContainsKey(row))
columnValue = Columns[column][row];
if (rowValue != columnValue)
throw new Exception();
return rowValue;
}
public void clear(int row, int column)
{
if (row < Rows.Count)
{
if (Rows[row].ContainsKey(column))
Rows[row].Remove(column);
}
if (column < Columns.Count)
{
if (Columns[column].ContainsKey(row))
Columns[column].Remove(row);
}
}
public void swapRows(int row1, int row2)
{
if (row1 == row2)
return;
var R1 = Rows[row1];
var R2 = Rows[row2];
// Walk through R1 updating the information in the columns
foreach (var pair in R1)
{
int column = pair.Key;
var C = Columns[column];
if (C.ContainsKey(row2))
{
// Element in both rows, swap.
C[row1] = C[row2];
C[row2] = pair.Value;
}
else
{
C.Add(row2, pair.Value);
C.Remove(row1);
}
}
// Walk through R2 updating the information in the columns
foreach (var pair in R2)
{
int column = pair.Key;
var C = Columns[column];
if (C.ContainsKey(row1))
{
// Element in both rows. Do nothing, already swapped them.
}
else
{
C.Add(row1, pair.Value);
C.Remove(row2);
}
}
// Swaps the rows
Rows[row1] = R2;
Rows[row2] = R1;
}
public void decompose()
{
// Can't change the column while going through it,
// so store the rows here.
var tmpColumn = new List<int>();
int r = 0;
for (int c = 0; c < Columns.Count; c++)
{
if (!findPivot(r, c))
// Tries the next column, same row.
continue;
var pivot = get(r, c);
tmpColumn.Clear();
foreach (var pair in Columns[c])
tmpColumn.Add(pair.Key);
foreach (var row2 in tmpColumn)
{
if (row2 != r)
{
var k = get(row2, c);
foreach (var pair in Rows[r])
{
int c2 = pair.Key;
long value = get(row2, c2) * pivot - pair.Value * k;
set(row2, c2, value);
}
}
}
r++;
}
}
private List<int> candidates = new List<int>();
public bool findPivot(int row, int column)
{
candidates.Clear();
foreach (var pair in Columns[column])
{
// Can't use rows above the diagonal.
if (pair.Key >= row)
candidates.Add(pair.Key);
}
if (candidates.Count == 0)
return false;
if (candidates.Count == 1)
{
swapRows(row, candidates[0]);
return true;
}
long minValue = long.MaxValue;
int bestRow = -1;
// It's a sparse matrix, so I check every pair of rows
// for a pivot that will keep the values in the matrix lowest.
for (int i = 0; i < candidates.Count; i++)
{
int row1 = candidates[i];
var R1 = Rows[row1];
long pivot = get(row1, column);
long rowValue = -1;
for (int j = i + 1; j < candidates.Count; j++)
{
int row2 = candidates[j];
var R2 = Rows[row2];
long k = get(row2, column);
foreach (var pair in R1)
{
int c2 = pair.Key;
long value = get(row2, c2) * pivot - pair.Value * k;
if (Math.Abs(value) > rowValue)
rowValue = Math.Abs(value);
}
}
if (rowValue < minValue)
{
bestRow = row1;
if (rowValue == 1)
// Doesn't get better than this
break;
minValue = rowValue;
}
}
swapRows(row, bestRow);
return true;
}
public int lastRow()
{
for (int i = Rows.Count - 1; i >= 0; i--)
if (Rows[i].Count != 0)
return i;
return -1;
}
}
}
}