Let $A$ be a $3\times 3$ matrix with characteristic polynomial $x^3-3x+a$ for what values of $a$ given matrix must be diagonal.

Let $ A$ be a $ 3\times 3$ matrix with characteristic polynomial $ x^3-3x+a$ for what values of $ a$ given matrix must be diagonal.

Efforts:

If a matrix has distinct eigenvalues, then matrix is diagonalizable. But how can I use this information.

I also know that if char. polynomial is $ x^3+a_2x^2+a_1x+a_0$ , then $ -a_2=\mbox{trace}(A) \mbox{ and } -a_0=\det(A).$

I am not able to proceed.

Can someone please give a hint?

Thanks.

Replacing non-negative entries of a complex diagonal matrix with zeros

Let $ \Lambda_r$ be a real-valued diagonal matrix containing negative elements. We can replace the negative elements with zeros this way $ $ \frac{\Lambda_r + \lvert \Lambda_r \rvert}{2}$ $

Let $ \Lambda_c$ be complex-valued diagonal. If at all possible, is there any equation similar to the above which will include $ \lvert \Lambda_c \rvert$ in order to replace the negative entries with zeros?

If $D$ is a diagonal matrix, when is the commutator $DA – AD$ full rank?

Suppose $ A \in \mathbb{C}^{n \times n}$ is full rank. I’m looking for a sufficient condition on $ A$ such that for some diagonal matrix $ D \in \mathbb{C}^{n \times n}$ , the commutator $ D A – A D$ is full rank.

I’ve worked out some necessary conditions- $ A$ and $ D$ cannot share an eigenvector, so no column of $ D$ can have $ n-1$ zero indices (ie, no column of $ A$ is a scaled column of the identity matrix).

For $ n=2$ , \begin{align} DA – A D &= \begin{bmatrix} 0 & (d_1 – d_2) a_{1,2} \ (d_2 – d_1) a_{2, 1} & 0 \end{bmatrix}\ \det(DA – AD) &= (d_1-d_2)^2 a_{1,2} a_{2,1}, \end{align} so a $ a_{1,2}, a_{2,1} \neq 0$ is both necessary and sufficient.

But for $ n=3$ ,

\begin{align} DA – A D &= \begin{bmatrix} 0 & (d_1 – d_2) a_{1,2} & (d_1 – d_3) a_{1, 3} \ (d_2 – d_1) a_{2, 1} & 0 & (d_2 – d_3) a_{2, 3} \ (d_3 – d_1) a_{3, 1} & (d_3 – d_2) a_{3, 2} & 0 \end{bmatrix}\ \det(DA – AD) &= (d_1-d_2)(d_1-d_3)(d_2-d_3) (a_{1,2} a_{2,3} a_{3,1} – a_{1,3}a_{2,1}a_{3,2}). \end{align} So if $ (a_{1,2} a_{2,3} a_{3,1} – a_{1,3}a_{2,1}a_{3,2})=0$ , $ DA – AD$ is rank deficient regardless of the choice of $ D$ .

Q1: Is there a geometric interpretation for the constraint $ (a_{1,2} a_{2,3} a_{3,1} – a_{1,3}a_{2,1}a_{3,2}) \neq 0$ ?

Q2: I don’t get a factored form of the determinant (one term depending on $ D$ , one term on $ A$ ) for $ n > 3$ . Is $ n=3$ a special case?

Q3: Is there a sufficient condition on $ A$ such that $ DA – AD$ is full rank for $ n>3$ ?

I’d prefer to not assume $ A$ is positive definite.

Diagonal Difference of a 2D matrix

How should I fix my code such that it will pass all corner cases not just some in HackerRank?

