3
$\begingroup$

So, if one is asked if a given matrix $A$ is symmetric, one could compute $A^T$ and check if $A^T=A$, however you can also simply check the symmetric entries accross the diagonal and see if they are equal (i.e whether $A_{ij}=A_{ji}$).

If one wishes to check if a square matrix is orthogonal, one could compute all the dot products of it's rows and columns, which, assuming an $n\times n$ matrix, requires $2\times\binom{n}{2}$ dot products (and this is without taking into account that as $n$ increases, so does the number of arguments in the sum of each dot product).

So, is there a shortcut that one may use to tell that a given matrix is orthogonal without having to compute all the dot products?

$\endgroup$
5
  • 1
    $\begingroup$ "simply check the symmetric entries accross the diagonal and see if they are equal" is exactly the same as checking that $A^T=A$, so I don't know why you call that a shortcut. $\endgroup$
    – Arthur
    Commented Nov 25, 2017 at 22:58
  • 2
    $\begingroup$ Think of it algorithmically, computing $A^T$ takes $O(n\times n)$ steps, however checking the symmetric entries only takes $2O(n)=O(n)$. It's a shortcut in the sense that if I ahve to code it, it's much shorter that way. Like computing 2*a+2*b+2*c = 2(a+b+c), they are the same, but the right hand side is much faster computationally. $\endgroup$
    – Makogan
    Commented Nov 25, 2017 at 23:16
  • 2
    $\begingroup$ checking the symmetric entries is still an $O(n^2)$ since you have to read all the matrix, and check a condition of the type $a=b$ at least $n(n-1)/2$ times $\endgroup$
    – Exodd
    Commented Nov 26, 2017 at 1:57
  • $\begingroup$ You are correct, I messed up my analysis, however checking the entries diagonally will still require less computations (the asymptotic running time is the same I agree, I was wrong), since you don't have to compute $A^T$ and then check the entries in between $A$ and $A^T$ $\endgroup$
    – Makogan
    Commented Nov 26, 2017 at 6:15
  • $\begingroup$ This is the algorithm shortcut in numpy: given a Matrix M, Transpose T, Identity I. we execute the following code: Q = M.dot(M.T) # M*T product if array_equal(Q,I): print('''The M matrix is ortogonal) $\endgroup$ Commented Sep 15, 2021 at 10:25

1 Answer 1

-2
$\begingroup$

Computing the dot product is the same as computing the matrix product $A^TA$ and checking it is equa to the identity matrix $I$, that, with the naive algorithm, costs $O(n^3)$ FLOPS.

With fast matrix multiplications, though, you can get down to $O(n^{2.3728639})$ FLOPS, so you can gain something substantial in time.

$\endgroup$
4
  • $\begingroup$ -1. What you are not realizing, is that the proposed and requested method can halt at every moment, or perform partial asserts. Computing the full matrix is the optimal solution but you must finish the computation. This is not addressed in this answer. If you have an estimate for the orthogonality probability, you could choose to assert first and then calculate, or viceversa. Hence the question of the assert for matrix orthogonality still remains valid and useful. $\endgroup$
    – Brethlosze
    Commented Nov 26, 2017 at 4:34
  • $\begingroup$ @hyprfrcb What does that mean? There exist matrix multiplication algorithms that run faster than cubic time and always complete. I don't know what "can halt at every moment" means or what this has to do with asserts. $\endgroup$
    – user507295
    Commented Nov 28, 2017 at 6:53
  • $\begingroup$ @WhatToDo The question means not to calculate the full matrix and then evaluate if the full matrix is orthogonal, but means to calculate lesser operations for assessing the property. Lets say a 10% of the full computation power for asserting it. This has full meaning for big size matrices. $\endgroup$
    – Brethlosze
    Commented Nov 28, 2017 at 14:49
  • $\begingroup$ @hyprfrcb With the fast multiplication of matrices you are saving operations with respect to doing all dot products. Moreover, a saving of the order of $\sqrt n$ has full meaning especially for big size matrices, and the saving is much more than 90% $\endgroup$
    – Exodd
    Commented Nov 28, 2017 at 15:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .