Check whether a given matrix is orthogonal or not
We are given a matrix, we need to check whether it is an orthogonal matrix or not. An orthogonal matrix is a square matrix and satisfies the following condition:
A*At = I
Examples :
Input: 1 0 0 0 1 0 0 0 1 Output: Yes Given Matrix is an orthogonal matrix. When we multiply it with its transpose, we get identity matrix. Input: 1 2 3 4 5 6 7 8 9 Output: No Given Matrix Is Not An Orthogonal Matrix
Simple Solution: The idea is simple, we first find the transpose of matrix. Then we multiply the transpose with the given matrix. Finally, we check if the matrix obtained is identity or not.
Implementation:
C++
// C++ code to check whether // a matrix is orthogonal or not #include <bits/stdc++.h> using namespace std; #define MAX 100 bool isOrthogonal( int a[][MAX], int m, int n) { if (m != n) return false ; // Find product of a[][] // and its transpose int prod[n][n]; for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { int sum = 0; for ( int k = 0; k < n; k++) { // Since we are multiplying with // transpose of itself. We use sum = sum + (a[i][k] * a[j][k]); } prod[i][j] = sum; } } // Check if product is identity matrix for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { if (i != j && prod[i][j] != 0) return false ; if (i == j && prod[i][j] != 1) return false ; } } return true ; } // Driver Code int main() { int a[][MAX] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; if (isOrthogonal(a, 3, 3)) cout << "Yes" ; else cout << "No" ; return 0; } |
C
// C code to check whether // a matrix is orthogonal or not #include <stdio.h> #include <stdbool.h> #define MAX 100 bool isOrthogonal( int a[][MAX], int m, int n) { if (m != n) return false ; // Find transpose int trans[n][n]; for ( int i = 0; i < n; i++) for ( int j = 0; j < n; j++) trans[i][j] = a[j][i]; // Find product of a[][] // and its transpose int prod[n][n]; for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { int sum = 0; for ( int k = 0; k < n; k++) { // Since we are multiplying with // transpose of itself. We use sum = sum + (a[i][k] * a[j][k]); } prod[i][j] = sum; } } // Check if product is identity matrix for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { if (i != j && prod[i][j] != 0) return false ; if (i == j && prod[i][j] != 1) return false ; } } return true ; } // Driver Code int main() { int a[][MAX] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; if (isOrthogonal(a, 3, 3)) printf ( "Yes" ); else printf ( "No" );; return 0; } // This code is contributed by kothavvsaakash. |
Java
// Java code to check whether // a matrix is orthogonal or not import java .io.*; class GFG { //static int MAX =100; static boolean isOrthogonal( int [][]a, int m, int n) { if (m != n) return false ; // Find transpose int [][]trans = new int [n][n]; for ( int i = 0 ; i < n; i++) for ( int j = 0 ; j < n; j++) trans[i][j] = a[j][i]; // Find product of a[][] // and its transpose int [][]prod = new int [n][n]; for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < n; j++) { int sum = 0 ; for ( int k = 0 ; k < n; k++) { // Since we are multiplying // transpose of itself. We use sum = sum + (a[i][k] * a[j][k]); } prod[i][j] = sum; } } // Check if product is // identity matrix for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < n; j++) { if (i != j && prod[i][j] != 0 ) return false ; if (i == j && prod[i][j] != 1 ) return false ; } } return true ; } // Driver code static public void main (String[] args) { int [][]a = {{ 1 , 0 , 0 }, { 0 , 1 , 0 }, { 0 , 0 , 1 }}; if (isOrthogonal(a, 3 , 3 )) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by anuj_67. |
Python3
# Python code to check # whether a matrix is # orthogonal or not def isOrthogonal(a, m, n) : if (m ! = n) : return False trans = [[ 0 for x in range (n)] for y in range (n)] # Find transpose for i in range ( 0 , n) : for j in range ( 0 , n) : trans[i][j] = a[j][i] prod = [[ 0 for x in range (n)] for y in range (n)] # Find product of a[][] # and its transpose for i in range ( 0 , n) : for j in range ( 0 , n) : sum = 0 for k in range ( 0 , n) : # Since we are multiplying # with transpose of itself. # We use sum = sum + (a[i][k] * a[j][k]) prod[i][j] = sum # Check if product is # identity matrix for i in range ( 0 , n) : for j in range ( 0 , n) : if (i ! = j and prod[i][j] ! = 0 ) : return False if (i = = j and prod[i][j] ! = 1 ) : return False return True # Driver Code a = [[ 1 , 0 , 0 ], [ 0 , 1 , 0 ], [ 0 , 0 , 1 ]] if (isOrthogonal(a, 3 , 3 )) : print ( "Yes" ) else : print ( "No" ) # This code is contributed by # Manish Shaw(manishshaw1) |
C#
// C# code to check whether // a matrix is orthogonal or not using System; class GFG { //static int MAX =100; static bool isOrthogonal( int [,]a, int m, int n) { if (m != n) return false ; // Find transpose int [,]trans = new int [n, n]; for ( int i = 0; i < n; i++) for ( int j = 0; j < n; j++) trans[i, j] = a[j, i]; // Find product of a[][] // and its transpose int [,]prod = new int [n, n]; for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { int sum = 0; for ( int k = 0; k < n; k++) { // Since we are multiplying // transpose of itself. We use sum = sum + (a[i, k] * a[j, k]); } prod[i, j] = sum; } } // Check if product is // identity matrix for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { if (i != j && prod[i, j] != 0) return false ; if (i == j && prod[i, j] != 1) return false ; } } return true ; } // Driver code static public void Main () { int [,]a = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; if (isOrthogonal(a, 3, 3)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by vt_m |
PHP
<?php // PHP code to check whether // a matrix is orthogonal or not function isOrthogonal( $a , $m , $n ) { if ( $m != $n ) return false; // Find transpose for ( $i = 0; $i < $n ; $i ++) for ( $j = 0; $j < $n ; $j ++) $trans [ $i ][ $j ] = $a [ $j ][ $i ]; // Find product of a[][] // and its transpose for ( $i = 0; $i < $n ; $i ++) { for ( $j = 0; $j < $n ; $j ++) { $sum = 0; for ( $k = 0; $k < $n ; $k ++) { // Since we are multiplying with // transpose of itself. We use $sum = $sum + ( $a [ $i ][ $k ] * $a [ $j ][ $k ]); } $prod [ $i ][ $j ] = $sum ; } } // Check if product is // identity matrix for ( $i = 0; $i < $n ; $i ++) { for ( $j = 0; $j < $n ; $j ++) { if ( $i != $j && $prod [ $i ][ $j ] != 0) return false; if ( $i == $j && $prod [ $i ][ $j ] != 1) return false; } } return true; } // Driver Code $a = array ( array (1, 0, 0), array (0, 1, 0), array (0, 0, 1)); if (isOrthogonal( $a , 3, 3)) echo "Yes" ; else echo "No" ; // This code is contributed by ajit. ?> |
Javascript
<script> // Javascript code to check whether // a matrix is orthogonal or not // static int MAX =100; function isOrthogonal(a, m, n) { if (m != n) return false ; // Find transpose let trans = new Array(n); for (let i = 0; i < n; i++) { trans[i] = new Array(n); for (let j = 0; j < n; j++) trans[i][j] = a[j][i]; } // Find product of a[][] // and its transpose let prod = new Array(n); for (let i = 0; i < n; i++) { prod[i] = new Array(n); for (let j = 0; j < n; j++) { let sum = 0; for (let k = 0; k < n; k++) { // Since we are multiplying // transpose of itself. We use sum = sum + (a[i][k] * a[j][k]); } prod[i][j] = sum; } } // Check if product is // identity matrix for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (i != j && prod[i][j] != 0) return false ; if (i == j && prod[i][j] != 1) return false ; } } return true ; } // Driver code let a = [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ]; if (isOrthogonal(a, 3, 3)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by divyesh072019 </script> |
Output :
Yes
Time Complexity: O(n*n*n)
Auxiliary Space: O(n*n)
An efficient solution is to combine three traversals into one. Instead of explicitly finding transpose, we use a[j][k] instead of a[k][j]. Also, instead of explicitly computing the product, we check identity while computing the product.
Implementation:
C++
// C++ code to check whether // a matrix is orthogonal or not #include <bits/stdc++.h> using namespace std; #define MAX 100 bool isOrthogonal( int a[][MAX], int m, int n) { if (m != n) return false ; // Multiply A*A^t for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { int sum = 0; for ( int k = 0; k < n; k++) { // Since we are multiplying with // transpose of itself. We use // a[j][k] instead of a[k][j] sum = sum + (a[i][k] * a[j][k]); } if (i == j && sum != 1) return false ; if (i != j && sum != 0) return false ; } } return true ; } // Driver Code int main() { int a[][MAX] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; if (isOrthogonal(a, 3, 3)) cout << "Yes" ; else cout << "No" ; return 0; } |
C
// C code to check whether // a matrix is orthogonal or not #include <stdio.h> #include <stdbool.h> #define MAX 100 bool isOrthogonal( int a[][MAX], int m, int n) { if (m != n) return false ; // Multiply A*A^t for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { int sum = 0; for ( int k = 0; k < n; k++) { // Since we are multiplying with // transpose of itself. We use // a[j][k] instead of a[k][j] sum = sum + (a[i][k] * a[j][k]); } if (i == j && sum != 1) return false ; if (i != j && sum != 0) return false ; } } return true ; } // Driver Code int main() { int a[][MAX] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; if (isOrthogonal(a, 3, 3)) printf ( "Yes" ); else printf ( "No" ); return 0; } // This code is contributed by kothavvsaakash. |
Java
// C# code to check whether // a matrix is orthogonal or not using System; class GFG { //static int MAX =100; static bool isOrthogonal( int [,]a, int m, int n) { if (m != n) return false ; // Multiply A*A^t for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < n; j++) { int sum = 0 ; for ( int k = 0 ; k < n; k++) { // Since we are multiplying // with transpose of itself. // We use a[j][k] instead // of a[k][j] sum = sum + (a[i, k] * a[j, k]); } if (i == j && sum != 1 ) return false ; if (i != j && sum != 0 ) return false ; } } return true ; } // Driver code public static void Main () { int [,]a = {{ 1 , 0 , 0 }, { 0 , 1 , 0 }, { 0 , 0 , 1 }}; if (isOrthogonal(a, 3 , 3 )) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by vt_m |
Python3
# Python code to check # whether a matrix is # orthogonal or not def isOrthogonal(a, m, n) : if (m ! = n) : return False # Multiply A*A^t for i in range ( 0 , n) : for j in range ( 0 , n) : sum = 0 for k in range ( 0 , n) : # Since we are multiplying # with transpose of itself. # We use a[j][k] instead # of a[k][j] sum = sum + (a[i][k] * a[j][k]) if (i = = j and sum ! = 1 ) : return False if (i ! = j and sum ! = 0 ) : return False return True # Driver Code a = [[ 1 , 0 , 0 ], [ 0 , 1 , 0 ], [ 0 , 0 , 1 ]] if (isOrthogonal(a, 3 , 3 )) : print ( "Yes" ) else : print ( "No" ) # This code is contributed by # Manish Shaw(manishshaw1) |
C#
// C# code to check whether // a matrix is orthogonal or not using System; public class GFG { //static int MAX =100; static bool isOrthogonal( int [,]a, int m, int n) { if (m != n) return false ; // Multiply A*A^t for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { int sum = 0; for ( int k = 0; k < n; k++) { // Since we are multiplying with // transpose of itself. We use // a[j][k] instead of a[k][j] sum = sum + (a[i,k] * a[j,k]); } if (i == j && sum != 1) return false ; if (i != j && sum != 0) return false ; } } return true ; } // Driver code public static void Main () { int [,]a = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; if (isOrthogonal(a, 3, 3)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by vt_m |
PHP
<?php // PHP code to check whether // a matrix is orthogonal or not //$MAX = 100; function isOrthogonal( $a , $m , $n ) { if ( $m != $n ) return false; // Multiply A*A^t for ( $i = 0; $i < $n ; $i ++) { for ( $j = 0; $j < $n ; $j ++) { $sum = 0; for ( $k = 0; $k < $n ; $k ++) { // Since we are multiplying // with transpose of itself. // We use a[j][k] instead // of a[k][j] $sum = $sum + ( $a [ $i ][ $k ] * $a [ $j ][ $k ]); } if ( $i == $j and $sum != 1) return false; if ( $i != $j and $sum != 0) return false; } } return true; } // Driver Code $a = array ( array (1, 0, 0), array (0, 1, 0), array (0, 0, 1)); if (isOrthogonal( $a , 3, 3)) echo "Yes" ; else echo "No" ; // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript code to check whether // a matrix is orthogonal or not MAX=100 function isOrthogonal(a, m, n) { if (m != n) return false ; // Multiply A*A^t for ( var i = 0; i < n; i++) { for ( var j = 0; j < n; j++) { var sum = 0; for ( var k = 0; k < n; k++) { // Since we are multiplying with // transpose of itself. We use // a[j][k] instead of a[k][j] sum = sum + (a[i][k] * a[j][k]); } if (i == j && sum != 1) return false ; if (i != j && sum != 0) return false ; } } return true ; } // Driver Code var a = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]; if (isOrthogonal(a, 3, 3)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by noob2000. </script> |
Output :
Yes
Time Complexity: O(n*n*n)
Auxiliary Space: O(1)
Contact Us