#!/bin/python3  import math import os import random import re import sys  # Complete the diagonalDifference function below. def diagonalDifference(arr):     sum_diag1 = 0     sum_diag2 = 0     arr_2d = []     print(arr)      for i in range(len(arr)):         for j in range(len(arr)):             if i==j:                 sum_diag1 += arr[i][j]             elif i+j == (len(arr)) - 1:                 sum_diag2 += arr[i][j]                 print(arr[i][j])       return abs(sum_diag1 - sum_diag2)  if __name__ == '__main__':     fptr = open(os.environ['OUTPUT_PATH'], 'w')      n = int(input())      arr = []      for _ in range(n):         arr.append(list(map(int, input().rstrip().split())))      result = diagonalDifference(arr)      fptr.write(str(result) + '\n')      fptr.close() 

Algorithm for searching based on diagonal entries

V0  V1  V2  V3  V4  V5  V6  V7  V8  V9 

V0 1 1 1 0 0 0 0 0 0 0 V1 0 55 0 -1 -1 0 0 0 0 0 V2 0 0 5 0 0 1 1 0 0 0 V3 0 0 0 5 0 0 0 -1 0 0 V4 0 0 0 0 5 0 0 -1 0 0 V5 0 0 0 0 0 5 0 -1 1 0 V6 0 0 0 0 0 0 5 0 1 0 V7 0 0 0 0 0 0 0 5 0 -1 V8 0 0 0 0 0 0 0 0 55 -1 V9 0 0 0 0 0 0 0 0 0 5

I need an algorithm to display result like this: Subgraph1: V0,V1 Subgraph2: V2,V5,V6,V8 SubGraph3: V3,V4, V7, V9.

Multiplying N x N matrices using Diagonal storage

This question is a part of my research. I am trying to multiply two N X N matrices which are stored diagonally. I implemented the following algorithm for this purpose which is working correctly but the problem is it is taking way too much time. For example, To multiply 1000 x 1000 matrices, it is taking almost 26 minutes. I am giving an small example for better understanding of what I am trying to accomplish.

Matrix A = [ 1 2 3 4 ], Matrix B =[ 5 6 7 8], diagArrayA= [1 4 2 3] (Elements stored diagonally in the order main diagonal – super diagonal -sub diagonal), diagArrayB = [5 8 6 7] (Same as above),

Result = A X B = [ 19 50 22 43] (Correct output) The code for multiply function is followed: (The problem seems to be in this function). I will appreciate any comment on the problem/code.

