对称矩阵中的线性索引

Question

我们可以使用线性索引来访问矩阵，它遵循以下模式：

0 1 2

3 4 5

6 7 8

对于这种情况（n是矩阵维度），很容易获得i，j坐标。对于基于0的索引，应为：

i = index / n

j = index % n

那么，如果我的矩阵是对称的，我只想访问上半部分怎么办？

0 1 2 3

.. 4 5 6

..... 7 8

........ 9

我知道线性索引将由下式给出：

index = j + n * i - i (i-1) / 2

但我想知道给定idx时的i，j。你们知道实现这个的方法吗？我在这里查找了一下，但没有找到答案。提前致谢。

- balborian

---

在Matlab中，矩阵是行优先的，因此您的索引有误。您不能使用Matlab的本机triu函数吗？或者您真的只需要这些索引而不是上三角矩阵吗？为什么同时标记c++和Matlab？你到底在寻找什么？ - horchler

MATLAB中有一个名为ind2sub的函数，你可以试一下。 - JustinBlaber

Answer 1

如果您想使用您使用的索引方式，并且想要避免循环，您可以反转索引函数。我将使用k来表示线性索引，所有索引都是以零为基础的。正如您所指出的那样：

k = j + n*i - i*(i-1) /2.

由于我们在这里使用正整数，并且所有组合（i，j）映射到不同的k，因此该函数是可逆的。我会首先注意到：

j = k - n*i + i*(i-1)/2

如果您能找到自己所在的行，则上述方程式定义了该列。现在考虑您想要的行，其定义为

row = min{ i | k - ni + i(i-1)/2 >= 0 }.

如果您解决了二次方程k - ni + i(i-1)/2 = 0并取i的下限，则可以得到行号，即

row = floor( (2n+1 - sqrt( (2n+1)^2 - 8k ) ) / 2 )

然后

j = k - row * n + row * (row-1)/2.

在伪代码中，这将是

//Given linear index k, and n the size of nxn matrix
i = floor( ( 2*n+1 - sqrt( (2n+1)*(2n+1) - 8*k ) ) / 2 ) ;
j = k - n*i + i*(i-1)/2 ;

这样可以避免使用循环，对于大矩阵来说速度会更快

- Keeran Brabazon

---

+1 哎呀，我正想在我的循环答案中添加类似的内容。请注意，这将j作为相对于行的值。例如，当n=4,k=8时，我得到i=2,j=1。如果您想要将j作为整个矩阵的值，请将其与结果相加。 - Geobits

是的，问题在于我的索引表达式是错误的，应该是："k = j + ni - i(i-1) /2 - i"，但现在获得方程不是那么直接，因为二次方程的解是：i = floor( ( 2n-1 - sqrt( (2n-1)(2n-1) - 8*k ) ) / 2 )；而且它可能有虚根。 - balborian

Answer 2

由于还没有人发布Matlab的解决方案，这里提供一个简单的一行代码：

idxs = find(triu(true(size(A))))

给定矩阵A，该函数将返回一个向量，包含所有索引。其中，idxs(k) 返回第 k 个线性索引，指向矩阵的上三角部分。

- mbauman

Answer 3

这是对Keeran Brabazon答案的评论。 k = j + ni - i(i-1) /2 - 这是你发布的方程式，但是它是错误的，正确的方程式是k = j + (2*n -1 -i)*i/2。但我们不能用它来找到i。

你发布的方程式可以用来找到i（行索引），但我们不能将i代入你的方程式中并得到j，因此你发布的j公式是错误的，因此最终结果将如下所示：

i = floor( ( 2*n+1 - sqrt( (2n+1)*(2n+1) - 8*k ) ) / 2 ) ;（与你的版本完全相同）

j = k - (2*n-1- i)*i/2; （与你的版本不同，我通过将i代入我的方程式中得到这个结果）

- Михаил Ф.

Answer 4

循环遍历每一行，记录每一行的偏移量和每一行的起始索引：

offset = 0;
startOfRow = 0;
for(i=0;i<height;i++){
    endOfRow = startOfRow + (width - offset);
    if(idx < endOfRow){ 
        j = (idx - endOfRow) + width;
        return {i,j};
    } else {                           
        startOfRow = endOfRow;
        offset++;
    }
}

我不会Matlab，所以这只是伪代码，但应该可以工作。正如horchler所说，确保你的索引正确。我在这里使用了 i，j ，因为你在示例中使用了它，但对我来说感觉有点奇怪。

- Geobits

Answer 5

你可以使用这个

idxs = find(triu(true(size(A)))');

这是对Matt. B答案的更新，因为你想要逐行表示。

- fcdimitr

Answer 6

MATLAB附带了内置函数ind2sub和sub2ind。请查看MATLAB的文档。

请注意，在MATLAB中，线性索引沿着行向下，并且索引从1开始。

例如：对于一个3 x 3矩阵

1 4 7

2 5 8

3 6 9

- AGD

Answer 7

这是我能想到的最简单的方法：

int i = 1, j, x=n;
while (idx > x)
{
    i++;
    idx=idx-x;
    x--;
}
j=idx+(i-1);

return i, j;

- Ron Teller

Answer 8

对于以0为基础的索引：

int j = 0;
int x = (n-1);
while (idx > x) {
    j++;
    idx=idx-x;
    x--;
}
i=idx;

- user3646176