void multiplyDiag(vector <float> diagArrayA, vector <float> diagArrayB){                cout << "function called " << endl;            //please declare as array             // float *a=cutDiagElement(getArray(diagArrayA,-1),0,0);          //   cout << "Value : " << a[0];         vector <float> result;         result.resize(n*n);       float total_time=0.0;       // const int sum=n*(n+1)/2; 

for(int k=0; k<=n-1;k++) { //1

             int start_index=k*n-k*(k-1)/2;               //cout << start_index;             //  int stop_index=start_index+n-k-1;            for(int i=k+1; i<=n-1; i++){ //2                  vector <float> diag_a1=cutDiagElement(getArray(diagArrayA,k-i),0,k);                 // cout << diag_a1[0] <<endl;                   vector <float> diag_b1=cutDiagElement(getArray(diagArrayB,i),0,0);                     int length1=diag_b1.size();                   //  int length1=n-i;                     // length1=length1-0-0;                   //cout << length1;                    float start1=clock();                   for(int j=0; j<=length1-1;j++)                       { //3                               //cout << "OK";                       result[start_index+i-k+j]+=diag_a1[j]*diag_b1[j];                          } //3                   float end1=clock();                   total_time=total_time+(end1-start1);                      vector <float> diag_a2=cutDiagElement(getArray(diagArrayA, i), 0, 0);                    vector <float> diag_b2= cutDiagElement(getArray(diagArrayB,k-i), k, 0);                    //  cout << diag_b2[0];                 //  int length2=diag_a2.size();                     float start2=clock();                    for(int j=0; j<=length1-1;j++)                        { //4                                 result[start_index+j]+=diag_a2[j]*diag_b2[j];                                //  cout<< multiply_result[start_index+j] << endl;                          }    //4                    float end2=clock();                  total_time=total_time+(end2-start2);          } //2     for(int i=0; i<=k; i++)      { //5              vector <float> diag_a3=cutDiagElement(getArray(diagArrayA, i), 0, k-i);                vector <float> diag_b3 = cutDiagElement(getArray(diagArrayB, k-i), i, 0);                int length3=diag_a3.size();              //   int length3=n-i;                //  length3=length3-(k-i);                float start3=clock();                  for(int j=0; j<=length3-1;j++){ //6                                             result[start_index+j]+=diag_a3[j]*diag_b3[j];                                               //cout<< multiply_result[start_index+j] << endl;                                }  //6             float end3=clock();           total_time=total_time+(end3-start3);       } //5 

}//1

// computing sub diagonal

for(int k=1; k<=n-1; k++) { //7

    int start_index=n*(n+1)/2+(k-1)*n-k*(k-1)/2;       // int stop_index=start_index+n-k-1;     for(int i=k+1; i<=n-1; i++)      { //8               vector <float> diag_a1=cutDiagElement(getArray(diagArrayA, -i), 0, 0);                vector <float> diag_b1= cutDiagElement(getArray(diagArrayB, i-k), 0, k);                int length1=diag_b1.size();               // int length1=n-(i-k);                 //   length1=length1-k;                float start4=clock();                for(int j=0; j<=length1-1;j++){ //9                            result[start_index+i+j-k]+=diag_a1[j]*diag_b1[j];                       } //9                  float end4=clock();                   total_time=total_time+(end4-start4);                   vector <float> diag_a2=cutDiagElement(getArray(diagArrayA, i-k), k, 0);                   vector <float> diag_b2= cutDiagElement(getArray(diagArrayB,-i), 0, 0);                 // int length2=diag_a2.size();                  float start5=clock();                   for(int j=0; j<=length1-1;j++)                            { //10                               result[start_index+j]+=diag_a2[j]*diag_b2[j];                            }//10                       float end5=clock();                 total_time=total_time+(end5-start5);        } //8     for(int i=0; i<=k; i++)                { //11                     vector <float> diag_a3=cutDiagElement(getArray(diagArrayA, -i), k-i, 0);                       vector <float> diag_b3 = cutDiagElement(getArray(diagArrayB, i-k), 0, i);                        int length3=diag_a3.size();                      //     int length3=n-i;                        //     length3=length3-(k-i);                      float start6=clock();                      for(int j=0; j<=length3-1;j++){ //12                                             result[start_index+j]+=diag_a3[j]*diag_b3[j];                                }  //12                    float end6=clock();                   total_time=total_time+(end6-start6);                   } //11 

} //7

cout << “time :” << (total_time) / CLOCKS_PER_SEC*1000 <

           cout << result[x] << endl;             } 

}

Multiplying N x N matrices using Diagonal storage

This question is a part of my research. I am trying to multiply two N X N matrices which are stored diagonally. I implemented the following algorithm for this purpose which is working correctly but the problem is it is taking way too much time. For example, To multiply 1000 x 1000 matrices, it is taking almost 26 minutes. I am giving an small example for better understanding of what I am trying to accomplish.

Matrix A = [ 1 2 3 4 ], Matrix B =[ 5 6 7 8], diagArrayA= [1 4 2 3] (Elements stored diagonally in the order main diagonal – super diagonal -sub diagonal), diagArrayB = [5 8 6 7] (Same as above),

Result = A X B = [ 19 50 22 43] (Correct output) The code for multiply function is followed: (The problem seems to be in this function). I will appreciate any comment on the problem/code.

void multiplyDiag(vector <float> diagArrayA, vector <float> diagArrayB){                cout << "function called " << endl;            //please declare as array             // float *a=cutDiagElement(getArray(diagArrayA,-1),0,0);          //   cout << "Value : " << a[0];         vector <float> result;         result.resize(n*n);       float total_time=0.0;       // const int sum=n*(n+1)/2; 

for(int k=0; k<=n-1;k++) { //1

             int start_index=k*n-k*(k-1)/2;               //cout << start_index;             //  int stop_index=start_index+n-k-1;            for(int i=k+1; i<=n-1; i++){ //2                  vector <float> diag_a1=cutDiagElement(getArray(diagArrayA,k-i),0,k);                 // cout << diag_a1[0] <<endl;                   vector <float> diag_b1=cutDiagElement(getArray(diagArrayB,i),0,0);                     int length1=diag_b1.size();                   //  int length1=n-i;                     // length1=length1-0-0;                   //cout << length1;                    float start1=clock();                   for(int j=0; j<=length1-1;j++)                       { //3                               //cout << "OK";                       result[start_index+i-k+j]+=diag_a1[j]*diag_b1[j];                          } //3                   float end1=clock();                   total_time=total_time+(end1-start1);                      vector <float> diag_a2=cutDiagElement(getArray(diagArrayA, i), 0, 0);                    vector <float> diag_b2= cutDiagElement(getArray(diagArrayB,k-i), k, 0);                    //  cout << diag_b2[0];                 //  int length2=diag_a2.size();                     float start2=clock();                    for(int j=0; j<=length1-1;j++)                        { //4                                 result[start_index+j]+=diag_a2[j]*diag_b2[j];                                //  cout<< multiply_result[start_index+j] << endl;                          }    //4                    float end2=clock();                  total_time=total_time+(end2-start2);          } //2     for(int i=0; i<=k; i++)      { //5              vector <float> diag_a3=cutDiagElement(getArray(diagArrayA, i), 0, k-i);                vector <float> diag_b3 = cutDiagElement(getArray(diagArrayB, k-i), i, 0);                int length3=diag_a3.size();              //   int length3=n-i;                //  length3=length3-(k-i);                float start3=clock();                  for(int j=0; j<=length3-1;j++){ //6                                             result[start_index+j]+=diag_a3[j]*diag_b3[j];                                               //cout<< multiply_result[start_index+j] << endl;                                }  //6             float end3=clock();           total_time=total_time+(end3-start3);       } //5 

}//1

// computing sub diagonal

for(int k=1; k<=n-1; k++) { //7

    int start_index=n*(n+1)/2+(k-1)*n-k*(k-1)/2;       // int stop_index=start_index+n-k-1;     for(int i=k+1; i<=n-1; i++)      { //8               vector <float> diag_a1=cutDiagElement(getArray(diagArrayA, -i), 0, 0);                vector <float> diag_b1= cutDiagElement(getArray(diagArrayB, i-k), 0, k);                int length1=diag_b1.size();               // int length1=n-(i-k);                 //   length1=length1-k;                float start4=clock();                for(int j=0; j<=length1-1;j++){ //9                            result[start_index+i+j-k]+=diag_a1[j]*diag_b1[j];                       } //9                  float end4=clock();                   total_time=total_time+(end4-start4);                   vector <float> diag_a2=cutDiagElement(getArray(diagArrayA, i-k), k, 0);                   vector <float> diag_b2= cutDiagElement(getArray(diagArrayB,-i), 0, 0);                 // int length2=diag_a2.size();                  float start5=clock();                   for(int j=0; j<=length1-1;j++)                            { //10                               result[start_index+j]+=diag_a2[j]*diag_b2[j];                            }//10                       float end5=clock();                 total_time=total_time+(end5-start5);        } //8     for(int i=0; i<=k; i++)                { //11                     vector <float> diag_a3=cutDiagElement(getArray(diagArrayA, -i), k-i, 0);                       vector <float> diag_b3 = cutDiagElement(getArray(diagArrayB, i-k), 0, i);                        int length3=diag_a3.size();                      //     int length3=n-i;                        //     length3=length3-(k-i);                      float start6=clock();                      for(int j=0; j<=length3-1;j++){ //12                                             result[start_index+j]+=diag_a3[j]*diag_b3[j];                                }  //12                    float end6=clock();                   total_time=total_time+(end6-start6);                   } //11 

} //7

cout << “time :” << (total_time) / CLOCKS_PER_SEC*1000 <

           cout << result[x] << endl;             } 

}

Multiplying N x N matrices using Diagonal storage

This question is a part of my research. I am trying to multiply two N X N matrices which are stored diagonally. I implemented the following algorithm for this purpose which is working correctly but the problem is it is taking way too much time. For example, To multiply 1000 x 1000 matrices, it is taking almost 26 minutes. I am giving an small example for better understanding of what I am trying to accomplish.

Matrix A = [ 1 2 3 4 ], Matrix B =[ 5 6 7 8], diagArrayA= [1 4 2 3] (Elements stored diagonally in the order main diagonal – super diagonal -sub diagonal), diagArrayB = [5 8 6 7] (Same as above),

Result = A X B = [ 19 50 22 43] (Correct output) The code for multiply function is followed: (The problem seems to be in this function). I will appreciate any comment on the problem/code.

void multiplyDiag(vector <float> diagArrayA, vector <float> diagArrayB){                cout << "function called " << endl;            //please declare as array             // float *a=cutDiagElement(getArray(diagArrayA,-1),0,0);          //   cout << "Value : " << a[0];         vector <float> result;         result.resize(n*n);       float total_time=0.0;       // const int sum=n*(n+1)/2; 

for(int k=0; k<=n-1;k++) { //1

             int start_index=k*n-k*(k-1)/2;               //cout << start_index;             //  int stop_index=start_index+n-k-1;            for(int i=k+1; i<=n-1; i++){ //2                  vector <float> diag_a1=cutDiagElement(getArray(diagArrayA,k-i),0,k);                 // cout << diag_a1[0] <<endl;                   vector <float> diag_b1=cutDiagElement(getArray(diagArrayB,i),0,0);                     int length1=diag_b1.size();                   //  int length1=n-i;                     // length1=length1-0-0;                   //cout << length1;                    float start1=clock();                   for(int j=0; j<=length1-1;j++)                       { //3                               //cout << "OK";                       result[start_index+i-k+j]+=diag_a1[j]*diag_b1[j];                          } //3                   float end1=clock();                   total_time=total_time+(end1-start1);                      vector <float> diag_a2=cutDiagElement(getArray(diagArrayA, i), 0, 0);                    vector <float> diag_b2= cutDiagElement(getArray(diagArrayB,k-i), k, 0);                    //  cout << diag_b2[0];                 //  int length2=diag_a2.size();                     float start2=clock();                    for(int j=0; j<=length1-1;j++)                        { //4                                 result[start_index+j]+=diag_a2[j]*diag_b2[j];                                //  cout<< multiply_result[start_index+j] << endl;                          }    //4                    float end2=clock();                  total_time=total_time+(end2-start2);          } //2     for(int i=0; i<=k; i++)      { //5              vector <float> diag_a3=cutDiagElement(getArray(diagArrayA, i), 0, k-i);                vector <float> diag_b3 = cutDiagElement(getArray(diagArrayB, k-i), i, 0);                int length3=diag_a3.size();              //   int length3=n-i;                //  length3=length3-(k-i);                float start3=clock();                  for(int j=0; j<=length3-1;j++){ //6                                             result[start_index+j]+=diag_a3[j]*diag_b3[j];                                               //cout<< multiply_result[start_index+j] << endl;                                }  //6             float end3=clock();           total_time=total_time+(end3-start3);       } //5 

}//1

// computing sub diagonal

for(int k=1; k<=n-1; k++) { //7

    int start_index=n*(n+1)/2+(k-1)*n-k*(k-1)/2;       // int stop_index=start_index+n-k-1;     for(int i=k+1; i<=n-1; i++)      { //8               vector <float> diag_a1=cutDiagElement(getArray(diagArrayA, -i), 0, 0);                vector <float> diag_b1= cutDiagElement(getArray(diagArrayB, i-k), 0, k);                int length1=diag_b1.size();               // int length1=n-(i-k);                 //   length1=length1-k;                float start4=clock();                for(int j=0; j<=length1-1;j++){ //9                            result[start_index+i+j-k]+=diag_a1[j]*diag_b1[j];                       } //9                  float end4=clock();                   total_time=total_time+(end4-start4);                   vector <float> diag_a2=cutDiagElement(getArray(diagArrayA, i-k), k, 0);                   vector <float> diag_b2= cutDiagElement(getArray(diagArrayB,-i), 0, 0);                 // int length2=diag_a2.size();                  float start5=clock();                   for(int j=0; j<=length1-1;j++)                            { //10                               result[start_index+j]+=diag_a2[j]*diag_b2[j];                            }//10                       float end5=clock();                 total_time=total_time+(end5-start5);        } //8     for(int i=0; i<=k; i++)                { //11                     vector <float> diag_a3=cutDiagElement(getArray(diagArrayA, -i), k-i, 0);                       vector <float> diag_b3 = cutDiagElement(getArray(diagArrayB, i-k), 0, i);                        int length3=diag_a3.size();                      //     int length3=n-i;                        //     length3=length3-(k-i);                      float start6=clock();                      for(int j=0; j<=length3-1;j++){ //12                                             result[start_index+j]+=diag_a3[j]*diag_b3[j];                                }  //12                    float end6=clock();                   total_time=total_time+(end6-start6);                   } //11 

} //7

cout << “time :” << (total_time) / CLOCKS_PER_SEC*1000 <

           cout << result[x] << endl;             } 

}

spectral sequence example diagonal map confusion

I’m attempting to wrap my head around spectral sequences, so constructed a really basic example to apply the definitions and go through the motions. My filtered chain complexes are:

$ F_2C_*: 0 \rightarrow \mathbb{Z} \xrightarrow{i_1} \mathbb{Z_1}\oplus \mathbb{Z_2} \xrightarrow{p_2} \mathbb{Z} \rightarrow 0 $

$ F_1C_*: 0 \rightarrow 0 \rightarrow \mathbb{Z}_2 \xrightarrow{p_2} \mathbb{Z} \rightarrow 0 $

$ F_0C_*:$ The zero complex.

Here $ i_1$ and $ p_2$ are the inclusion and projection maps, and the sub-indices on the $ \mathbb{Z}s$ are just for labeling purposes.

With $ Z^r_{p,q}$ defined as $ \{x \in F_pC_q : \partial x \in F_{p-r}C_{q-1}\}/F_{p-1}C_q$ , the differential is meant to restrict to well-defined maps $ d^r:Z^r_{p,q} \rightarrow Z^r_{p-r,q-1}$ .

But in my example the map $ Z^1_{2,2} \rightarrow Z^1_{1,1}$ does not appear to be well-defined:

$ Z^1_{2,2} := \{x \in \mathbb{Z}\oplus \mathbb{Z} : p_2 x \in \mathbb{Z} \}/\mathbb{Z}_2 \cong \mathbb{Z}_1$ ,

$ Z^1_{1,1} := \mathbb{Z}$ .

However $ [(a,b)]$ and $ [(a,b’)]$ in $ Z^1_{2,2}$ get sent to $ b$ and $ b’$ in $ \mathbb{Z}$ respectively, even though $ [(a,b)] = [(a,b’)]$ .

I cannot see where I’ve made a mistake, but I’m pretty sure something’s not right. Where have I gone wrong?